3622
правки
Изменения
м
<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]$. Для элементов должно выполняться отношение порядка. {|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>(Shellsort)]]|$O(n\log^2{n})$|Зависит от выбора шага|$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(1)$<br> ([[Cортировка слиянием с использованием O(1) дополнительной памяти|модифицированная реализация]])|Да|$O(n \log n)$|Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.|- align = "center"|[[Timsort| Timsort]]|$O(n)$|$O(n\log{n})$|$O(n\log{n})$|$O(n)$|Да|$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"|[[Smoothsort| Плавная сортировка <br>(Smoothsort)]]|$O(n)$|$O(n\log{n})$|$O(n\log{n})$|$O(1)$|Нет|$O(n\log{n})$|Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо.|- align = "center"|[[Терпеливая сортировка| Терпеливая сортировка <br>(Patience sorting)]]|$O(n\log{n})$|$O(n\log{n})$|$O(n\log{n})$|$O(n)$|Нет|$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>(Bucket Sort)]]|$O(n + k)$|$O(n \log_k n)$|$O(n \cdot k)$|$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)$|Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.|- align = "center"|[[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием <br>(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)$|Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток.|- align = "center"|[[PSRS-сортировка|PSRS-сортировка <br>(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}$ подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы.|} ==См. также==*[[Поисковые структуры данных]]*[[Приоритетные очереди]]*[[Поиск подстроки в строке]] ==Источники информации==*[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 Википедия {{---}} Алгоритмы сортировки]*[https://en.wikipedia.org/wiki/Sorting_algorithm Wikipedia {{---}}Sorting algorithm]*[http://habrahabr.ru/post/221807/ Хабрахабр {{---}} Бенчмарк алгоритмов сортировки]* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 174. — ISBN 978-5-8459-1794-2</wikitex>[[Категория: Дискретная математика и алгоритмы]][[Категория: Сортировки]][[Категория: Квадратичные сортировки]][[Категория: Сортировки на сравнениях]][[Категория: Многопоточные сортировки]][[Категория: Другие сортировки]]
Перенаправление на Сортировки
