Чтение онлайн

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

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), но оказывается, что существует намного более удачный алгоритм выбора базового элемента.

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