Finally

Try

Begin

Begin

Var

Begin

Else

End

Begin

Begin

Begin

Var

Begin

Else

End

Begin

Begin

Begin

Begin

Begin

Var

Begin

repeat Dec(R);

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

repeat Inc(L);

until aCompare(aList.List[L], M) >= 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

QuickHoarMDNSort(aList, aFirst, R, aCompare);

aFirst:=R+1;

end;

end;

{ Быстрая сортировка Хоара без рекурсии }

procedure QuickHoarNonRecursiveSort;

L, R, SP: Integer;

M, Temp: Pointer;

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

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

Stack[0]:=aFirst;

Stack[1]:=aLast;

SP:=2;

while SP <> 0 do

{ Извлечь верхний список }

Dec(SP, 2);

aFirst:=Stack[SP];

aLast:=Stack[SP+1];

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

while aFirst < aLast do

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

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

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

L:=aFirst-1; R:=aLast+1;

while True do

repeat Dec(R);

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

repeat Inc(L);

until aCompare(aList.List[L], M) >= 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

Stack[SP]:=R+1;

Stack[SP+1]:=aLast;

Inc(SP, 2);

aLast:=R;

Stack[SP]:=aFirst;

Stack[SP+1]:=R;

Inc(SP, 2);

aFirst:=R+1;

end;

end;

end;

end;

{ Сортировка слиянием }

procedure MSS;

Mid, i, j, ToInx,

FirstCount: Integer;

{ Вычислить среднюю точку }

Mid:=(aFirst + aLast) div 2;

{ Рекурсивная сортировка слиянием первой и второй половин списка }

if aFirst < Mid then

MSS(aList, aFirst, Mid, aCompare, aTempList);

if (Mid+1) < aLast then

MSS(aList, Mid+1, aLast, aCompare, aTempList);

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

FirstCount:=Mid-aFirst+1;

Move(aList.List[aFirst], aTempList[0], FirstCount*SizeOf(Pointer));

{ Установить значения индексов: i - индекс для вспомогательного списка

(т.е. первой половины); j - индекс для второй половины списка;

ToInx - индекс в результирующем списке, куда будут копироваться

отсортированные элементы }

i:=0; j:=Mid+1; ToInx:=aFirst;

{ Выполнить слияние двух списков; повторять

пока один из списков не опустеет }

while (i < FirstCount) and (j <= aLast) do

{ Определить элемент с наименьшим значением из следующих

элементов в обоих списках и скопировать его; увеличить

значение соответствующего индекса }

if aCompare(aTempList[i], aList.List[j]) <= 0 then

aList.List[ToInx]:=aTempList[i];

Inc(i);

aList.List[ToInx]:=aList.List[j];

Inc(j);

end;

{ В объединенных списках есть еще один элемент }

Inc(ToInx);

end;

{ Если в первом элементе остались элементы, скопировать их }

if i < FirstCount then

Move(aTempList[i], aList.List[ToInx], (FirstCount - i)*SizeOf(Pointer));

{ Если во втором списке остались элементы, то они уже находятся в нужных

позициях, т.е. сортировка завершена; если второй список пуст, сортировка

также завершена }

end;

procedure MergeSortStd(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

TempList: PPointerList;

ItemCount: Integer;

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

if aFirst < aLast then

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

ItemCount:=aLast-aFirst+1;

GetMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));

MSS(aList, aFirst, aLast, aCompare, TempList);

FreeMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));

end;

end;

end;

Дата добавления: 2014-01-07