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

Реализация алгоритма быстрой сортировки

Алгоритм быстрой сортировки можно реализовать не только посредством процедура quicksort так, чтобы среднее время выполнения равнялось 0(п logn). Мокно создать другие процедуры, реализующие этот алгоритм, которые будут иметь тот же порядок 0(п logn) времени выполнения в среднем, но за счет меньшей константы пропорциональности в этой оценке будут работать несколько быстрее (напомним, что порядок времени выполнения, такой как 0(п logn), определяется с точностью до константы пропорциональности). Эту константу мокно уменьшить, если выбирать опорное значение таким, чтобы оно разбивало рассматриваемое в данный момент подмножество элементов на две примерно равные части. Если всегда такие подмножества разбиваются точно пополам, тогда каждый сортируемый элемент имеет глубину точно logn в дереве, аналогичном изображению из рис. 8.1 (вспомните полные двоичные деревья из главы 5). Для сравнения: средняя глубина элементов в процедуре quicksort (листинг 8.8) составляет 1.4 logn. Так что мокно надеяться, что при "правильном" выборе опорного значения выполнение алгоритма ускорится.

Например, можно с помощью датчика случайных чисел выбрать три элемента из подмножества и средний (по величине) из них назначить опорным значением. Мокно также, задав некоторое число к, выбрать случайным образом (например, опять с помощью датчика случайных чисел) к элементов из подмножества, упорядочить их процедурой quicksort или посредством какой-либо простой сортировки из раздела 8.2 и в качестве опорного значения взять медиану (т.е. (к + 1)/2-й элемент) этих к элементов. Заметим в скобках, что интересной задачей является определение наилучшего значения к как функции от количества элементов в подмножестве, подлежащем сортировке. Если к очень мало, то среднее время будет близко к тому, как если бы выбирался только один элемент. Если же к очень велико, то рке необходимо учитывать время наховдения медианы среди к элементов.

Другие реализации алгоритма быстрой сортировки можно получить в зависимости от того, что мы делаем в случае, когда получаются малые подмножества. Напомним, что в разделе 8.2 говорилось о том, что при малых и алгоритмы с временем выполнения О(п) работают быстрее, чем алгоритмы с временем выполнения порядка O(nlogn). Однако понятие "малости" и зависит от многих факторов, таких как организация рекурсивных вызовов, машинная архитектура и компилятор языка программирования, на котором написана процедура сортировки. В книге [65] предлагается значение 9 в качестве порогового значения размера подмножества, ниже которого целесообразно применять простые методы сортировки.

Сушествует еше один метод "ускорения" быстрой сортировки за счет увеличения используемого пространства памяти компьютера. Отметим, что этот метод применим к любым алгоритмам сортировки. Если есть достаточный объем свободной памяти, то мокно создать массив указателей на записи массива А. Затем следует организовать процедуру сравнения ключей записей посредством этих указателей. В этом случае нет необходимости в физическом перемещении записей, достаточно перемешать указатели, что значительно быстрее перемещения непосредственно записей, особенно когда они большие (состоят из многих полей). В конце выполнения процедуры сортировки указатели будут отсортированы слева направо, указывая на записи в нужном порядке. Затем сравнительно просто мокно переставить сами записи в правильном порядке.

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

* Поскольку в данном случае необходимо только значение медианы, то вместо упорядочивания всего списка из к элементов рациональнее применить один из быстрьг>£ алгоритмов нахождения значения медианы, описанньж в разделе 8.7.



8.4. Пирамидальная сортировка

в этом разделе мы рассмотрим алгоритм сортировки, называемой пирамидальной, его время выполнения в худшем случае такое, как и в среднем, и имеет порядок 0(п logn). Этот алгоритм можно записать в абстрактной (обобшенной) форме, используя операторы множеств INSERT, DELETE, EMPTY и MIN, введенные в главах 4 и 5. Обозначим через L список элементов, поддежаших сортировке, а S - множество элементов типа recordtype (тип записи), которое будет использоваться для хранения сортируемых элементов. Оператор MIN применяется к ключевому полю записей, т.е. MIN(S) возврашает запись из множества S с минимальным значением ключа. В листинге 8.9 показан абстрактный алгоритм сортировки, который мы далее преобразуем в алгоритм пирамидальной сортировки.

Листинг 8.9. Абстрактный алгоритм сортировки

(1) for X е L do

(2) INSERT (X, s) ;

(3) while not EMPTY(S) do begin

(4) y:= MIN(S> ;

(5) writelniy) ;

(6) DELETE (y, S) end

В главах 4 и 5 мы показали различные структуры данных, такие как 2-3 деревья, помогаюшие реализовать эти операторы множеств с временем выполнения O(logn). Если список L содерлшт п элементов, то наш абстрактный алгоритм требует выполнения п операторов INSERT, п операторов MIN, п операторов DELETE ип + 1 операторов EMPTY. Таким образом, обшее время выполнения алгоритма имеет порядок 0(п logn), если, конечно, используется подходяшая структура данных.

