Книга: Фундаментальные алгоритмы и структуры данных в Delphi

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

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

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

Алгоритм быстрой сортировки был разработан К.A.Р. Хоаром (C.A.R. Hoare) в 1960 году. Этот алгоритм, наверное, еще более известен, чем пузырьковая сортировка. В настоящее время он является самым широко используемым в программировании методом сортировки, что вызвано его крайне положительными характеристиками: это алгоритм класса O(n log(n)) для общего случая, он требует лишь незначительного объема дополнительной памяти, работает с различными типами входных списков и достаточно удобен для реализации. Но, к сожалению, быстрая сортировка имеет и несколько нежелательных характеристик: при его реализации допускается очень много ошибок (простые ошибки в реализации могут остаться незамеченными и при выполнении могут потребовать дополнительного времени), быстродействие в худшем случае составляет O(n(^2^)) и к тому же она неустойчива.

Кроме того, быстрая сортировка наиболее изучена. Со времени выхода в свет первой статьи Хоара многие исследователи изучали быструю сортировку и сформировали значительную базу данных по теоретическому определению времени выполнения, подкрепленную эмпирическими данными. Было предложено немало улучшений базового алгоритма, позволяющих увеличить скорость работы. Некоторые из предложенных улучшений будет рассмотрены в этой главе. При таком богатстве литературных источников по алгоритму быстрой сортировки, если следовать всем рекомендациям, у вас не должно возникнуть проблем с реализацией. (В последней оптимизированной реализации алгоритма использовалось более шести различных справочных пособий по алгоритмам. Причем в одной из них была приведена "оптимизированная" быстрая сортировка, которая была написана так плохо, что при одних и тех же входных данных работала даже медленнее, чем стандартный метод TList.Sort.)

Быстрая сортировка встречается везде. Во всех версиях Delphi, за исключением версии 1, метод TList.Sort реализован на основе алгоритма быстрой сортировки. Метод TStringList.Sort во всех версиях Delphi реализован с помощью быстрой сортировки. В С++ функция qsort из стандартной библиотеки времени выполнения также реализована на базе быстрой сортировки.

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

Таким образом, для выполнения быстрой сортировки необходимо знать два алгоритма более низкого уровня: как выбирать базовый элемент и как наиболее эффективно переставить элементы списка таким образом, чтобы получить два набора элементов: со значениями, меньшими, чем значение базового элемента, и со значениями, большими, чем значение базового элемента.

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

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

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

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

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

После выбора базового элемента можно перейти к описанию алгоритма разбиения списка. Добро пожаловать в известные своей быстротой внутренние циклы быстрой сортировки! Мы будем оперировать с двумя индексами: первый будет использоваться для прохождения по элементам списка слева направо, а второй -справа налево. Начинаем справа, и идем к левому краю списка, сравнивая значение каждого элемента со значением базового элемента. Выполнение цикла завершается, если найден элемент, значение которого меньше или равно значению базового элемента. Это был внутренний цикл 1: сравнение двух элементов и уменьшение значения индекса. Затем та же операция выполняется слева. Проход выполняется в направлении к правому концу списка. Значение каждого элемента сравнивается со значением базового элемента. Цикл завершается, если найден элемент, значение которого больше или равно значению базового элемента. Это внутренний цикл 2: сравнение двух элементов и увеличение значения индекса.

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

Листинг 5.14. Стандартная быстрая сортировка

