Файл: Алгоритмы сортировки данных (Теоретические основы).pdf

Таблица 2

Экспериментальное среднее время сорти­ровки

Время Tc работы алгоритма C хорошо аппроксимируется выражением k_cn log₂n, где k_c — коэффициент, зависящий от типа компьютера. Обозначим через g отношение T_p/T_c, где Tp — время пирамидальной сортировки. Значение g возрастает приблизительно от 1,6 до 4,5 для n = 10⁸. Это свидетельствует о том, что время T_p растет быстрее, чем число операций, которое согласно теории определяется выражением k_pn log₂n, где k_p — коэффициент, т.е. сказывается увеличение удельного времени доступа к данным. Значение g и темп его изменения зависят от размера записи R и типа компьютера, точнее, от параметров иерархической структуры его памяти. В любом случае существует область больших значений n, где время T_p в несколько раз больше T_c. Это утверждение справедливо для всех разновидностей пирамидальной сортировки.

Чтобы сравнить метод слияния и метод QuickSort, рассмотрим последние результаты их оптимизации. Под оптимизацией сортировки [4] обычно понимается приближение среднего числа сравнений ключей к теоретико-информационному пределу log₂(n!). В [7] для сортировки был выведен нижний предел n + H_n – 2 среднего числа транспозиций записей — перемещений записей или обмена их местами (H_n — гармоническое число). Сокращение числа транспозиций также будем называть оптимизацией. Под всесторонней оптимизацией будем понимать умень­шение среднего числа как основных действий, так и массовых вспомогательных действий, для которых может быть известен теоретический минимум.

Метод QuickSort реализует разделение массива на внешне упорядоченные части (ВУЧ). Каж­дая запись может изменять положение лишь в рамках ВУЧ. Разделение можно изобразить дере­вом ВУЧ, узлы которого представляют ВУЧ, так как весь массив и каждая ВУЧ, содержащая более одной записи, разделяются на меньшие ВУЧ. В итоге, когда каждая ВУЧ содержит един­ственную запись, массив становится упорядоченным.

Исследованию и усовершенствованию метода QuickSort посвящено немало работ, остано­вимся на последних [2; 8; 12; 13]. В них по-разному реализуются две главные идеи:

а) отказ от разделения многочисленных малых ВУЧ (ведет к сильному сокращению множества вспомогательных действий);

б) улучшение формы дерева ВУЧ, выражающееся в уменьшении средней глубины листьев дерева.

Упорядочение малых ВУЧ выполняют алгоритмом вставки или иным алгоритмом. Длина внешнего пути [12] дерева ВУЧ определяет число сравнений ключей. В алгоритме, описанном в [12] и названном нами алгоритмом B, ВУЧ, как правило, разделяется на пять частей, дерево ВУЧ имеет меньшую длину внешнего пути, чем в алгоритме A, однако действия в алгоритме B сложнее, так как при разделении ВУЧ используются два опорных элемента. Средний выигрыш в числе сравнений приблизительно равен

---

2n ln n – (1,9n ln n – 2,46n) = 0,1n ln n + 2,46n

(для алгоритма A среднее число сравнений ключей равно 2n lnn). В [13] было показано, как этот выигрыш увеличить до значения 0,2n ln n (приблизительно). В алгоритме B среднее число транспозиций, примерно равное 0,6n ln n, существенно больше, чем в алгоритме A. Поэтому оптимизацию нельзя считать сбалансированной: уменьшение среднего числа сравнений клю­чей сопровождается ростом числа транспозиций сортируемых записей.

Алгоритм C предложен в МЭИ [2]. В нем упорядочение малых ВУЧ проводится специаль­ными алгоритмами, названными решетками, а форма дерева ВУЧ улучшается благодаря равно­мерному разделению ВУЧ, что достигается использованием в качестве опорного значения медианы пяти записей, взятых из разделяемой ВУЧ. Идея не нова, медиана трех элементов используется в известных реализациях QuickSort. Получение медианы — это дополнительные издержки времени, лишние операции. Важно их сократить и хотя бы частично совместить с операциями по разделению ВУЧ. Это было достигнуто при построении алгоритма C примени­тельно к медианам пяти элементов ВУЧ. Согласно [2] в алгоритме C среднее число K сравне­ний ключей с ростом n приближается к значению 1,62n ln n – 1,35n, т.е. по сравнению с алго­ритмом A выигрыш составляет примерно 0,38n ln n + 1,35n. Среднее число транспозиций составляет не более 0,5n ln n, и реализованы они как перемещения записей, тогда как в алго­ритме B используются более сложные операции — обмены записей местами. Поэтому время сортировки алгоритмом C при n = 10⁶ существенно меньше времени алгоритма B (рис. 5).

