💻Алгоритмы сортировки

Алгоритм сортировки упорядочивает элементы коллекции. QuickSort и MergeSort делают это за O(n log n); простые алгоритмы вроде BubbleSort — за O(n²), что на больших данных в тысячи раз медленнее.

Зачем сортировать и почему это сложно

Поиск в отсортированном массиве занимает O(log n) — это двоичный поиск. В неотсортированном — O(n), то есть просматривать каждый элемент. Разница между log(1 000 000) = 20 и 1 000 000 операций огромна. Поэтому сортировка — фундамент алгоритмики.

Сложность в том, что разные алгоритмы лучше работают в разных условиях: маленький массив, почти отсортированный, много повторений, ограничена память. Универсального лучшего алгоритма нет.

Простые алгоритмы — медленные, но понятные

Bubble Sort — сравниваем соседние элементы и меняем местами, если стоят не так. Повторяем, пока массив не отсортирован. O(n²). Для 10 000 элементов — 100 миллионов сравнений. Почти никогда не используется в реальности.

Insertion Sort — берём элемент и вставляем его на правильное место в уже отсортированную часть. Как сортируют карты в руке. O(n²) в худшем случае, но O(n) на почти отсортированном массиве. Используется внутри TimSort для маленьких кусков.

Selection Sort — находим минимум, ставим первым, находим следующий минимум, ставим вторым. O(n²) всегда. Простой, но неэффективный.

Быстрые алгоритмы — O(n log n)

QuickSort (1959, Тони Хоар) — выбираем опорный элемент (pivot), разделяем массив на «меньше pivot» и «больше pivot», рекурсивно сортируем каждую часть. В среднем O(n log n), в худшем — O(n²). На практике самый быстрый для случайных данных.

MergeSort — делим массив пополам, сортируем каждую половину, сливаем. Всегда O(n log n). Стабильный — одинаковые элементы сохраняют порядок. Требует дополнительную память O(n). Хорош для связных списков и внешней сортировки.

HeapSort — строим кучу (heap), затем последовательно извлекаем максимум. Всегда O(n log n), O(1) дополнительной памяти. Но на практике медленнее QuickSort из-за плохой кэш-локальности.

Специальные алгоритмы

Counting Sort — подсчитываем количество каждого значения, затем выстраиваем. O(n + k), где k — диапазон значений. Идеален для сортировки оценок (1–5), возрастов (0–120). Не работает для вещественных чисел.

TimSort — гибрид MergeSort и Insertion Sort. Делит массив на «runs» (уже отсортированные куски), сортирует маленькие части Insertion Sort, сливает MergeSort. O(n log n) в худшем, O(n) для почти отсортированных. Стандартный алгоритм в Python (sorted()) и Java (Arrays.sort()).

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

Маленький массив (<50 элементов) — Insertion Sort. Случайные данные — QuickSort. Нужна стабильность — MergeSort. Почти отсортированный массив — TimSort или Insertion Sort. Целые числа в маленьком диапазоне — Counting Sort.