Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
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 работает только в том случае, когда в сортируемом списке есть хотя бы два элемента. В качестве базового элемента выбирается средний элемент списка. Затем устанавливаются начальные значения для индексов 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;
{выполнить быструю сортировку первого подфайла}