Сортировка

Материал из Викиконспекты
Перейти к: навигация, поиск

<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}$ подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы.

См. также

Источники информации

</wikitex>

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Сортировка&oldid=46810»