Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Самым эффективным методом выбора базового элемента на сегодняшний день является метод медианы трех. Мы уже говорили, что в идеальном случае желательно было бы выбирать средний элемент (или медиану) всех элементов списка. Тем не менее, определение медианы - достаточно сложная задача. Более простым кажется приближенное определение медианы. Для этого из подсписка выбирается три элемента и в качестве базового элемента выбирается медиана этих трех элементов. Медиана трех элементов служит приближением фактической медианы всех элементов списка. Конечно, такой алгоритм предполагает, что в списке должно быть, по
Выбор трех элементов ничем не ограничивается, но имеет смысл выбирать первый, последний и средний элементы. Почему? Такая схема может облегчить весь процесс сортировки. Мы находим не только медиану трех элементов, но и расставляем их в требуемом порядке. Элемент с наименьшим значением попадает в первую позицию, средний элемент - в середину списка, а элемент с наименьшим значением - в последнюю позицию. Таким образом, при выборе базового элемента размер частей списка сокращается на два элемента, поскольку уже известно, что они находятся в правильных частях списка относительно базового элемента. Кроме того, такой алгоритм автоматически помещает базовый элемент в нужное место: в середину подсписка.
Листинг 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
{вытолкнуть верхний подфайл}