|
|
| (не показано 12 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | <wikitex>
| + | #перенаправление [[Сортировки]] |
| − | ''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку.
| |
| − | | |
| − | Обычно таким признаком служит лексикографический номер.
| |
| − | | |
| − | Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке сортировка слиянием потребует $O(n^2)$ времени и $O(1)$ памяти против $O(n \log n)$ и $O(n)$ с использованием массива; а вот сортировка пузырьком не изменится.
| |
| − | | |
| − | Также есть алгоритмы параллельной сортировки данных (т.н. [[Сортирующие сети]]), время работы которых в лучшем случае $O(\log n)$.
| |
| − | == Классификация сортировок ==
| |
| − | | |
| − | === Время работы ===
| |
| − | | |
| − | Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время — наибольшее время.
| |
| − | У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
| |
| − | | |
| − | === Память ===
| |
| − | | |
| − | Параметр сортировки, показывающий, сколько '''дополнительной''' памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
| |
| − | | |
| − | === Стабильность ===
| |
| − | | |
| − | ''Стабильной сортировкой'' называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.
| |
| − | | |
| − | === Количество обменов ===
| |
| − | | |
| − | Количество обменов может быть важным параметром в случае, если объекты имеют большой размер. В таком случае при большом количестве обменов время алгоритма заметно увеличивается.
| |
| − | | |
| − | === Детерминированность ===
| |
| − | | |
| − | Алгоритм сортировки называется ''детерминированным'', если каждая операция присваивания, обмена и т.д. не зависит от предыдущих.
| |
| − | Все сортирующие сети являются детерминированными.
| |
| − | | |
| − | == Сравнение сортировок ==
| |
| − | | |
| − | | |
| − | Будем рассматривать сортировки массива из $n$ элементов множества $A$,
| |
| − | причем на $A$ должно быть выполнено [[Бинарное отношение|отношение эквивалентности]].
| |
| − | | |
| − | | |
| − | {|class="wikitable"
| |
| − | |+
| |
| − | !width="15%"|Название !!width="8%"| Лучшее время !!width="8%"| Среднее !!width="8%"| Худшее !!width="8%"| Память !! width="8%"|Стабильность !! width="10%| Обмены (в среднем) !! "width="35%"| Описание
| |
| − | |- align = "center"
| |
| − | |[[Сортировка пузырьком| Сортировка пузырьком <br>(Bubble Sort)]]
| |
| − | |$O(n)$
| |
| − | |$O(n^2)$
| |
| − | |$O(n^2)$
| |
| − | |$O(1)$
| |
| − | |Да
| |
| − | |$O(n^2)$
| |
| − | |Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
| |
| − | |- align = "center"
| |
| − | |[[Сортировка вставками| Сортировка вставками <br>(Insertion Sort)]]
| |
| − | |$O(n)$
| |
| − | |$O(n^2)$
| |
| − | |$O(n^2)$
| |
| − | |$O(1)$
| |
| − | |Да
| |
| − | |$O(n^2)$
| |
| − | |На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
| |
| − | |- align = "center"
| |
| − | |[[Сортировка выбором| Сортировка выбором<br> (Selection Sort)]]
| |
| − | |$O(n^2)$
| |
| − | |$O(n^2)$
| |
| − | |$O(n^2)$
| |
| − | |$O(1)$
| |
| − | |Нет
| |
| − | |$O(n)$
| |
| − | |На $i$-ом шаге алгоритма находим минимальный среди последних $n - i + 1$, и меняем его местами с $i$-ым элементом в массиве.
| |
| − | |- align = "center"
| |
| − | |[[Быстрая сортировка|Быстрая сортировка<br> (Quick Sort)]]
| |
| − | |$O(n \log n)$
| |
| − | |$O(n \log n)$
| |
| − | |$O(n^2)$<br>(маловероятно)
| |
| − | |$O(\log n)$<br>(стек вызовов)
| |
| − | |Нет
| |
| − | |$O(n \log n)$
| |
| − | |Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного (одна — все элементы, меньшие опорного элемента, вторая — большие), и в сортировке полученных частей рекурсивным вызовом себя от них.
| |
| − | |- align = "center"
| |
| − | |[[Сортировка слиянием|Сортировка слиянием <br>(Merge Sort)]]
| |
| − | |$O(n \log n)$
| |
| − | |$O(n \log n)$
| |
| − | |$O(n \log n)$
| |
| − | |$O(n)$ (обычная реализация)<br>$O(\log n)$<br> ([[Cортировка слиянием с использованием O(1) дополнительной памяти|модифицированная реализация]])
| |
| − | |Да
| |
| − | |$O(n \log n)$
| |
| − | |Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.
| |
| − | |- align = "center"
| |
| − | |[[Сортировка кучей|Пирамидальная сортировка <br>(Heap Sort)]]
| |
| − | |$O(n \log n)$
| |
| − | |$O(n \log n)$
| |
| − | |$O(n \log n)$
| |
| − | |$O(1)$
| |
| − | |Нет
| |
| − | |$O(n \log n)$
| |
| − | |Строим из массива кучу, по очереди извлекаем минимум кучи.
| |
| − | |- align = "center"
| |
| − | |[[Дерево поиска, наивная реализация|Сортировка с помощью бинарного дерева <br>(Tree Sort)]]
| |
| − | |$O(n)$
| |
| − | |$O(n \log n)$
| |
| − | |$O(n \log n)$
| |
| − | |$O(n)$
| |
| − | |Да
| |
| − | |$O(n)$
| |
| − | |Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания.
| |
| − | |- align = "center"
| |
| − | |[[Карманная сортировка|Карманная сортировка <br>(Bucked Sort)]]
| |
| − | |$O(n)$
| |
| − | |$O(n \log_k n)$
| |
| − | |$O(n^2)$
| |
| − | |$O(n)$
| |
| − | |Да
| |
| − | | -
| |
| − | |распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
| |
| − | |- align = "center"
| |
| − | |[[Цифровая сортировка|Цифровая сортировка <br>(Radix Sort)]]
| |
| − | |$O(n \lg n)$
| |
| − | |$O(n \lg n)$
| |
| − | |$O(n \lg n)$
| |
| − | |$O(n)$
| |
| − | |Да
| |
| − | | -
| |
| − | |Сортировка объектов равной длины, имеющих "разряды". обычно это строки или целые числа. Алгоритм состоит в том, чтобы отсортировать объекты по разрядам, начиная от младших к старшим.
| |
| − | |- align = "center"
| |
| − | |[[Сортировка подсчетом|Сортировка подсчетом <br>(Counting Sort)]]
| |
| − | |$O(n)$
| |
| − | |$O(n + k)$
| |
| − | |$O(k)$
| |
| − | |$O(k)$
| |
| − | |Да
| |
| − | |$O(n + k)$
| |
| − | |Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона $k$, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа.
| |
| − | |- align = "center"
| |
| − | |[[Сортировка Хэна (или Хана?)|Сортировка Хэна <br>(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)$
| |
| − | |Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.
| |
| − | |}
| |
| − | | |
| − | | |
| − | | |
| − | == Ссылки ==
| |
| − | | |
| − | [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8 Википедия срывает покровы]
| |
| − | </wikitex>
| |
| − | [[Категория: Дискретная математика и алгоритмы]]
| |
| − | [[Категория: Сортировки]]
| |
