Главная Промышленная автоматика.

можные исходные последовательности ключей равновероятны, составляет примерно Для доказательства этого утверждения рассмотрим два списка ключей, которые обратны друг другу: Li = ki, йг. и L2 = *п> йв 1> •••> fej. Переставляются ключи

й( и kj из одного списка, если они расположены в "неправильном" порядке, т.е. нарушают отношение линейного порядка, заданного на множестве значений ключей. Такая перестановка для ключей й( и kj выполняется только один раз, так как они расположены неправильно или только в списке Li, или только в списке L2, но не в обоих сразу. Поэтому обшее число перестановок в алгоритме "пузырька", примененном к спискам Li и Lj, равно числу пар элементов, т.е. числу сочетаний из и по 2:

С* = п(п - 1) / 2 . Следовательно, среднее число перестановок для списков Li и L2 равно п(п - 1)/4 или примерно Поскольку для любого упорядочивания ключей сушествует обратное к нему, как в случае списков Li и L2, то отсюда вытекает, что среднее число перестановок для любого списка таюке равно примерно

Число перестановок для сортировки вставками в среднем точно такое же, как и для алгоритма "пузырька". Для доказательства этого достаточно применить тот же самый аргумент: каждая пара элементов подвергается перестановке или в самом упорядочиваемом списке I и в обратном к нему, но никогда в обоих.

Если на выполнение процедуры swap необходимы большие вьиислительные или временные ресурсы, то легко увидеть, что в этом случае сортировка посредством выбора более предпочтительна, нежели другие рассмотренные методы сортировки. В самом деле, в алгоритме этого метода (листинг 8.4) процедура swap выполняется вне внутреннего цикла, поэтому она выполняется точно п - 1 раз для массива длиной п. Другими словами, в этом алгоритме осушествляется 0(п) перестановок в отличие от двух других алгоритмов, где количество таких перестановок имеет порядок 0(п). Причина этого понятна: в методе сортировки посредством выбора элементы "перескакивают" через большой ряд других элементов, вместо того чтобы последовательно меняться с ними местами, как это делается в алгоритме "пузырька" и алгоритме сортировки вставками.

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

Ограниченность простых схем сортировки

Еше раз напомним, что каждый из рассмотренных в этом разделе алгоритмов выполняется за время порядка 0{п) как в среднем, так и в самом худшем случае. Поэтому для больших п эти алгоритмы заведомо проигрывают алгоритмам с временем выполнения 0(п logn), которые будут описаны в следующем разделе. Значение п, начиная с которого быстрые алгоритмы сортировки становятся предпочтительнее простых методов сортировки, зависит от различных факторов, таких как качество объектного кода программы, генерируемого компилятором, компьютера, на котором выполняется программа сортировки, или от размера записей. Определить такое критическое значение п для конкретных задач и вычислительного окрркения (компилятор, компьютер и т.п.) можно после экспериментов с профайлером и на основании выдаваемых им результатов. Практический опыт учит, что при га, не превышающем 100, на время вьшолнения программы влияет множество факторов, которые с трудом поддаются регистрации и поэтому не учтены в анализе, проведенном в этом разделе. Для небольших значений п рекомендуем применять простой в реализации алгоритм сортировки Шелла (Shell), который имеет временную слокность 0(ге). Этот алгоритм, описанный в упражнении 8.3, является обобщением алгоритма "пузырька".

Профайлер - это подпрограмма протоколирования, позволяющая оценить время выполнения отдельных функций и операторов программы. - Прим. ред.



8.3. Быстрая сортировка

Первый алгоритм с временем выполнения 0(ге logre), который мы рассмотрим далее, является, по-видимому, самым эффективным методом внутренней сортировки и поэтому имеет название "быстрая сортировка". В этом алгоритме для сортировки элементов массива А[п] из этих элементов выбирается некоторое значение

ключа V в качестве опорного элемента, относительно которого переупорядочиваются элементы массива. Желательно выбрать опорный элемент близким к значению медианы распределения значений ключей так, чтобы опорный элемент разбивал множество значений ключей на две примерно равные части. Далее элементы массива переставляются так, чтобы для некоторого индекса / все переставленные элементы

А[]] имели значения ключей, меньшие чем v, а все элементы Д[;+ 1], А[п] - значения ключей, большие или равные v. Затем процедура быстрой сортировки рекурсивно применяется к множествам элементов А[1], A[j} и A[j + 1],

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

Пример 8.4. На рис. 8.9 показаны последовательные шаги выполнения алгоритма быстрой сортировки, выполняемые над последовательностью целых чисел 3, 1, 4, 1, 5, 9, 2, 6, 5, 3. На каждом этапе значение v выбирается как наибольшее значение из двух самых левых различных элементов-чисел. Сортировка завершается, когда отдельные частичные подмножества, на которые разбивается исходный массив в процессе рекурсивных вызовов процедуры, будут содержать одинаковые ключи. На рис. 8.9 каждый этап показан в виде двух шагов: сначала для каждого частичного подмножества выбирается свое значение v, затем элементы в этих подмножествах переставляются в соответствии с выбранным значением v, тем самым опять разбиваются еше на два подмножества, к которым снова рекурсивно применяется процедура сортировки.D

Теперь начнем разрабатывать рекурсивную процедуру quicksort(i.j), которая будет работать с элементами массива А, определенным вне этой процедуры. Процедура quicksort(i, J) должна упорядочить элементы Л[[], Д[;]. Предварительный набросок процедуры показан в листинге 8.5. Отметим, что если все элементы A[i]> имеют одинаковые ключи, над ними не производятся никакие действия.

Листинг 8.5. Процедура быстрой сортировки

(1) if рмеют не менее двух различных ключей then begin

(2) пусть v - наибольший из первых двух найденных различных

ключей ,-

(3) переставляются элементы А[i], A[j] так, чтобы

для некоторого к, l+l<fc<j, A[i], А[к-1\ имели ключи,

меньшие, чем v, а А[к], A[j] - большие или равные v;

(4) quicksort(i, к-1) ; (.5). quicksort (к,

Напишем функцию findpivot (нахождение опорного элемента), реализующую проверку в строке (1) листинга 8.5, т.е. проверяющую, все ли элементы A[i], A[j] одинаковы. Если функция findpivot не находит различных ключей, то возвращает

Строго говоря, описываемый далее алгоритм быстрой сортировки имеет время выполнения 0(л logn) только в среднем, в самом худшем случае его временная сложность имеет порядок О(л).

Интересно отметить, что название quicksort (быстрая сортировка) этому алгоритму дал его автор Хоар (Ноаге С. А. R.) в работе [49] (интересная статья, в которой исчерпывающе описан данный алгоритм), и в дальнейшем никто не оспаривал это название. - Прим. ред.



значение 0. В противном случае она возвращает индекс наибольшего из первых двух различных ключей. Этот наибольший ключ становится опорным элементом. Код функции flndpivot приведен в листинге 8.6.

Этап 1

Этап 2

3 1 6 1 5

3 I 9

Этап 3

готово

готово

v = i

Этап 4 (

готово готово V = 6

готово

Этап 5

готово готово

Рис. 8.1. Этапы быстрой сортировки

Листинг 8.6. Функция findpivot

function findpivot ( i, j: integer ): Integer; var

firstkey. keytype;

{ примет значение первого найденного ключа, т.е. Л[i].key ) к: integer; { текущий индекс при поиске различных ключей) begin

firstkey: = A[i] .key;

for k:= 1+ 1 toj do { просмотр ключей }

if A[k] .key > firstkey then { выбор наибольшего ключа)





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 118 119 120 121 122 123

0.0019