Сортировка
<wikitex>
Сортировкой называется процесс упорядочивания множества объектов по какому-либо признаку.
Обычно таким признаком служит лексикографический номер.
Классификация сортировок
Будем рассматиривать сортировки массива из $n$ элементов множества $A$, причем на $A$ должно быть выполнено отношение эквивалентности.
Время работы.
Эта классификация является самой важной. Оценивают худшее время алгоритма, среднее и лучшее. У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
Память
Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
Стабильность
Стабильной сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами.
Количество обменов
Важный параметр, когда объекты имеют большой размер. В таком случае при большом кол-ве обменов время алгоритма заметно увеличивается.
Сравнение сортировок
| Название | Лучшее время | Среднее | Худшее | Память | Стабильность | Обмены (в среднем) | Описание |
|---|---|---|---|---|---|---|---|
| Сортировка пузырьком (Bubble Sort) |
$O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Да | $O(n^2)$ | Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. |
| Сортировка вставками (Insertion Sort) |
$O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Да | $O(n^2)$ | На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован. |
| Сортировка выбором (Selection Sort) |
$O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Нет | $O(n)$ | На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве. |
| Быстрая сортировка (Quick Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ (маловероятно) |
$O(\log n)$ (стек вызовов) |
Нет | $O(n \log n)$ | Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного и в сортировке полученных частей. |
| Сортировка слиянием (Merge Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ (обычная реализация) $O(1)$ (модифицированная реализация) |
Да | $O(n \log n)$ | Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии. |
| Пирамидальная сортировка (Heap Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Нет | $O(n \log n)$ | Строим из массива кучу, по очереди извлекаем минимум кучи. |
| Сортировка с помощью бинарного дерева (Tree Sort) |
$O(n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Да | $O(n)$ | Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания. |
| Карманная сортировка (Bucked Sort) |
$O(n)$ | $O(n \log n)$ | $O(n^2)$ | $O(n)$ | Да | - | распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения. |
| Цифровая сортировка (Radix Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Да | - | сортировка, аналогичная карманной. карманы в данном случае - цифры от 0 до 9. |
- Прочие сортировки.
- Сортировка подсчетом. Сортировка объектов, ключи которых входят в заранее известный диапазон целых чисел. Время работы - $O(n + k)$, где $k$ - длина диапазона.
- Сортировка Хэна - упоротая сортировка целых чисел с оценкой $O(n \log \log n)$
</wikitex>