Структура данных частично упорядоченных деревьев из раздела 4.11 хорошо подходит для данного алгоритма. Напомним, что частично упорядоченное дерево можно представить в виде кучи - массива А, чьи элементы подчиняются неравенствам A\i].key < Al2*i].key и A[i].key < A[2*i -Ь l].key. Если интерпретировать элементы с индексами 2i и 2i + \ как "сыновей" элемента с индексом i, тогда массив А формирует сбалансированное двоичное дерево, в котором значения ключей родителей никогда не превосходят значения ключей сыновей.

В разделе 4.11 было показано, что частично упорядоченное дерево поддерживает операторы INSERT и DELETEMIN с временем выполнения O(logn). Но на частично упорядоченном дереве нельзя реализовать обший оператор DELETE с временем выполнения O(logn) (всегда найдется отдельный эдемент, требующий линейного времени удаления в самом худшем случае). В связи с этим отметим, что в листинге 8.9 удаляются только элементы, имеющие минимальные значения ключей. Поэтому строки (4) и (6) можно объединить одним оператором DELETEMIN, который будет возвращать эдемент у. Таким образом, используя структуру данных частично упорядоченного дерева из раздела 4.11, можно выполнить абстрактный алгоритм сортировки за время 0(п logn).

Сделаем еще одно изменение в алгоритме дистинга 8.9, чтобы избежать печати удаляемых элементов. Заметим, что множество S всегда хранится в виде кучи в верхней части массива, даясе когда содержит только i элементов (i < п). Для частично упорядоченного дерева наименьший эдемент всегда хранится в ячейке А[1]. Элементы, уже удаленные из множества S, можно было бы хранить в ячейках

Свое название этот алгоритм подучил вследствие того, что применяемое здесь частично упорядоченное сортирующее дерево имеет вид "пирамиды". Отметим таюке, что в русском издании Книги [3] этот метод сортировки назван "сортдеревом", т.е. упорядочиванием посредством сортирующего дерева. - Прим. ред.



All + 1], A[n], сортированными в обратном порядке, т.е. так, чтобы выполнялись неравенства Ali + 1] > A[i + 2] > ... > A[n].Поскольку элемент А[1] является наименьшим среди элементов то для повышения эффективности оператора DELETEMIN можно просто поменять местами элементы А[1] viAfiJ. Поскольку новый элемент A[i] (т.е. старый А[1]) не меньше, чем A[i + 1] (элемент A[i + 1] бьш удален из множества S на предыдущем шаге как наименьший), то получим последовательность A[n], отсортированными в убывающем порядке. Теперь надо заняться размещением элементов А[1], ...,A[i - 1].

Поскольку новый элемент А[1] (старый элемент Alt]) нарушает структуру частично упорядоченного дерева, его надо "протолкнуть" вниз по ветвям дерева, как это делается в процедуре DELETEMIN листинга 4.13. Здесь для этих целей мы используем процедуру pushdown (протолкнуть вниз), оперирующую с массивом А, определенным вне этой процедуры. Код процедурырн*Ай?оил приведен в листинге 8.10. С помощью последовательности перестановок данная процедура "проталкивает" элемент A[first]BHm по дереву до нужной позиции. Чтобы восстановить частично упорядоченное дерево в случае нашего алгоритма сортировки, надо вызвать процедуру pushdown для first - 1.

Листинг 8.10. Процедура pushdown

procedure pushdown ( first, last: integer >

{ Элементы A[first] , A [last] составляют частично

упорядоченное дерево за исключением, возможно, элемента А1 first] и его сыновей. Процедура pushdown восстанавливает частично упорядоченное дерево }

г: integer; { указывает текущую позицию A[first] } begin

r:= first; { инициализация } while г <= last div 2 do

if last = 2*r then begin

{ элемент в позиции г тоеет одного сьиа

в позиции 2*г } if А[г].key > А[2*г].кеу then swapiA[r], A[2*r]);

r;= last { досрочный выход из цикла while }

else { элемент в позиции г имеет двух сыновей в позициях 2*ги 2*г + 1 } if А[г].;сеу > А[2*г].;сеу and

А[2*г].кеу<= А[2*г + 1 ]. Jcey then begin { перестановка элемента в позиции г

с левым сыном } swap{A[r] , A[2*r] ) ;

т- 2*г

else \i Air].key > A[2*r + ll.Jcey and

A[2*r + 1] .key < A[2*r] .key then begin { перестановка элемента в позиции г с правым сыном }

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

8.4. ПИРАМИДАЛЬНАЯ СОРТИРОВКА 245





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.0038