procedure QSS( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

begin

{пока в списке есть хотя бы два элемента}

while (aFirst < aLast) do

begin

{в качестве базового элемента выбирается средний элемент списка}

Pivot := aList.List^[(aFirst+aLast) div 2];

{задать начальные значения индексов и приступить к разбиению списка}

L := pred(aFirst);

R := succ(aLast);

while true do

begin

repeat

dec(R);

until (aCompare (aList.List^ [R], Pivot) <=0);

repeat

inc(1);

until (aCompare(aList.List^[L], Pivot) >=0);

if (L >= R) then

Break;

Temp := aList.List^[L];

aList.List^[L] := aList.List^[R];

aList.List^[R] :=Temp;

end;

{выполнить быструю сортировку первого подфайла}

if (aFirst < R) then

QSS(aList, aFirst, R, aCompare);

{выполнить быструю сортировку второго подфайла - устранение рекурсии}

aFirst :=succ(R);

end;

end;

procedure TDQuickSortStd(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortStd');

QSS(aList, aFirst, aLast, aCompare);

end;

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

Именно она является рекурсивной, и именно она - суть всей реализации. Первое, что необходимо отметить, - процедура QSS работает только в том случае, когда в сортируемом списке есть хотя бы два элемента. В качестве базового элемента выбирается средний элемент списка. Затем устанавливаются начальные значения для индексов L и R - перед первым элементом и после последнего элемента списка соответственно. После этого в процедуре организован бесконечный цикл - при необходимости мы сами выйдем из него с помощью оператора break. Обратите внимание, что внутренние циклы организованы с помощью операторов Repeat..until. В первом цикле уменьшается значение индекса R до тех пор, пока он не будет указывать на элемент, значение которого меньше или равно значению базового элемента. Во втором цикле значение индекса L увеличивается до тех пор, пока он не будет указывать на элемент, значение которого больше или равно значению базового элемента. Затем сравниваются значения индексов L и R. Если значение L больше или равно значению R, индексы встретились или пересеклись, и мы выходим из бесконечного цикла. В противном случае два элемента, на которые указывают индексы, меняются местами, и выполнение цикла продолжается.

После выхода из бесконечного цикла во многих реализациях алгоритма быстрой сортировки присутствует примерно следующий код:

QSS(aList, aFirst, R, aCompare);

QSS(aList, R+ 1, aList, aCompare);

Другими словами, рекурсивно выполняется сортировка первой части, а затем -второй части раздела. Один из самых простых хитростей искусства программирования заключается в исключении рекурсивного вызова в конце рекурсивной процедуры. Как правило, бывает достаточно изменения переменных в процедуре и перехода к ее началу. В QSS для исключения рекурсии используется цикл while при изменении значения переменной aFirst. Очень простой метод устранения рекурсии, не правда ли?

После изучения такого рода процедур, особенно процедур с циклами, любой программист начнет искать способы увеличения ее эффективности. В случае с быстрой сортировкой лучше не пытайтесь изменять приведенную процедуру. Даже незначительное изменение может привести к существенному снижению скорости работы или к тому, что бесконечный цикл оправдает свое название. Давайте рассмотрим несколько часто встречаемых ошибок. Первое желание - установить начальные значения индексов L и R так, чтобы они указывали на фактические первый и последний элементы списка, а не на предшествующий первому и следующий после последнего элементы, а затем заменить цикл Repeat..until циклом while, естественно, изменив условие цикла. По крайней мере, в этом случае можно исключить одну операцию декремента и одну - инкремента. Первый цикл превратиться в цикл "выполнять, пока больше чем", а второй - в цикл "выполнять, пока меньше чем". Если на вход такой "улучшенной" процедуры быстрой сортировки подавать список с произвольных расположением элементов, он будет работать без ошибок. Но для списка, все элементы которого равны, бесконечный цикл будет действительно выполняться бесконечно, поскольку значения индексов меняться не будут. Изменение условий циклов включает равенство, позволяет избежать зацикливания процедуры, но приводит к еще одной проблеме: индексы будут выходить за границы списка.

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

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

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

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

Что дает нам случайный выбор базового элемента? При условии, что у нас есть достаточно хороший генератор псевдослучайных чисел, такой выбор гарантирует, что вероятность попадания на "худший" элемент становится пренебрежительно малой. Но, тем не менее, она не превращается в 0, просто выбор наихудшего для быстрой сортировки элемента в качестве базового становится весьма маловероятным.

Листинг 5.15. Быстрая сортировка со случайным выбором базового элемента

procedure QSR(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

begin

while (aFirst < aLast) do

begin

{выбрать случайный элемент, переставить его со средним элементом и взять в качестве базового элемента}

R := aFirst + Random(aLast - aFirst + 1);

L := (aFirst + aLast) div 2;

Pivot := aList.List^[R];

aList.List^[R] := aList.List^[L];

aList.List^[L] := Pivot;

{задать начальные значения индексов и приступить к разбиению списка}

L := pred( aFirst);

R := succ(aLast);

while true do

begin

repeat

dec(R);

until (aCompare(aList.List^[R], Pivot) <=0);

repeat

inc(1);

until (aCompare(aList.List^[L], Pivot) >=0);

if (L >= R) then

Brealc-Temp := aList.List^[L];

aList.List^[L] := aList.List^[R];

aList.List^[R] := Temp;

end;

{выполнить быструю сортировку первого подфайла}

if (aFirst < R) then

QSR(aList, aFirst, R, aCompare);

{выполнить быструю сортировку второго подфайла - устранение рекурсии}

aFirst :=succ(R);

end;

end;

procedure TDQuickSortRandom(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortRandom');

QSR(aList, aFirst, aLast, aCompare);

end;

Как видите, различия между стандартным алгоритмом быстрой сортировки и приведенным в листинге 5.15 совсем незначительны. Основное отличие представляет собой вставленный блок кода, который специально выделен в листинге. В нем первый индекс выбирается случайным образом из диапазона от aFirst до aLast включительно, а затем элемент с выбранным индексом меняется местами со средним элементом. Для удобства в приведенной реализации используется Delphi-функция Random. Она предоставляет хорошие последовательности псевдослучайных чисел. Перестановка выбранного и среднего элементов дает преимущества, о которых мы уже говорили.

Несмотря на то что внесенное изменение снижает вероятность выбора "худшего" элемента при каждом проходе цикла, тем не менее, оно не увеличивает скорость выполнения процедуры. Фактически скорость даже падает (как это и можно было предположить). Генерация случайного числа в качестве индекса для базового элемента работает отлично, в том смысле, что вероятность выбора "плохого" элемента в качестве базового снижается, но это положительное свойство не приводит к повышению быстродействия процедуры. Сложность линейного конгруэнтного метода генерации случайных чисел, используемого функцией Random, только увеличивает время выполнения процедуры. Можно было бы исследовать быстродействие при использовании различных генераторов (некоторые из них будут рассмотрены в главе 6), но оказывается, что существует намного более удачный алгоритм выбора базового элемента.

Самым эффективным методом выбора базового элемента на сегодняшний день является метод медианы трех. Мы уже говорили, что в идеальном случае желательно было бы выбирать средний элемент (или медиану) всех элементов списка. Тем не менее, определение медианы - достаточно сложная задача. Более простым кажется приближенное определение медианы. Для этого из подсписка выбирается три элемента и в качестве базового элемента выбирается медиана этих трех элементов. Медиана трех элементов служит приближением фактической медианы всех элементов списка. Конечно, такой алгоритм предполагает, что в списке должно быть, по крайней мере, три элемента. Но даже если элементов меньше, выполнить их сортировку не представляет большого труда.

Выбор трех элементов ничем не ограничивается, но имеет смысл выбирать первый, последний и средний элементы. Почему? Такая схема может облегчить весь процесс сортировки. Мы находим не только медиану трех элементов, но и расставляем их в требуемом порядке. Элемент с наименьшим значением попадает в первую позицию, средний элемент - в середину списка, а элемент с наименьшим значением - в последнюю позицию. Таким образом, при выборе базового элемента размер частей списка сокращается на два элемента, поскольку уже известно, что они находятся в правильных частях списка относительно базового элемента. Кроме того, такой алгоритм автоматически помещает базовый элемент в нужное место: в середину подсписка.

Листинг 5.16. Быстрая сортировка со случайным выбором базового элемента

procedure QSM(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

begin

while (aFirst < aLast) do

begin

{если в списке есть, по крайней мере, три элемента, выбрать базовый элемент, как медиану первого, последнего и среднего элементов списка и записать его в позицию в середине списка}

if (aLast - aFirst) >= 2 then

begin

R := (aFirst + aLast) div 2;

if (aCompare(aList.List^[aFirst], aList.List^[R]) > 0) then

begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] aList.List^[R];

aList.List^[R] :=Temp;

if (aCompare(aList.List^[aFirst], aList.List^[aLast]) > 0) then

begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[aLast];

aList.List^[aLast] := Temp;

if (aCompare(aList,List^[R], aList.List^[aLast]) > 0) then

begin

Temp := aList.List^[R];

aList.List^[R] := aList.List^[aLast];

aList.List^[aLast] := Temp;

Pivot :-aList,List^[R];

{в противном случае в списке всего 2 элемента, выбрать в качестве базового первый элемент}

Pivot := aList.List^[ aFirst ];

{задать начальные значения индексов и приступить к разбиению списка}

L := pred( aFirst);

R := succ(aLast);

while true do

begin

repeat

dec (R);

until (aCompare (aList.List^[R], Pivot) <= 0);

repeat

inc(L);

until (aCompare(aList.List^[L], Pivot) >=0);

if (L >=R) then

Break;

Temp := aList.List^[L];

aList.List^[L] := aList.List^[R];

aList.List^[R] := Teilend;

{выполнить быструю сортировку первого подфайла}

if (aFirst < R) then

QSM(aList, aFirst, R, aCompare);

{выполнить быструю сортировку второго подфайла - устранение рекурсии}

aFirst := succ(R);

end;

end;

procedure TDQuickSortMedian( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortMedian');

QSM(aList, aFirst, aLast, aCompare);

end;

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

Сортировка трех выбранных элементов выполняется на основе одного малоизвестного и малоиспользуемого метода. Предположим, что выбраны элементы a, b и c. Сравниваем а и b. Если b меньше чем я, поменять их местами. Таким образом, получим a < b. Сравниваем a и c. Если c меньше чем a, поменять их местами. Получим a < c. После выполнения этих сравнений нам будет известно, что элемент a содержит минимальное значение из трех выбранных элементов, поскольку оно меньше или равно значениям элементов b и c. Сравниваем b и с. Если с меньше чем b, поменять их местами. Теперь элементы расположены в порядке a< b<c, т.е. они отсортированы. Если количество элементов в списке не больше двух, в качестве базового элемента выбирается первый.

Это улучшение, несмотря на кажущуюся медлительность, на практике работает быстрее, чем стандартная быстрая сортировка. Надо признать, увеличение скорости незначительно, но, тем не менее, ощутимо.

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

Рассмотрим рекурсивный вызов. Задаются четыре параметра, два из которых постоянны, а два других от вызова к вызову могут изменяться. Постоянные параметры - aList и aCompare, переменные параметры - aFirst и aSecond. Рекурсивный вызов можно устранить за счет использования явного стека, который предназначен для заталкивания и выталкивания переменных параметров. При этом цикл будет выполняться до тех пор, пока стек не будет пустым.

Листинг 5.17. Быстрая сортировка со случайным выбором базового элемента

procedure QSNR(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

Stack : array [0..63] of integer;

{позволяет разместить до 2 миллиардов элементов}

SP : integer;

begin

{инициализировать стек}

Stack[0] := aFirst;

Stack[1] := aLast;

SP := 2;

while (SP <> 0) do

begin

{вытолкнуть верхний подфайл}

dec(SP, 2);

aFirst := Stack[SP];

aLast := Stack[SP+1];

{пока в списке есть хотя бы два элемента}

while (aFirst < aLast) do

begin

{в качестве базового выбирается средний элемент}

Pivot := aList.List^[ (aFirst+aLast) div 2];

{задать начальные значения индексов и приступить к разбиению списка}

L := pred(aFirst);

R := succ(aLast);

while true do

begin

repeat

dec(R);

until (aCompare(aList.List^[R], Pivot) <=0);

repeat

inc(L);

until (aCompare(aList.List^[L], Pivot) >=0);

if (L >= R) then

Break;

Temp := aList.List^ [L];

aList.List^[L] := aList.List^[R];

aList.List^[R] :=Temp;

end;

{затолкнуть больший подфайл в стек и повторить цикл для меньшего подфайла}

if (R - aFirst) < (aLast - R) then begin

Stack [SP] :=succ(R);

Stack[SP+1] := aLast;

inc(SP, 2);

aLast := R;

end

else begin

Stack[SP] := aFirst;

Stack [SP+1] :=R;

inc(SP, 2);

aFirst := succ(R);

end;

end;

end;

end;

procedure TDQuickSortNoRecurse( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

begin

TDValidateListRange(aList, aFirst, aLast, 'TDQuickSortNoRecurse');

QSNR(aList, aFirst, aLast, aCompare);

end;

И в этом листинге код состоит из двух процедур: процедуры-драйвера и процедуры собственно сортировки. Таким образом, общая схема работы алгоритма осталась неизменной, но в этом случае внутренняя процедура, QSNR, вызывается только один раз.

В процедуре QSNR объявляется стек Stack для хранения 64 элементов типа longint и указатель на стек SP, который будет указывать на начало стека. Комментарий жизнерадостно утверждает, что размера стека будет достаточно для хранения 2 миллиардов элементов. Через несколько минут мы докажем справедливость комментария. В начале процедуры в стек записываются переданные процедуре начальный и конечный индексы. Предполагается, что на индекс первого элемента указывает указатель стека, а индекс последнего элемента хранится в позиции SP+1. После записи индексов указатель стека перемещается на 2 позиции. (В реализации алгоритма может использоваться два стека: один для индексов aFirst, а второй - для индексов aLast. При этом для обоих стеков будет нужен только один указатель.)

Далее начинается выполнение цикла while, которое завершается, когда стек опустеет, что эквивалентно равенству SP=0.

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

Давайте на минутку задумаемся, что происходит. Если нам несказанно повезло, и для каждого подсписка в качестве базового элемента были выбраны их действительные медианы, то размеры подсписков будут составлять ровно половину размера подсписка более высокого уровня. Если в исходном списке было, например, 32 элемента, он будет разбит на 2 подсписка по 16 элементов, каждый из которых, в свою очередь, будет разбит еще на два подсписка по 8 элементов и т.д. Таким образом, максимальная глубина вложения подсписков в стеке будет равна пяти, поскольку 2(^5^)=32. Подумайте над этим. Мы затолкнем в стек подсписок из 16 элементов, разобьем второй такой же список на два списка по 8 элементов, затолкнем в стек один из списков длиной 8 элементов, а второй разобьем на два подсписка по 4 элемента и т.д. Пока мы дойдем до подсписка с одним элементом, в стеке уже будут находиться подсписок из 16 элементов, подсписок из 8 элементов, подсписок из 4 элементов, подсписок из 2 элементов и подсписок из 1 элемента. Пять уровней. Таким образом, для сортировки списка, содержащего 2 миллиарда элементов, будет достаточно 32 уровней (как это указано в комментарии к процедуре QSNR), если, конечно, каждый раз мы будем удачно выбирать базовый элемент.

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

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

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

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

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

Представьте себе, что разбиваются только подсписки размером не менее определенного количества элементов. К чему бы привел такой алгоритм быстрой сортировки? Мы получим грубо отсортированный список, т.е. все его элементы будут находиться вблизи требуемых позиций. Подсписки, которые были получены перед прекращением процесса разбиения, будут отсортированы в том смысле, что если подсписок X находится перед подсписком Y, то все элементы подсписка X будут расположены в отсортированном списке перед элементами подсписка Y. Это как раз самое удобное распределение для сортировки методом вставок. Таким образом, работу, начатую быстрой сортировкой, можно завершить с помощью сортировки методом вставок.

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

Листинг 5.18. Оптимизированная быстрая сортировка

const

QSCutOff = 15;

procedure QSInsertionSort(aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

IndexOfMin : integer;

Temp : pointer;

begin

{найти элемент с наименьшим значением из первых QSCutOff элементов и переместить его на первую позицию}

IndexOfMin := aFirst;

j := QSCutOff;

if (j > aLast) then

j := aLast;

for i := succ(aFirst) to j do

if (aCompare(aList.List^[i], aList.List^[IndexOfMin]) < 0) then

IndexOfMin := i;

if (aFirst <> indexOfMin) then begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[IndexOfMin];

aList.List^[IndexOfMin] := Temp;

end;

{выполнить сортировку методом вставок}

for i := aFirst+2 to aLast do

begin

Temp := aList.List^[i];

j := i

while (aCompare(Temp, aList.List^[j-1]) < 0) do

begin

aList.List^[j] := aList.List^[j-1];

dec(j);

end;

aList.List^ [j ] :=Temp;

end;

end;

procedure QS( aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdComparSFunc);

var

L, R : integer;

Pivot : pointer;

Temp : pointer;

Stack : array [0..63] of integer;

{позволяет разместить до 2 миллиардов элементов}

SP : integer;

begin

{инициализировать стек}

Stack[0] := aFirst;

Stack[1] := aLast;

SP := 2;

{пока в стеке есть подфайлы}

while (SP<> 0) do

begin

{вытолкать верхний подфайл}

dec(SP, 2);

aFirst := Stack[SP];

aLast := Stack[SP+1];

{повторять пока в подфайле есть достаточное количество элементов}

while ((aLast - aFirst) > QSCutOff) do

begin

{выполнить сортировку первого, среднего и последнего элементов и в качестве базовой точки выбрать средний - метод медианы трех}

R := (aFirst + aLast) div 2;

if aCompare(aList.List^[aFirst], aList.List^[R]) > Othen begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[R];

aList.List^[R] := Temp;

end;

if aCompare(aList.List^[aFirst], aList.List^[aLast]) > 0 then begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[aLast];

aList.List^ [aLast] := Temp;

end;

if aCompare(aList.List^[R], aList.List^[aLast]) > 0 then begin

Temp := aList.List^[R];

aList.List^[R] := aList.List^[aLast];

aList.List^ [aLast] :=Temp;

end;

Pivot := aList.List^[R];

{задать начальные значения индексов и приступить к разбиению списка}

L := aFirst;

R := aLast;

while true do

begin

repeat

dec(R);

until (aCompare(aList.List^[R], Pivot) <=0);

repeat

inc(1);

until (aCompare(aList.List^[L], Pivot) >=0);

if (L >= R) then

Break;

Temp := aList.List^[L];

aList.List^[L] := aList.List^[R];

aList.List^[R] :=Temp;

end;

{затолкнуть больший подфайл в стек и повторить цикл для меньшего подфайла}

if (R - aFirst) < (aLast - R) then begin

Stack[SP] :=succ(R);

Stack[SP+1] := aLast;

inc(SP, 2);

aLast := R;

end

else begin

Stack[SP] := aFirst;

Stack [SP+1] :=R;

inc(SPs 2);

aFirst := succ(R);

end;

end;

end;

end;

procedure TDQuickSort( aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

begin

TDValidateListRange(aList, aFirst, aLast, 'TDQuickSort');

QS(aList, aFirst, aLast, aCompare);

QSInsertionSort(aList, aFirst, aLast, aCompare);

end;

Эта оптимизированная быстрая сортировка состоит из трех процедур. Первая из них - вызываемая процедура TDQuickSort. Она проверяет корректность переданных параметров, для частично сортировки списка вызывает процедуру QS, а затем для окончательной сортировки вызывает процедуру QSInsertionSort. Процедура QS выполняет нерекурсивный процесс разбиения списка до получения подсписков определенного минимального размера. QSInsertionSort представляет собой процедуру оптимизированной сортировки методом вставок для частично отсортированного списка. В частности, обратите внимание, что элемент с наименьшим значением находится в первых QSCutOf f элементах списка. Это вызвано выполнением процесса разбиения и тем фактом, что при достижении размеров подсписков QSCutOff элементов разбиение прекращается.

Стоила ли игра свеч? Тесты однозначно показывают, что стоила. При сортировке 100000 элементов типа longint оптимизированный алгоритм сортировки потребовал на 18% меньше времени, чем стандартный.

Оглавление книги