Как работают алгоритмы сортировки

В Python есть несколько встроенных алгоритмов сортировки, но самые популярные — Timsort (гибридный алгоритм, используемый в sorted() и list.sort()) и классические методы, такие как QuickSort, MergeSort, BubbleSort и другие.

Основные алгоритмы:

1. BubbleSort – простой, но неэффективный (O(n²)).
   python

   Копировать

   def bubble_sort(arr):
       n = len(arr)
       for i in range(n):
           for j in range(0, n-i-1):
               if arr[j] > arr[j+1]:
                   arr[j], arr[j+1] = arr[j+1], arr[j]

2. QuickSort – рекурсивный, средняя сложность O(n log n).

   python

   Копировать

   def quicksort(arr):
       if len(arr) <= 1:
           return arr
       pivot = arr[len(arr) // 2]
       left = [x for x in arr if x < pivot]
       middle = [x for x in arr if x == pivot]
       right = [x for x in arr if x > pivot]
       return quicksort(left) + middle + quicksort(right)

3. Timsort – гибрид MergeSort + InsertionSort (O(n log n) в худшем случае). Используется в Python (оптимизирован для реальных данных).

Выбор алгоритма зависит от данных:

• Для небольших списков подойдет даже BubbleSort.
• Для общего случая лучше sorted() (Timsort).
• Если важна стабильность (сохранение порядка равных элементов) — MergeSort.