Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [ 70 ] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

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

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

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

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

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

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

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

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



47 ДеВствие-

.47 ynetmmsi

>

увЕлшаие.!

>

обмен

>•

вбит

увелтение l>

уменьшЕнив j

\ >

пймен

Ota, уменьшение

Рис. 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 имеет входной параметр М, который определяет, насколько короткой должна быть подпосле-



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [ 70 ] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.001