Рис.5. Сравнение времени сортировки алгоритмов В и С

Итак, по характеристикам алгоритм C лучше алгоритмов A и B. Однако достигнутые резуль­таты оптимизации метода QuickSort далеки от идеала: значение K заметно больше значения log2(n!) ≈ 1,44n (ln n – 1). Среднее число транспозиций записей относительно мало, но сущест­венно больше нижнего предела n + Hn – 2. Дальнейшее сокращение числа основных действий метода QuickSort, по-видимому, не имеет хорошей перспективы. Найдем альтернативу лучшим реализациям метода QuickSort.

Метод слияния обычно используется для сортировки файлов записей и редко применяется для сортировки массивов, так как требует значительной дополнительной памяти и выполняет больше транспозиций, чем метод QuickSort. Сильными сторонами слияния являются стабиль­ность времени сортировки и близость среднего числа сравнений к теоретическому минимуму. Так называемое t-арное слияние выполняет слияния t упорядоченных частей массива вплоть до получения единой части, т.е. упорядоченного массива. На рис. 6 для t = 3 показана схема слия­ния 30 упорядоченных частей (ими могут быть отдельные записи). На каждой фазе слияния (они обозначены штриховыми линиями) все сортируемые записи перемещаются в памяти. Число перемещений отдельно взятой записи равно числу фаз L = ┌logt(n/m)┐, где m — макси­мальное число записей в одной исходной части. При t = ┌n/m┐ каждая запись перемещается однажды. Итак, возможно рекордно малое число P перемещений записей. В дальнейшем будем исследовать процесс t-арного слияния при больших значениях t.

---

Сокращая числа перемещений записей P, важно сохранить указанные выше преимущества слияния. Массовая операция, во время которой сравниваются ключи, — это выбор очередной наименьшей записи из остающихся записей. Простой перебор при сравнении записей неприем­лем, он сильно снижает производительность метода при больших t. Найдем лучший вариант.

Обозначим X вычислительную сложность одной фазы слияния и выясним, каким должна быть X, чтобы получить приемлемую оценку сложности O(n log₂n) всего процесса слияния.

Выбирая эту оценку как ориентир, учитываем указанный выше теоретико-информационный предел и тот факт, что сравнения ключей являются самой массовой операцией при сортировке.

Возьмем m = 1 и запишем равенство X ┌logt n┐ = O(n log₂ n). Из него следует X = O(n log₂n/log_tn) = O(n log₂t), а сложность выбора одной записи, включая ее пересылку, получает оценку O(log₂t). Такую оценку имеет выбор среди t ключей экстремального ключа, реализуемый в простой пирамиде [4]. Асимптотическая оценка O(log₂t) скрывает коэффициент при величине log₂t, но если он будет велик, нельзя ожидать преимущества метода слияния по сравнению с методом QuickSort.

Рис.6. Реализация метода многопутевого слияния

Авторами был выполнен анализ использования (в качестве схемы выбора) простой и слабой [9] бинарных пирамид, 3-арной, 4-арной и 5-арной пирамид. Прежде всего определялся коэф­фициент k в формуле klog₂t числа сравнений при выборе записи. Наименьшее значение k

имеет слабая пирамида, для нее k ~ 1. Поскольку в ней выполняются и пересылки, и много­численные вспомогательные операции, в целях сравнения проверялись улучшенные реализа­ции прочих пирамид. По затратам времени выбора лучшими оказались слабая пирамида и про­стая бинарная пирамида, в которой для уменьшения числа сравнений использована идея Р. Флойда [10].

Время тратится и на построение пирамид, выполняемое примерно столько же раз, сколько узлов в схеме слияния (рис. 6), исключая листья дерева. Время построения 4-арной и 5-арной пирамид наименьшее, но эти пирамиды проигрывают бинарным пирамидам по общим затра­там времени.

Таким образом, продолжена оптимизация t-арного слияния, начало которой было положено в [3]. В новых реализациях t-арного слияния помимо слабой пирамиды впервые используется схема выбора записей по принципу турнира.

