Пропорциональное расширение сортировки
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худшая производительность | О нлогн ( ) |
| Лучшая производительность | О нлогн ( ) |
| Средняя производительность | О нлогн ( ) |
| Наихудшая пространственная сложность | O(log n ) вспомогательный |
| Оптимальный | Да |
Сортировка с расширением пропорций (сокращенно PESort на основе сравнения ) — это алгоритм сортировки , который пытается улучшить производительность, особенно производительность в худшем случае , быстрой сортировки .
Базовая операция секционирования в быстрой сортировке имеет линейный шаблон доступа, который чрезвычайно эффективен в современных иерархиях памяти , но производительность алгоритма критически зависит от выбора опорного значения. Хороший сводный отчет разделит данные, подлежащие сортировке, почти на равные половины. Неправильный выбор приведет к сильно однобокому разделению, в результате чего одна часть останется почти такой же большой, как исходная задача, и приведет к возникновению O ( n 2 ) производительность.
Сортировка с расширением пропорции начинается с отсортированного префикса из k элементов, затем используется медиана этой выборки для разделения следующих pk элементов. Ограничивая соотношение размеров выборки и разделяемых данных (т. е. долю, на которую расширяется отсортированный префикс), дисбаланс ограничивается. В этом он имеет некоторое сходство с samplesort . [1]
История
[ редактировать ]Сортировка расширения пропорций была опубликована Цзин-Чао Ченом в 2001 году. [2] как улучшение его более ранней конструкции сортировки с разделением пропорций. [3] Его производительность в среднем случае, которая была измерена только экспериментально в оригинальной статье, была проанализирована Ричардом Коулом и Дэвидом К. Кандатилом в 2004 году. [4] и Чена в 2006 году, [5] и показано, что в среднем требуется log 2 n + O ( n ) сравнений. Слегка усовершенствованный вариант — сортировка по симметрии — был опубликован в 2007 году. [6]
Алгоритм
[ редактировать ]Алгоритм начинается с массива, разделенного на отсортированную часть S, с несортированной частью U. соседнюю (В исходной сортировке с расширением пропорции отсортированная часть всегда предшествовала несортированной части; симметричный вариант допускает любой порядок.) Можно начать с первого элемента как отсортированной части (всегда сортируется один элемент) или отсортировать небольшое количество элементов с использованием более простой сортировки вставками . Первоначально отсортированные элементы также могут быть взяты из всего массива для повышения производительности в случае предварительно отсортированных данных.
Далее, что наиболее важно, длина несортированной части | У | ограничено кратной p длине отсортированной части | С | . В частности, если | У | > п 2 | С | , затем рекурсивно отсортируйте S и соседний p | С | элементов U , сделайте результат ( p +1 раз длиннее исходного [а] ) новый S и повторяйте до тех пор, пока условие не будет выполнено.
Если нет ограничения на несортируемую часть ( p =∞ ), то алгоритм эквивалентен быстрой сортировке. Если несортированная часть имеет длину 1 ( почти p =0 ), то алгоритм эквивалентен двоичной сортировке вставками. Значения около p ≈16 дают наилучшую производительность в среднем случае, конкурирующую с быстрой сортировкой. [6] : 764 в то время как меньшие значения улучшают производительность в худшем случае. [б]
Элиэзер Альбачеа опубликовал аналогичный алгоритм в 1995 году под названием Leapfrogging samplesort , где размер ограничен, поэтому | У | ≤ | С |+1 , [7] [1] позже обобщено до (2 к −1)(| S |+1) . [8]
Отсортированная часть массива делится пополам (по медиане), а одна половина перемещается (путем замены ее на несортированные элементы) в дальний конец массива, таким образом мы имеем исходный частично разбитый массив вида LUR , где L — левая половина отсортированной части, U — несортированная часть ограниченной длины, а R — правая половина отсортированной части.
выполняется стандартный шаг быстрой сортировки для U разделяя его (по месту) на UL Затем и UR , . UL UL и UR меньше не сортируются, но каждый элемент или больше равен медиане, а каждый элемент или UR равен. [с] Конечный результат LU L U R R состоит из двух массивов нужного вида (отсортированная часть соседствует с несортированной частью) и сортируются рекурсивно .
При скачкообразной выборочной сортировке и исходной пропорциональной сортировке отсортированная часть всегда предшествует неотсортированной части, что достигается путем разделения перемещением R , что к LRU LUR приводит UL , а затем замены R на конец перед U , что приводит к LU L RU R . Хотя симметричная версия немного сложнее, ее преимущество заключается в том, что части L и R действуют как контрольные значения ли границы U. для циклов разделения, что устраняет необходимость проверки в цикле, достигнуты [1]
Можно применить большинство усовершенствований реализации, используемых для быстрой сортировки, включая методы обнаружения и эффективной обработки в основном отсортированных входных данных. [9] [6] В частности, подсортировки ниже определенного порога размера обычно реализуются с использованием простой сортировки вставками.
Как и в случае с быстрой сортировкой, количество рекурсивных уровней может быть ограничено до log 2 n, если сначала выполняется меньшая подсортировка, а большая реализуется как хвостовой вызов . В отличие от быстрой сортировки, количество уровней ограничено O (log n ), даже если этого не сделать. [9] : 781
Примечания
[ редактировать ]- ^ Обратите внимание, что в разных источниках используются разные соглашения для p : Чен использует соотношение неотсортированной части к отсортированной части, поэтому любое p > 0 имеет смысл, в то время как в других источниках это отношение общего размера к размеру отсортированной части, поэтому имеет смысл только p > 1 .
- ^ Алгоритм требует не более 1/log 2 (1 + 1/(2 p 2 +2 p −1)) n log 2 n сравнений. Для p ≤ 16 эта константа может быть аппроксимирована 1,37 p 2 +1,63 п -0,5 .
- ^ Предполагается сортировка по возрастанию. Сортировка по убыванию требует очевидных корректировок.
Ссылки
[ редактировать ]- ^ Jump up to: а б Альбачеа, Элиэзер А. (январь 2012 г.). «Анализ среднего случая скачкообразной выборочной сортировки» (PDF) . Филиппинские научные письма . 5 (1).
- ^ Чен, Цзин-Чао (июль 2001 г.). «Пропорциональная сортировка расширения». SIAM Journal по вычислительной технике . 31 (1): 323–330. дои : 10.1137/S0097539798342903 .
- ^ Чен, Цзин-Чао (осень 1996 г.). «Сортировка пропорциональным разделением». Северный журнал вычислительной техники . 3 (3): 271–279. дои : 10.1137/S0097539798342903 .
- ^ Коул, Ричард; Кандатил, Дэвид К. (14–17 сентября 2004 г.). Анализ среднего случая сортировок разделов (PDF) . Алгоритмы - ESA 2004: 12-й ежегодный европейский симпозиум. Берген. стр. 240–251. дои : 10.1007/978-3-540-30140-0_23 . ISBN 3-540-23025-4 .
- ^ Чен, Цзин-Чао (15 декабря 2006 г.). «Эффективная сортировка выборки и анализ среднего случая PEsort» . Теоретическая информатика . 369 (1–3): 44–66. дои : 10.1016/j.tcs.2006.07.017 .
- ^ Jump up to: а б с Чен, Цзин-Чао (11 сентября 2007 г.). «Симметричная сортировка разделов». Программное обеспечение: практика и опыт . 38 (7): 761–773. arXiv : 0706.0046 . дои : 10.1002/сп.851 . S2CID 844616 .
- ^ Альбасеа, Элиэзер А. (1995). Чехарда в выборочной сортировке . Азиатская конференция по информатике. дои : 10.1007/3-540-60688-2_30 .
- ^ Альбасеа, Элиэзер А. (29 января 2018 г.). «Обобщенная скачкообразная выборочная сортировка: класс O ( n log 2 2 n ) Алгоритмы сортировки по сложности в наихудшем случае и O ( n log n ) по сложности в среднем». arXiv : 1801.09431 [ cs.DS ].
- ^ Jump up to: а б Чен, Цзин-Чао (10 июля 2004 г.). «Создание новой функции сортировки для библиотеки C». Программное обеспечение: практика и опыт . 34 (8): 777–795. дои : 10.1002/сп.593 . S2CID 8193225 .