Оба выше рассмотренных метода достаточно просты и наглядны, но не очень эффективны. Значительно быстрее работает алгоритм сортировки К.Хоора, который называют сортировкой с разделением или "быстрой сортировкой". В основу алгоритма положен метод последовательного дробления массива на части.
program Quck_sort; {Быстрая сортировка по невозрастанию дроблением массива на части}
uses Crt;
const Count=20;
M : array [1..Count] of
byte=(9,11,12,3,19,1,5,17,10,18,3,19,17,9, 12,20,20,19,2,5);
var
I,A : integer;
procedure QuickS(First,Last;integer);
var I,J,X,W,L:integer;
begin
I:=First; {Левая граница массива — первый элемент}
J:=Last; {Правая граница массива — последний элемент}
Х:=М[(First+Last) div 2]; {Определить середину массива}
repeat
while M[I]>X do I:=I+1;
while X>M[J] do J:=J-1;
A:=A+1; {Увеличить число итераций обмена элементов}
if I<=J then
begin {Обменять местами элементы}
W:=M[i];
M[I]:=M[J];
M[J]:=W;
I:=I+1;
J:=J-1;
{Печатать текущее состояние массива после каждой перестановки}
for L := 1 to Count do Write(' ',M[L]); Writeln('Число итераций =',A);
end;
until I>J;
if First
if I
end; {Конец сортировки}
begin {Начало основной программы}
ClrScr;
Writeln('Исходный массив:'); Writeln;
for I:=1 to Count do Write (M[I]:3,' '); Writeln;
A:=0;
QuickS (1,Count); {Вызов процедуры сортировки QuickS}
Writeln ('Отсортированный массив:'); Writeln;
for I:=1 to Count do Write (M[I]:3,' '); Writeln;
end.
|