Следующий шаг оптимизации — это выбор размера m исходных упорядоченных частей и способа их получения. Рассмотрим вариант, когда, неупорядоченный массив большой: пусть n = 10⁷, m=1. Если t = 100, то потребуется упорядочить на 1-й фазе слияния 10⁷/100 = 10⁵ час­тей и для этого 10⁵ раз построить схему выбора — пирамиду или турнирную схему, затратив больше времени. Для исключения такого рода фазы слияния описываемым ниже способом упо­рядочим части массива размером t (в последней части записей может быть меньше чем t). Для каждой части, сравнивая ключи, будем сортировать номера записей. Используя полученную последовательность номеров, переместим каждую запись (всего n пересылок записей, как и на исключенной фазе).

---

Были исследованы восемь способов упорядочения исходных частей. Алгоритмы естествен­ного и простого бинарного слияния [4] оказались наилучшими по времени сортировки исход­ных частей. Для сокращения числа машинных операций была проведена оптимизация их про­грамм. Для R = 48 среднее время сортировки одной части в условных единицах приведено в табл. 2. Оно зависит от размера записи R, но остается меньшим у алгоритмов слияния в рабо­чей области значений t. Например, для t = 1000 затрачивается примерно в 1,35 раза меньше вре­мени, если взамен первой фазы применяется простое бинарное слияние.

Заключение

Как можно было убедиться, практическая польза от описанных алгоритмов есть, со своей задачей они с переменным успехом справляются. Абсолютным лидером стал Timsort — дающий заметное ускорение при увеличении степени упорядоченности данных и работающий на уровне Quicksort в обычных случах. Не зря он признан и встроен в Python, OpenJDK и Android JDK.

Про Smoothsort в сети довольно немного информации (по сравнению с остальными алгоритмами) и не спроста: из-за сложности идеи и спорной производительности он скорее является алгоритмическим изыском, нежели применимым методом. Я нашел всего лишь одно реальное применение этого алгоритма — в библиотеке sofia-sip, предназначенной для построения IM- и VoIP-приложений.

Появление Shellsort в данном тесте является довольно спорным моментом, потому что его асимптотическая сложность несколько больше, чем у остальных двух алгоритмов. Но у него есть два больших преимущества: простота идеи и алгоритма, которая позволяет почти всегда обходить Smoothsort по скорости работы и простота реализации — работающий код занимает всего пару десятков строк, в то время как хорошие реализации Timsort и Smoothsort требуют более сотни строк.

Список использованных источников

1. Зубов В.С., Шевченко И.В. Об ускорении «быстрой сортировки» // Труды XXI международной НТК «Информационные средства и технологии». Т. 3. М.: Издательский дом МЭИ, 2013. С. 122—129.
2. Зубов В.С., Шевченко И.В. Новый алгоритм сортировки по методу многопутевого слияния // Вестник МЭИ. 2014. № 6. С. 49—56.
3. Кнут Д.Э. Искусство программирования. Т. 1. Основные алгоритмы: пер. с англ.; 3-е изд. — М.: Издательский дом «Вильямс», 2014. С. 449—451.
4. Кнут Д.Э. Искусство программирования. Т. 3. Сортировка и поиск: пер. с англ.; 2-е изд. — М.: Издательский дом «Вильямс», 2014. – 832 с.
5. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ— 2-е изд. — М.: Вильямс, 2016. — С. 1296
6. Седжвик Р. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск— СПб.: ДиаСофтЮП, 2003. — С. 672.
7. Шевченко И.В. Композиции быстрых алгоритмов сортировки. Электронный журнал «Вычислитель­ные сети. Теория и практика» / Network-Journal. Theory and practice BC/NW. 2005. № 1 (6). http://network-journal.mpei.ac.ru/cgi-bit/main.pl?l=ru&n=6&pa=3&ar=4
8. Aumüller M., Dietzfelbinger M. Optimal Partitioning for Dual Pivot Quicksort. Automata, Languages and Programming // Lecture Notes in Computer Science. 2013. Vol. 7965. P. 33—44.
9. Dutton R.D. Weak-heap Sort // BIT. 2013. Vol. 33. P. 372—381.
10. Floyd R.W. Algorithm 245: treesort 3 // Comm. ACM. Vol. 7. No 12. P. 701.
11. Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2015. — 336 с.
12. Yaroslavskiy V. Dual pivot quicksort. 2014. http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
13. Wild S., Nebel M.E. Average case analisys of Java 7’s dual pivot quicksort. Algorithms — ESA 2012 // Lecture Notes in Computer Science. 2012. Vol. 7501. P. 825—836.

---