5.1. Сортировка

Сортировка стала важным предметом вычислительной математики в основном потому/ что она отнимает значительную часть времени работы ЭВМ. Осознание того, что 25% всего времени вычислений расходуется на сортировку данных, придает особое значение эффективным алгоритмам сортировки.

К сожалению, нет алгоритма сортировки, который был бы наилучшим в любом случае. Трудно даже решить, какой алгоритм будет лучшим в данной ситуации, так как эффективность алгоритма сортировки может зависеть от множества факторов, например от того, (1) каково число сортируемых элементов; (2) все ли элементы могут быть помещены в доступную оперативную память; (3) до какой степени элементы уже отсортированы; (4) каковы диапазон и распределение значений сортируемых элементов; (5) записаны ли элементы на диске, магнитной ленте или перфокартах; (6) каковы длина, сложность и требования к памяти алгоритма сортировки; (7) предполагается ли, что элементы будут периодически исключаться или добавляться; (8) можно ли элементы сравнивать параллельно.

Очевидно, что с отсортированными данными работать легче, чем с произвольно расположенными. Когда элементы отсортированы, их проще найти (как в телефонном справочнике), обновить, исключить, включить и слить воедино. На отсортированных данных легче определить, имеются ли пропущенные элементы (как в колоде игральных карт), и удостовериться, что все элементы были проверены. Легче также найти общие элементы двух множеств, если они оба отсортированы. Сортировка применяется при трансляции программ, когда составляются таблицы символов; она также является важным средством для ускорения работы практически любого алгоритма, в котором часто нужно обращаться к определенным элементам.

Обычно сортируемые элементы представляют собой записи данных определенного вида. Каждая запись имеет поле ключа и поле информации. Поле ключа содержит положительное число, обычно целое, и записи упорядочиваются по значению ключа.

В этом разделе мы рассматриваем два из наиболее эффективных алгоритмов сортировки, быстрой сортировки и сортировки пирамидой (QUICKSORT и HEAPSORT), и устанавливаем теоретически неулуч-шаемые границы для всех алгоритмов сортировки с помощью сравнений. В других разделах обсуждаются еще два алгоритма сортировки: сортировка простыми включениями (SIS) (разд. 2.4) и параллельная сортировка (PARSORT) (разд. 5.5).

QUICKSORT: Алгоритм сортировки со средним временем работы О {NXnN)

Основная причина медленной работы алгоритма SIS заключается в том, что все сравнения и обмены между ключами в последовательности Gj, Ga, . - ., происходят ДЛЯ пар ИЗ соседних элементов. При

Рис. 5.1.1. Начальные шаги алгоритма QUICKSORT при сортировке последовательности целых чисел,

таком способе требуется относительно большое время, чтобы поставить ключ, находящийся не на месте, в нужную позицию в сортируемой последовательности. Естественно попытаться ускорить этот процесс, сравнивая пары элементов, находящихся далеко друг от друга в последовательности.

К. Хоор изобрел и весьма эффективно применил эту идею (алгоритм QUICKSORT), сократив среднее время работы алгоритма SIS от порядка 0{N) до порядка 0{N In N). Поясним этот алгоритм следующим примером.

Предположим, что мы хотим отсортировать последовательность чисел из первой строки на рис. 5.1.1. Начнем с предположения, что первый ключ в этой последовательности (38) служит хорошей аппроксимацией ключа, который в конечном счете появится в середине отсортированной последовательности. Используем это значение в качестве ведущего элемента, относительно которого ключи могут меняться местами, и продолжим следующим образом. Устанавливаем два указателя / и J, из которых / начинает отсчет слева (/=1), а J - справа в последовательности {J=N). Сравниваем o; и Uj. Если OjUj, то устанавливаем J-«-J-1 и проводим следующее сравнение. Продолжаем ужньшать J до тех пор, пока не достигнем a{>aj. Тогда поменяем местами (рис. 5.1.1, строка 5, обмен ключей

38 и 04), устанавливаем /-/+1 и продолжаем увеличивать I до тех пор, пока не получим a,>aj. После следующего обмена (строка 10, 79<->38) снова уменьшаем J. Чередуя уменьшение / и увеличение /, продолжаем этот процесс с обоих концов последовательности к «середине» до тех пор, пока не получим /=J.

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

Ту же процедуру можно применить к левой и правой подпоследовательностям для окончательной сортировки всей последовательности. Последняя строка (с номером 22) рис. 5.1.1 показывает, что когда будет получено I=J, то 1=1. После этого процедура снова применяется к подпоследовательностям (1,6) и (8,16).

Рекурсивный характер алгоритма наводит на мысль, что следует значения индексов крайних элементов большей из двух неотсортированных подпоследовательностей (8,16) поместить на стек и затем перейти к сортировке меньшей подпоследовательности (1,6).

В строке 4 на рис. 5.1.2 число 04 перешло в позицию 2 и сортировке подлежат подпоследовательности (1,1) и (3,6). Так как (1,1) уже отсортирована (число 02), сортируем (3,6), что в свою очередь ведет к строке 6, в которой подлежат сортировке (3,4) и (6,6). В строке 7 подпоследовательность (1,6) отсортирована. Теперь извлекаем (8,16) из стека и начинаем сортировку этой подпоследовательности. В строке 13 находятся подпоследовательности (8,11) и (13,16), которые надо отсортировать. Помещаем (13, 16) на стек, сортируем (8,11) и т. д. В строке 20 последовательность целиком отсортирована.

Прежде чем описать алгоритм QUICKSORT формально, нужно точно показать, как он работает. Мы пользуемся стеком [LEFT(/(), RIGHT (Д)] для запоминания индексов крайних левого и правого элементов еще не отсортированных подпоследовательностей. Так как короткие подпоследовательности быстрее сортируются при помощи обычного алгоритма, алгоритм QUICKSORT имеет входной параметр М, который определяет, насколько короткой должна быть подпосле-