Интросорт
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худшая производительность | О( п журнал п ) |
| Средняя производительность | О( п журнал п ) |
| Оптимальный | да |
Интросортировка или интроспективная сортировка — это гибридный алгоритм сортировки , который обеспечивает как высокую среднюю производительность, так и (асимптотически) оптимальную производительность в худшем случае. Он начинается с быстрой сортировки , переключается на пирамидальную сортировку , когда глубина рекурсии превышает уровень, основанный на ( логарифме ) количества сортируемых элементов, и переключается на сортировку вставками , когда количество элементов ниже некоторого порога. Он сочетает в себе хорошие стороны трех алгоритмов с практической производительностью, сравнимой с быстрой сортировкой типичных наборов данных, и временем выполнения в худшем случае O ( n log n ) из-за сортировки кучи. Поскольку три алгоритма, которые он использует, представляют собой сортировку сравнения , он также является сортировкой сравнения.
Интросорт был изобретен Дэвидом Массером в работе Массера (1997) , в которой он также представил introselect , гибридный алгоритм выбора, основанный на быстром выборе (вариант быстрой сортировки), который возвращается к медиане медиан и, таким образом, обеспечивает линейную сложность в наихудшем случае, что является оптимальным. Оба алгоритма были представлены с целью предоставить общие алгоритмы для стандартной библиотеки C++ , которые имели бы как высокую среднюю производительность, так и оптимальную производительность в худшем случае, что позволило бы ужесточить требования к производительности. [1] Introsort — это встроенный и нестабильный алгоритм .
Псевдокод
[ редактировать ]реализация пирамидальной сортировки и функции разделения типа, описанного в статье о быстрой сортировке Если доступны , интросорт можно кратко описать как
procedure sort(A : array): maxdepth ← ⌊log2(length(A))⌋ × 2 introsort(A, maxdepth)procedure introsort(A, maxdepth): n ← length(A) if n < 16: insertionsort(A) else if maxdepth = 0: heapsort(A) else: p ← partition(A) // assume this function does pivot selection, p is the final position of the pivot introsort(A[1:p-1], maxdepth - 1) introsort(A[p+1:n], maxdepth - 1)
Коэффициент 2 для максимальной глубины является произвольным; его можно настроить для практической работы. A [ i : j ] обозначает срез массива элементов от i до j, включая A [ i ] и A [ j ] . Предполагается, что индексы начинаются с 1 (первый элемент Массив А[1] ).
Анализ
[ редактировать ]При быстрой сортировке одной из важнейших операций является выбор опорной точки: элемента, вокруг которого разбит список. Самый простой алгоритм выбора опорной точки — взять первый или последний элемент списка в качестве опорной точки, что приводит к плохому поведению в случае отсортированных или почти отсортированных входных данных. Вариант Никлауса Вирта использует средний элемент для предотвращения таких случаев, вырождаясь до O( n 2 ) для надуманных последовательностей. Алгоритм выбора медианы из 3 берет медиану первого, среднего и последнего элементов списка; однако, несмотря на то, что это хорошо работает со многими реальными входными данными, все же возможно составить список убийц со средним значением 3 , который приведет к резкому замедлению быстрой сортировки, основанной на этом методе выбора сводной точки.
Массер сообщил, что для убийственной последовательности с медианой из 3 из 100 000 элементов время работы внутренней сортировки составило 1/200 от времени быстрой сортировки с медианой из 3. рассмотрел влияние на кэши отложенной мелкой сортировки Седжвика Массер также , при которой небольшие диапазоны сортируются в конце за один проход сортировки вставками . Он сообщил, что он может удвоить количество промахов в кэше, но его производительность с двусторонними очередями значительно выше, и его следует сохранить для библиотек шаблонов, отчасти потому, что в других случаях выигрыш от немедленной сортировки невелик.
Реализации
[ редактировать ]Introsort или какой-либо его вариант используется в ряде стандартных функций сортировки библиотеки , включая некоторые сортировки C++ реализации .
, выпущенной в июне 2000 г., SGI C++ В стандартной библиотеке шаблонов stl_algo.h, реализация нестабильной сортировки использует метод интросортировки Массера с глубиной рекурсии для переключения на пирамидальную сортировку, передаваемую в качестве параметра, выбор медианы из 3 и окончательный этап сортировки вставкой Кнута для разделов меньшего размера. чем 16.
Библиотека GNU Standard C++ аналогична: использует интросортировку с максимальной глубиной 2×log 2 n , за которой следует сортировка вставками для разделов меньше 16. [2]
LLVM libc++ также использует интросортировку с максимальной глубиной 2×log 2 n , однако предел размера для сортировки вставками различен для разных типов данных (30, если замены тривиальны, и 6 в противном случае). Также отдельно обрабатываются массивы размером до 5. [3] Кутенин (2022) представляет обзор некоторых изменений, внесенных LLVM, с упором на исправление квадратичности в 2022 году. [4]
Библиотека Microsoft .NET Framework классов , начиная с версии 4.5 (2012 г.), использует интросортировку вместо простой быстрой сортировки. [5]
Go использует модификацию внутренней сортировки: для срезов из 12 или менее элементов он использует сортировку вставками , а для более крупных срезов он использует быструю сортировку с обходом шаблонов и более продвинутую медиану из трех медиан для поворотного выбора. [6] До версии 1.19 использовалась сортировка оболочки для небольших срезов.
Java , начиная с версии 14 (2020 г.), использует гибридный алгоритм сортировки, который использует сортировку слиянием для высокоструктурированных массивов (массивы, состоящие из небольшого количества отсортированных подмассивов) и интросортировку в противном случае для сортировки массивов целых, длинных, плавающих и двойных чисел. . [7]
Варианты
[ редактировать ]pdqsort
[ редактировать ]Быстрая сортировка с обходом шаблонов (pdqsort) — это вариант внутренней сортировки, включающий следующие улучшения: [8]
- Медиана трех поворотов,
- Метод разделения «BlockQuicksort» для смягчения штрафов за неправильное предсказание ветвей,
- Линейная производительность по времени для определенных шаблонов ввода ( адаптивная сортировка ),
- Используйте перетасовку элементов в плохих случаях, прежде чем пытаться использовать более медленную пирамидальную сортировку.
pdqsort используется Rust , GAP , [9] и библиотека C++ Boost . [10]
Ссылки
[ редактировать ]- ^ « Общие алгоритмы », Дэвид Массер
- ^ Документация libstdc++: алгоритмы сортировки
- ^ исходный код libc++: сортировка
- ^ Кутенин Данила (20 апреля 2022 г.). «Изменение std::sort в масштабе Google и за его пределами» . Экспериментальный холод .
- ^ Метод Array.Sort (Массив)
- ^ Исходный код Go 1.20.3
- ^ Исходный код Java 14
- ^ Питерс, Орсон Р.Л. (2021). «orlp/pdqsort: быстрая сортировка с обходом шаблонов» . Гитхаб . arXiv : 2106.05123 .
- ^ "slice.sort_unstable(&mut self)" . Ржавчина .
Текущий алгоритм основан на быстрой сортировке с устранением шаблонов Орсона Питерса, которая сочетает в себе быстрый средний случай рандомизированной быстрой сортировки с быстрым наихудшим случаем пирамидальной сортировки, при этом достигая линейного времени на срезах с определенными шаблонами. Он использует некоторую рандомизацию, чтобы избежать вырожденных случаев, но с фиксированным начальным значением, чтобы всегда обеспечивать детерминированное поведение.
- ^ Ламмих, Питер (2020). Эффективная проверенная реализация Introsort и Pdqsort . IJCAR 2020: Автоматизированное мышление. Том. 12167. стр. 307–323. дои : 10.1007/978-3-030-51054-1_18 .
Общий
[ редактировать ]- Массер, Дэвид Р. (1997). «Интроспективные алгоритмы сортировки и отбора» . Программное обеспечение: практика и опыт . 27 (8): 983–993. doi : 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# . Архивировано из оригинала 7 марта 2023 года.
- Никлаус Вирт. Алгоритмы и структуры данных . Прентис-Холл, Инк., 1985. ISBN 0-13-022005-1 .