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), если, конечно,
