Сортировка
<wikitex> Сортировкой (англ. sorting) называется процесс упорядочивания множества объектов по какому-либо признаку.
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке сортировка кучей потребует $O(n^2 \log n)$ времени против $O(n \log n)$ с использованием массива; а вот сортировка пузырьком не изменится.
Также есть алгоритмы параллельной сортировки данных (т.н. Сортирующие сети), время работы которых в лучшем случае $O(\log n)$.
Содержание
Классификация сортировок
Время работы
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время — наибольшее время. У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
Память
Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
Устойчивость
Устойчивой сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.
Количество обменов
Количество обменов может быть важным параметром в случае, если объекты имеют большой размер. В таком случае при большом количестве обменов время алгоритма заметно увеличивается.
Детерминированность
Алгоритм сортировки называется детерминированным, если каждая операция присваивания, обмена и т.д. не зависит от предыдущих. Все сортирующие сети являются детерминированными.
Сравнение сортировок
Рассмотрим массив $\big[ 1 \ldots n \big]$. Для элементов должно выполняться отношение порядка.
| Название | Лучшее время | Среднее | Худшее | Память | Устойчивость | Обмены (в среднем) | Описание |
|---|---|---|---|---|---|---|---|
| Сортировка пузырьком (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)$ | На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован. |
| Сортировка Шелла (Shellsort) |
$O(n\log^2{n})$ | Зависит от выбора шага | $O(n^2)$ | $O(1)$ | Нет | $O(n^2)$ | Является модификацией сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах. |
| Сортировка выбором (Selection Sort) |
$O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Нет | $O(n)$ | На $i$-ом шаге алгоритма находим минимальный среди последних $n - i + 1$, и меняем его местами с $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)$ | Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии. |
| Timsort | $O(n)$ | $O(n\log{n})$ | $O(n\log{n})$ | $O(n)$ | Да | $O(n\log{n})$ | Гибрид сортировки слиянием. Разбиваем массив на подмассивы фиксированной длины и сортируем каждый подмассив любой устойчивой сортировкой. После чего объединяем отсортированные подмассивы модифицированной сортировкой слиянием. |
| Сортировка кучей (Heap Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Нет | $O(n \log n)$ | Строим из массива кучу, по очереди извлекаем минимум кучи. |
| Плавная сортировка (Smoothsort) |
$O(n)$ | $O(n\log{n})$ | $O(n\log{n})$ | $O(1)$ | Нет | $O(n\log{n})$ | Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо. |
| Терпеливая сортировка (Patience sorting) |
$O(n\log{n})$ | $O(n\log{n})$ | $O(n\log{n})$ | $O(n)$ | Нет | $O(n\log{n})$ | Раскидываем элементы массива по стопкам, после чего строим двоичную кучу из стопок. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива. |
| Сортировка с помощью бинарного дерева (Tree Sort) |
$O(n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Да | $O(n)$ | Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания. |
| Карманная сортировка (Bucket Sort) |
$O(n + k)$ | $O(n \log_k n)$ | $O(n \cdot k)$ | $O(n)$ | Да | - | Распределяем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения. |
| Цифровая сортировка (Radix Sort) |
$O(n \lg n)$ | $O(n \lg n)$ | $O(n \lg n)$ | $O(n)$ | Да | - | Сортировка объектов равной длины, имеющих "разряды". обычно это строки или целые числа. Алгоритм состоит в том, чтобы отсортировать объекты по разрядам, начиная от младших к старшим. |
| Сортировка подсчетом (Counting Sort) |
$O(n)$ | $O(n + k)$ | $O(k)$ | $O(k)$ | Да | $O(n + k)$ | Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона $k$, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа. |
| Сортировка Хэна (Han's Sort) |
$O(n \log \log n)$ | $O(n \log \log n)$ | $O(n \log \log n)$ | $O(n)$ | Да | $O(n \log \log n)$ | Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона. |
| Многопоточная сортировка слиянием (Multithreaded merge sort) |
$O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$ | $O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$ | $O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$ | $O(n)$ | Да | $O(n \log n)$ | Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток. |
| PSRS-сортировка (PSRS-sorting) |
$O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$ | $O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$ | $O(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})$ | $O(N_{ind}^2)$ | Нет | $O(n \log n)$ | Разделим массив на $N_{ind}$ подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы. |
См. также
Источники информации
- Википедия — Алгоритмы сортировки
- Wikipedia —Sorting algorithm
- Хабрахабр — Бенчмарк алгоритмов сортировки
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 174. — ISBN 978-5-8459-1794-2
</wikitex>
