Сортировки
31 алгоритм с визуализацией: от пузырька до тима, с Big O, сравнением подходов и разбором того, когда каждый из них имеет смысл
Сортировка - фундаментальная операция в информатике: расположить набор элементов в заданном порядке. Двоичный поиск, построение B-деревьев, работа с индексами баз данных, объединение множеств - всё это либо требует отсортированных данных на входе, либо неявно упорядочивает их внутри. Поэтому алгоритмы сортировки входят в базовый словарь любого инженера.
Устойчивость (stability) - гарантия того, что элементы с одинаковым ключом сохраняют исходный относительный порядок. Пример: сортируем список сотрудников по отделу - устойчивый алгоритм сохранит исходный порядок внутри каждого отдела. Merge Sort, Tim Sort, Counting Sort, Radix Sort, Insertion Sort - устойчивы. Quick Sort, Heap Sort, Selection Sort - нет (при стандартной реализации).
In-place означает: алгоритм использует не более O(log n) дополнительной памяти (стек рекурсии не в счёт). Quick Sort, Heap Sort, Insertion Sort - in-place. Merge Sort требует O(n) дополнительной памяти - это плата за устойчивость и гарантированный O(n log n) в худшем случае.
- Адаптивность: алгоритм использует уже существующий порядок. Insertion Sort и Tim Sort работают за O(n) на почти отсортированных данных - они «замечают» натуральные упорядоченные блоки (runs) и обрабатывают их эффективнее.
- Онлайн-сортировка: Insertion Sort обрабатывает элементы по одному по мере поступления, не требуя полного набора данных заранее. Это важно в потоковых системах.
- Внешняя сортировка: когда данные не помещаются в RAM, нужны алгоритмы, минимизирующие обращения к диску. Классика - External Merge Sort: разбить на отсортированные куски, слить их серией merge-проходов.
- Параллельные сети: Bitonic Sort и Sorting Networks построены как фиксированные схемы сравнений - независимо от данных, поэтому естественно ложатся на GPU и FPGA.
Нет универсально лучшего алгоритма сортировки - каждый оптимален в своей нише. Выбор определяется четырьмя ключевыми факторами: размер данных, степень упорядоченности, допустимый расход памяти и тип ключей.
- Маленькие данные (n < 50): Insertion Sort выигрывает у «умных» алгоритмов за счёт минимального overhead - никаких рекурсий, никаких разбиений. Именно поэтому Tim Sort и Intro Sort переключаются на Insertion Sort для малых подмассивов.
- Почти отсортированные данные: Insertion Sort (O(n) инверсий → O(n) шагов) или Tim Sort - они обнаруживают натуральные runs и объединяют их, не трогая уже упорядоченные части. Shell Sort тоже адаптивен, хотя и без строгих гарантий.
- Нужна устойчивость: Merge Sort (O(n log n) гарантированно, O(n) памяти), Tim Sort (стандарт в Python и Java), Counting Sort (O(n + k), только для целых чисел), Radix Sort (O(d·n) для чисел и строк). Quick Sort и Heap Sort - неустойчивы без специальных ухищрений.
- Минимум памяти (in-place): Heap Sort - O(n log n) всегда, O(1) памяти. Quick Sort - O(n log n) в среднем, O(log n) стек, легко реализуется без лишних аллокаций. Intro Sort добавляет Heap Sort как fallback при глубокой рекурсии.
- Целые числа в диапазоне [0, k): Counting Sort за O(n + k) - при малом k абсолютно неразбиваемо быстро. Для больших ключей - Radix Sort: O(d·n), где d - число разрядов. Bucket Sort - при равномерном распределении.
- Дорогие сравнения (сложные объекты, строки): минимизируйте число сравнений. Merge Sort делает fewer сравнений, чем Quick Sort. Tim Sort ещё умнее - использует двоичный поиск при вставке в run.
Практическое правило: в большинстве задач Tim Sort (Python, Java, Android) или pdqsort / Intro Sort (C++ STL, Rust) - правильный выбор по умолчанию. Они адаптивны, дают worst-case гарантии и хорошо оптимизированы в рантайме.
Нижняя граница для сравнительных алгоритмов - Ω(n log n). Доказательство: любой алгоритм, основанный исключительно на попарных сравнениях, порождает дерево решений с n! листьями (по числу возможных перестановок). Высота такого дерева - log₂(n!) ≈ n log₂ n по формуле Стирлинга. Следовательно, в худшем случае потребуется не менее ⌈log₂(n!)⌉ сравнений - обойти это теоретически невозможно.
- O(n²) - квадратичные: Bubble Sort, Insertion Sort, Selection Sort. Просты в реализации, без overhead. Эффективны при n < 50 или почти отсортированных данных (Insertion Sort: O(n) при O(n) инверсиях).
- O(n log n) - оптимальные сравнительные: Merge Sort и Heap Sort - всегда. Quick Sort - в среднем; O(n²) при вырожденных данных, устраняется рандомизацией или выбором медианы трёх. Tim Sort и Intro Sort комбинируют несколько алгоритмов для worst-case гарантий.
- O(n log² n) - субоптимальные гибриды: Shell Sort - исторически важен, на практике быстрее O(n²), но без строгих O(n log n) гарантий. Используется в нишевых embedded-системах.
- O(n + k) - линейные (не-сравнительные): Counting Sort (k - диапазон значений), Bucket Sort (равномерное распределение), Radix Sort (O(d·(n + k))). Они обходят нижнюю границу, работая с ключами напрямую, а не попарно сравнивая.
- O(n²) учебные исключения: Bogosort - O((n+1)!) в среднем; Stooge Sort - O(n^(log 3 / log 1.5)) ≈ O(n^2.7). Включены как контрпримеры: они намеренно неэффективны и показывают, что «работает правильно» и «работает эффективно» - разные вещи.
Важно разделять амортизированную и worst-case сложность. Quick Sort имеет O(n log n) в среднем, но O(n²) в худшем случае - что можно вызвать заранее подготовленными данными. Именно поэтому production-стандарт - Intro Sort: Quick Sort, переключающийся на Heap Sort при глубине рекурсии > 2 log n.
Алгоритмы сортировки классифицируются по нескольким независимым осям. Понимание этих осей помогает быстро выбирать и комбинировать алгоритмы под конкретную задачу.
- Сравнительные - работают с любыми элементами, у которых определён порядок: Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, Shell Sort, Tim Sort, Intro Sort. Нижний предел: Ω(n log n).
- Не-сравнительные - используют структуру ключей напрямую: Counting Sort (целые числа), Radix Sort (поразрядно для чисел и строк), Bucket Sort (равномерное распределение), Flash Sort (обобщённый Bucket). Могут работать за O(n).
- Устойчивые: Insertion Sort, Merge Sort, Tim Sort, Counting Sort, Radix Sort, Bucket Sort - равные элементы сохраняют исходный относительный порядок.
- Неустойчивые: Selection Sort, Quick Sort (стандартный), Heap Sort, Shell Sort, Intro Sort - при стандартной реализации порядок равных элементов не гарантирован.
- In-place O(1) памяти: Selection Sort, Bubble Sort, Heap Sort.
- In-place O(log n) стек: Quick Sort (глубина рекурсии), Shell Sort.
- O(n) дополнительной памяти: Merge Sort, Tim Sort - плата за устойчивость.
- O(n + k) памяти: Counting Sort, Radix Sort, Bucket Sort - дополнительные массивы для счётчиков и корзин.
- Divide & Conquer: Merge Sort, Quick Sort - рекурсивное разбиение на подзадачи.
- Heap-based: Heap Sort - структура данных «куча» позволяет извлекать максимум за O(log n).
- Гибридные адаптивные: Tim Sort (Insertion Sort + Merge Sort), Intro Sort (Quick Sort + Heap Sort + Insertion Sort) - комбинируют сильные стороны нескольких алгоритмов.
- Специализированные: Radix Sort, Counting Sort, Bucket Sort, Flash Sort - оптимизированы под конкретный тип данных.
- Сети сортировки: Bitonic Sort, Sorting Networks - фиксированная схема сравнений, не зависящая от данных; эффективны для параллельных вычислений на GPU и FPGA.
Bubble Sort
Пузырьковая сортировка многократно проходит по массиву, меняя местами соседние элементы, пока весь массив не окажется упорядочен.
Selection Sort
Сортировка выбором на каждом шаге находит наименьший элемент в неотсортированной части массива и ставит его сразу после уже отсортированной части.
Insertion Sort
Сортировка вставками строит отсортированную часть массива слева направо, забирая по одному элементу из неотсортированной части и вставляя его на правильную позицию.
Merge Sort
Сортировка слиянием рекурсивно делит массив пополам, сортирует каждую половину независимо, а затем сливает две отсортированные половины в один отсортированный массив.
Quick Sort
Быстрая сортировка выбирает опорный элемент, разбивает массив на элементы меньше и больше опорного, а затем рекурсивно сортирует каждую часть - почти всегда на месте и с очень низкими константными накладными расходами.
Heap Sort
Пирамидальная сортировка строит из массива структуру данных «куча» (heap) и многократно извлекает из неё наибольший элемент, помещая его в конец массива - гарантированно за O(n log n) в любом случае, без рекурсии и почти без дополнительной памяти.
Shell Sort
Сортировка Шелла - это сортировка вставками, которая сначала сравнивает и переставляет далеко отстоящие друг от друга элементы, постепенно сокращая это расстояние (gap) до 1.
Cocktail Shaker Sort
Шейкерная сортировка - это двунаправленная пузырьковая сортировка: она поочерёдно проходит массив слева направо и справа налево, «выталкивая» на каждом проходе и самый большой, и самый маленький ещё не отсортированный элемент.
Comb Sort
Сортировка расчёской - это улучшение пузырьковой сортировки: она сравнивает элементы, отстоящие друг от друга на убывающий промежуток (gap), а не только соседей, что устраняет главную слабость bubble sort - маленькие элементы («черепахи»), застревающие в конце.
Counting Sort
Сортировка подсчётом не сравнивает элементы друг с другом - она считает, сколько раз встречается каждое значение, и по этим подсчётам напрямую вычисляет финальную позицию каждого элемента.
Radix Sort
Поразрядная сортировка упорядочивает числа, сортируя их многократно по одному разряду за раз - от младшего к старшему - используя на каждом шаге устойчивую сортировку подсчётом.
Bucket Sort
Блочная сортировка распределяет элементы по нескольким «корзинам» (bucket) в соответствии с их значением, сортирует каждую корзину отдельно (обычно простым алгоритмом), а затем соединяет корзины по порядку.
Timsort
Timsort - гибридный алгоритм, объединяющий сортировку вставками для маленьких «прогонов» (run) и сортировку слиянием для их объединения, специально настроенный на реальные данные, которые часто содержат уже отсортированные участки.
Introsort
Интроспективная сортировка начинает как быстрая сортировка, но следит за глубиной рекурсии и переключается на пирамидальную сортировку, если рекурсия уходит слишком глубоко, а на маленьких подмассивах - на сортировку вставками.
Cycle Sort
Циклическая сортировка находит для каждого элемента его финальную позицию в отсортированном массиве и переставляет элементы по циклам так, чтобы каждый элемент был записан ровно один раз.
Smoothsort
Смузсорт, придуманный Эдсгером Дейкстрой, - вариант пирамидальной сортировки, который строит не один бинарный, а лес куч Леонардо переменного размера, что позволяет ему адаптивно ускоряться на частично отсортированных данных, оставаясь сортировкой на месте с O(1) памяти.
Tournament Sort
Турнирная сортировка - вариант сортировки выбором, который находит минимум не за O(n) линейным проходом, а за O(log n) с помощью бинарного дерева турнира, где каждый внутренний узел хранит «победителя» сравнения своих потомков.
Patience Sort
Пасьянсная сортировка вдохновлена карточным пасьянсом «солитёр»: карты раскладываются по стопкам так, чтобы верх каждой стопки не убывал сверху вниз, а затем стопки сливаются как в merge sort - попутно алгоритм даёт изящный способ найти длиннейшую возрастающую подпоследовательность.
Block Sort (WikiSort)
Блочная сортировка (семейство алгоритмов, к которому относится WikiSort) - это устойчивая сортировка слиянием, которая сливает два отсортированных участка на месте, без вспомогательного массива размером O(n), в отличие от классического merge sort.
Library Sort
Библиотечная сортировка (или gapped insertion sort) - вставочная сортировка, которая держит между элементами свободные «зазоры», чтобы вставка нового элемента чаще всего не требовала сдвигать большой хвост массива, как в обычной сортировке вставками, а находила себе пустое место рядом.
Gnome Sort
Гномья сортировка получила название по методу, которым садовый гном якобы сортирует горшки с цветами: он смотрит на два соседних горшка, и если порядок неправильный - меняет их местами и делает шаг назад, а если порядок правильный - делает шаг вперёд.
Odd-Even Sort
Чётно-нечётная сортировка (brick sort) - вариант пузырьковой сортировки, который вместо одного последовательного прохода чередует два независимых набора сравнений: по нечётным и по чётным позициям, что делает пары сравнений внутри каждого набора независимыми друг от друга и пригодными для параллельного выполнения.
Strand Sort
Сортировка прядями раз за разом вытягивает из входных данных максимально длинную уже возрастающую подпоследовательность («прядь»), а затем сливает её с результатом - так же, как последний шаг сортировки слиянием, но без предварительного деления массива пополам.
Pancake Sort
Блинная сортировка сортирует массив, используя только одну операцию - «переворот» (flip) префикса массива, как переворачивание стопки блинов лопаткой: перевернуть верхние k блинов сразу, не трогая остальные.
Postman Sort
Почтовая сортировка названа по методу, которым реальные почтовые сортировочные машины раскладывают письма по индексу: сначала - по первой (самой значимой) цифре в отдельные лотки, а затем каждый лоток заново сортируется по следующей цифре, и так далее, пока письма не окажутся полностью упорядочены.
Bitonic Sort
Битоническая сортировка строит массив из «битонических» последовательностей - тех, что сначала монотонно возрастают, а потом монотонно убывают (или наоборот) - и сливает их фиксированной сетью сравнений, у которой заранее известны все пары элементов для сравнения, независимо от значений самих элементов.
Sorting Network (Batcher's)
Нечётно-чётная сортировка слиянием Батчера строит сортирующую сеть - фиксированную, заранее известную последовательность операций «сравнить и при необходимости поменять местами» - но, в отличие от битонической сортировки, использует другую схему слияния двух уже отсортированных половин, основанную на разделении элементов по чётности их позиции.
Spreadsort
Спред-сортировка - гибридный алгоритм, который на каждом уровне рекурсии выбирает между «распределением» элементов по корзинам (как в корзинной сортировке) и обычной сортировкой сравнениями для маленьких групп, адаптивно подстраиваясь под то, насколько равномерно распределены данные и насколько мала текущая группа.
Flashsort
Флэш-сортировка - алгоритм распределяющей сортировки, который сначала грубо раскидывает элементы по «классам» на основе их значения, переставляет их почти на нужные места за один проход, а затем сортировкой вставками устраняет оставшийся мелкий беспорядок внутри каждого класса.
Bogosort
Бого-сортировка - шуточный алгоритм: массив случайно перемешивается снова и снова, пока он не окажется отсортированным. Это не практичный метод сортировки, а наглядная иллюстрация того, насколько плохим может быть алгоритм и почему «просто пробовать наугад» - не стратегия.
Stooge Sort
Стуз-сортировка - намеренно неэффективный рекурсивный алгоритм: он сравнивает и при необходимости меняет местами лишь крайние элементы диапазона, а затем трижды рекурсивно обрабатывает пересекающиеся две трети диапазона - интересный не практической пользой, а тем, насколько простая на вид рекурсия может давать почти кубическую сложность.