Структуры данных и алгоритмы (1021739), страница 59
Текст из файла (страница 59)
В этом случае переставляются не сами записи, а только указатели на них.После упорядочивания указателей сами записи можно расположить в нужном порядке за время порядка О(п).Ограниченность простых схем сортировкиЕще раз напомним, что каждый из рассмотренных в этом разделе алгоритмов выполняется за время порядка О(п2) как в среднем, так и в самом худшем случае.
Поэтому для больших п эти алгоритмы заведомо проигрывают алгоритмам с временем выполнения О(п logra), которые будут описаны в следующем разделе. Значение л, начинаяс которого быстрые алгоритмы сортировки становятся предпочтительнее простых методов сортировки, зависит от различных факторов, таких как качество объектного кодапрограммы, генерируемого компилятором, компьютера, на котором выполняется программа сортировки, или от размера записей. Определить такое критическое значение пдля конкретных задач и вычислительного окружения (компилятор, компьютер и т.п.)можно после экспериментов с профайлером1 и на основании выдаваемых им результатов. Практический опыт учит, что при га, не превышающем 100, на время выполненияпрограммы влияет множество факторов, которые с трудом поддаются регистрации ипоэтому не учтены в анализе, проведенном в этом разделе.
Для небольших значений прекомендуем применять простой в реализации алгоритм сортировки Шелла (Shell), который имеет временную сложность О(п1'ь). Этот алгоритм, описанный в упражнении 8.3, является обобщением алгоритма "пузырька".1Профайлер — это подпрограмма протоколирования, позволяющая оценить время выполнения отдельных функций и операторов программы. — Прим. ред.234ГЛАВА 8. СОРТИРОВКА8.3.
Быстрая сортировка1Первый алгоритм с временем выполнения О(п log л) , который мы рассмотрим далее, является, по-видимому, самым эффективным методом внутренней сортировки и2поэтому имеет название "быстрая сортировка". В этом алгоритме для сортировкиэлементов массива А[1], ..., А[п} из этих элементов выбирается некоторое значениеключа v в качестве опорного элемента, относительно которого переупорядочиваютсяэлементы массива. Желательно выбрать опорный элемент близким к значению медианы распределения значений ключей так, чтобы опорный элемент разбивал множество значений ключей на две примерно равные части. Далее элементы массива переставляются так, чтобы для некоторого индекса /' все переставленные элементыА[1], ..., АЦ] имели значения ключей, меньшие чем v, а все элементы A[j + 1], ....А[п] — значения ключей, большие или равные v.
Затем процедура быстрой сортировки рекурсивно применяется к множествам элементов .А[1], ..., АЦ] и А[; + 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) должна упорядочить элементы A[i], ..., A[j]. Предварительный набросокпроцедуры показан в листинге 8.5. Отметим, что если все элементы A[i], ..., A[f]имеют одинаковые ключи, над ними не производятся никакие действия.Листинг 8.5.
Процедура быстрой сортировки(1)if A[i], ..., А[j] имеют не менее двух различных ключей then begin(2)пусть v —^наибольший из первых двух найденных различныхключей;переставляются элементы A [ i ] , ..., A [ j ] так, чтобыдля некоторого k, i+l<fc<j, A [ i ] , ..., A[k-l] имели ключи,,меньшие, чем v, a A[k], ..., A [ j ] — большие или равные v;qu,icksort(i, k-l) ;quicksort(k, j)(3)(4)(.5).endНапишем функцию findpivot (нахождение опорного элемента), реализующую проверку в строке (1) листинга 8.5, т.е.
проверяющую, все ли элементы A[i], ..., A\j]одинаковы. Если функция findpivot не находит различных ключей, то возвращает1Строго говоря, описываемый далее алгоритм быстрой сортировки имеет время выполнения О(п logn) только в среднем, в самом худшем случае его временная сложность имеет порядок 2О(п2).Интересно отметить, что название quicksort (быстрая сортировка) этому алгоритму дал егоавтор Хоар (Ноаге С. A. R.) в работе [49] (интересная статья, в которой исчерпывающе описанданный алгоритм), и в дальнейшем никто не оспаривал это название.
— Прим. ред.8.3. БЫСТРАЯ СОРТИРОВКА235значение 0. В противном случае она возвращает индекс наибольшего из первых двухразличных ключей. Этот наибольший ключ становится опорным элементом. Кодфункции findpivot приведен в листинге 8.6.3141592532114593|6|531145|9365365«i6Этап 12Этап 21Этап 31готовоготовоЕЕ3v=53I 933а9655345659\4Этап 41готово\56/v\.5готовоV= 6ГОТОВО55SЭтап 5'ГОТОВОГОТОВОРис. 8.1. Этапы быстрой сортировкиЛистинг 8.6. Функция findpivotfunction findpivot ( i, j: integer ): integer;varfirstkey: keytype;{ примет значение первого найденного ключа,т.е.
А[i].key }k: integer; { текущий индекс при поиске различных ключей)beginfirstkey.= A[i] .key;for A-:=i + l t o j d o { просмотр ключей }if A[k].key > firstkey then { выбор наибольшего ключа}236ГЛАВА 8. СОРТИРОВКАreturn(k)else if A[k].key < firstkey thenreturn(i) ;return(0) { различные ключи не найдены }end; { findpivot }Теперь реализуем строку (3) из листинга 8.5, где необходимо переставить элементыA[i], ..., AJJ] так, чтобы все элементы с ключами, меньшими опорного значения, располагались слева от остальных элементов1.
Чтобы выполнить эти перестановки, введем двакурсора I и г, указывающие соответственно на левый и правый концы той части массиваА, где в настоящий момент мы переставляем (упорядочиваем) элементы. При этом считаем, что уже все элементы A[i], ..., A[l- 1], расположенные слева от I, имеют значенияключей, меньшие опорного значения. Соответственно элементы А[г + 1], ..., A[j], расположенные справа от г, имеют значения ключей, большие или равные опорному значению(рис. 8.2). Нам необходимо рассортировать элементы .AJ7], ...,А[г\.ключи < опорное значениеключи > опорное значение//гjРис. 8.2.
Ситуация, возникающая в процессеперемещения элементов.Сначала положим I = i и г = j. Затем будем повторять следующие действия, которые перемещают курсор I вправо, а курсор г влево до тех пор, пока курсоры непересекутся.1.Курсор перемещается I вправо, пока не встретится запись с ключом, не меньшимопорного значения. Курсор г перемещается влево, также до тех пор, пока невстретится запись с ключом, меньшим опорного значения. Отметим, что выборопорного значения функцией findpivot гарантирует, что есть по крайней мереодна запись с ключом, значение которого меньше опорного значения, и есть хотябы одна запись со значением ключа, не меньшим выбранного опорного значения.Поэтому обязательно существует "промежуток" между элементами A[i] и -А[у], покоторому могут перемещаться курсоры I и г.2.
Выполняется проверка: если I > г (на практике возможна только ситуация, когдаI = г + 1), то перемещение элементов A[i], ..., A[j] заканчивается.3. В случае I < г (очевидно, что случай I = г невозможен) переставляем местамиэлементы Д[П, и А[г]. После этого запись А[1] будет иметь значение ключа меньшее, чем опорное значение, а А[г] — большее или равное опорному значению.Курсор I перемещается на одну позицию от предыдущего положения вправо, акурсор г — на одну позицию влево. Далее процесс продолжается с пункта 1.Описанный циклический процесс несколько неуклюжий, поскольку проверка, приводящая к окончанию процесса, расположена посредине.
Если этот процесс оформить ввиде цикла repeat, то этап 3 надо переместить в начало. Но в этом случае при I = i иг = j сразу меняются местами элементы A[i] и A[f], независимо от того, надо это делатьили нет. Но с другой стороны, это несущественно, так как мы не предполагаем перво1Можно скопировать элементы A[t], ..., A[j] в другой массив, упорядочить их там, а затем вернуть обратно в ячейки A[i]A[j] массива А. Но мы не будем обсуждать этот подход, так как он требует дополнительной памяти и удлиняет сам процесс сортировки посравнению с рассматриваемым подходом, когда перестановки элементов выполняются непосредственно в массиве А.8.3.
БЫСТРАЯ СОРТИРОВКА237начальное упорядочивание элементов A[i], ..., A[f]. В любом случае, читатель должензнать о таких "шалостях" алгоритма, поэтому они не должны его озадачивать. Функция partition (разделение), которая выполняет перестановки элементов и возвращаетиндекс I, указывающий на точку разделения данного фрагмента массива А на основезаданного опорного значения pivot, приведена в листинге 8.7.Листинг 8.7.
Функция partitionfunction partition ( i, j: integer; pivot: keytype ) : integer;var1, i: integer; { курсоры }begin(1)(2)(3)(4)(5)(6)(7)(8)(9)1:= isr:= j ;repeatswap(A[l], A [ r ] ) ;while A [ l ] . k e y < pivot doI:= 1 + 1;while A[r] .key >= pivot dor:= r - 1until1 > r;return(1)end; { partition }Теперь можно преобразовать эскиз алгоритма быстрой сортировки (листинг 8.5) внастоящую программу quicksort (быстрая сортировка). Код этой программы приведенв листинге 8.8. Для сортировки элементов массива А типа аггау[1..п] of recordtypeнадо просто вызвать процедуру quicksort(l, n).Листинг 8.8. Процедура быстрой сортировкиprocedure quicksort ( i, j: integer );^{ сортирует элементы A [ i ] , ..., A [ j ] внешнего массива А }varpivot: keytype; { опорное значение }pivotindex: integer;{ индекс элемента массива А, чей ключ равен pivot }k: integer;{начальный индекс группы элементов, чьи ключи > pivot)begin(1)pivotindex:= findpivot(i, j);(2)if pivotindex <> 0 then begin{ если все ключи равны, то ничего делать не надо }(3)pivot:= A[pivotindex].key;(4)(5)(6)k:= portitiond, j, pivot);endquicksort(i, k-1);guicA:sort(>:, j )end; { quicksort }Временная сложность быстрой сортировкиПокажем, что время выполнения быстрой сортировки п элементов составляет всреднем О(п logn) и О(л2) в худшем случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
