Сортировки - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:33:55Z

rollbackEdits.php mass rollback

88.208.225.209 в 04:17, 1 сентября 2022

2022-09-01T04:17:45Z

109.254.254.86: /* Сравнение сортировок */

2018-05-21T18:45:43Z

‎Сравнение сортировок

81.163.153.202: /* Сравнение сортировок */

2018-05-09T15:30:25Z

‎Сравнение сортировок

Shersh: Новая страница: « ''Сортировкой'' (англ. ''sorting'') называется процесс упорядочивания множества объектов ...»

2015-06-04T07:47:28Z

Новая страница: «<wikitex> ''Сортировкой'' (англ. ''sorting'') называется процесс упорядочивания множества объектов ...»

Новая страница

<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"
|[[Сортировка пузырьком| Сортировка пузырьком (Bubble Sort)]]
|$O(n)$
|$O(n^2)$
|$O(n^2)$
|$O(1)$
|Да
|$O(n^2)$
|Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
|- align = "center"
|[[Сортировка вставками| Сортировка вставками (Insertion Sort)]]
|$O(n)$
|$O(n^2)$
|$O(n^2)$
|$O(1)$
|Да
|$O(n^2)$
|На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
|- align = "center"
|[[Сортировка Шелла| Сортировка Шелла (Shellsort)]]
|$O(n\log^2{n})$
|Зависит от выбора шага
|$O(n^2)$
|$O(1)$
|Нет
|$O(n^2)$
|Является модификацией сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах.
|- align = "center"
|[[Сортировка выбором| Сортировка выбором (Selection Sort)]]
|$O(n^2)$
|$O(n^2)$
|$O(n^2)$
|$O(1)$
|Нет
|$O(n)$
|На $i$-ом шаге алгоритма находим минимальный среди последних $n - i + 1$, и меняем его местами с $i$-ым элементом в массиве.
|- align = "center"
|[[Быстрая сортировка|Быстрая сортировка (Quick Sort)]]
|$O(n \log n)$
|$O(n \log n)$
|$O(n^2)$ (маловероятно)
|$O(\log n)$ (стек вызовов)
|Нет
|$O(n \log n)$
|Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного (одна — все элементы, меньшие опорного элемента, вторая — большие), и в сортировке полученных частей рекурсивным вызовом себя от них.
|- align = "center"
|[[Сортировка слиянием|Сортировка слиянием (Merge Sort)]]
|$O(n \log n)$
|$O(n \log n)$
|$O(n \log n)$
|$O(n)$ (обычная реализация) $O(1)$ ([[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"
|[[Сортировка кучей|Сортировка кучей (Heap Sort)]]
|$O(n \log n)$
|$O(n \log n)$
|$O(n \log n)$
|$O(1)$
|Нет
|$O(n \log n)$
|Строим из массива кучу, по очереди извлекаем минимум кучи.
|- align = "center"
|[[Smoothsort| Плавная сортировка (Smoothsort)]]
|$O(n)$
|$O(n\log{n})$
|$O(n\log{n})$
|$O(1)$
|Нет
|$O(n\log{n})$
|Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо.
|- align = "center"
|[[Терпеливая сортировка| Терпеливая сортировка (Patience sorting)]]
|$O(n\log{n})$
|$O(n\log{n})$
|$O(n\log{n})$
|$O(n)$
|Нет
|$O(n\log{n})$
|Раскидываем элементы массива по стопкам, после чего строим двоичную кучу из стопок. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива.
|- align = "center"
|[[Дерево поиска, наивная реализация|Сортировка с помощью бинарного дерева (Tree Sort)]]
|$O(n)$
|$O(n \log n)$
|$O(n \log n)$
|$O(n)$
|Да
|$O(n)$
|Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания.
|- align = "center"
|[[Карманная сортировка|Карманная сортировка (Bucket Sort)]]
|$O(n + k)$
|$O(n \log_k n)$
|$O(n \cdot k)$
|$O(n)$
|Да
| -
|Распределяем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
|- align = "center"
|[[Цифровая сортировка|Цифровая сортировка (Radix Sort)]]
|$O(n \lg n)$
|$O(n \lg n)$
|$O(n \lg n)$
|$O(n)$
|Да
| -
|Сортировка объектов равной длины, имеющих "разряды". обычно это строки или целые числа. Алгоритм состоит в том, чтобы отсортировать объекты по разрядам, начиная от младших к старшим.
|- align = "center"
|[[Сортировка подсчетом|Сортировка подсчетом (Counting Sort)]]
|$O(n)$
|$O(n + k)$
|$O(k)$
|$O(k)$
|Да
|$O(n + k)$
|Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона $k$, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа.
|- align = "center"
|[[Сортировка Хэна (или Хана?)|Сортировка Хэна (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"
|[[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием (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-сортировка (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>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Квадратичные сортировки]]
[[Категория: Сортировки на сравнениях]]
[[Категория: Многопоточные сортировки]]
[[Категория: Другие сортировки]]

← Предыдущая		Версия 16:33, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	<wikitex>		<wikitex>
	''Сортировкой'' (англ. ''sorting'') называется процесс упорядочивания множества объектов по какому-либо признаку.		''Сортировкой'' (англ. ''sorting'') называется процесс упорядочивания множества объектов по какому-либо признаку.

← Предыдущая		Версия 04:17, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	<wikitex>		<wikitex>
	''Сортировкой'' (англ. ''sorting'') называется процесс упорядочивания множества объектов по какому-либо признаку.		''Сортировкой'' (англ. ''sorting'') называется процесс упорядочивания множества объектов по какому-либо признаку.

@@ Строка 170: / Строка 170: @@
 |Да
 |$O(n \log \log n)$
-|Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.
+|Очень сложная сортировка, основанная на принадлежности ключей к целым числам. Использует экспоненциальное поисковое дерево Андерсона.
 |- align = "center"
 |[[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием <br>(Multithreaded merge sort)]]

@@ Строка 89: / Строка 89: @@
 |Да
 |$O(n \log n)$
-|Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.
+|Алгоритм состоит в разделении массива пополам, сортировке половин и их слиянии.
 |- align = "center"
 |[[Timsort| Timsort]]