{ реурсивные алгоритмы: быстрая сортировка, см. программу внизу }
{ ----------------------------------------------------------------------- }
{ БЫСТРАЯ СОРТИРОВКА. }
{ Устанавливаем I=1 и J=N. Сравниваем элементы A[I] и A[J]. Если }
{ A[I]<=A[J], то уменьшаем J на 1 и проводим следующее сравнение элемен- }
{ тов A[I] с A[J]. Последовательное уменьшение индекса J и сравнение ука- }
{ занных элементов A[I] с A[J] продолжаем до тех пор, пока выполняется }
{ условие A[I] <= A[J]. Как только A[I] станет больше A[J], меняем места- }
{ ми элементы A[I] с A[J], увеличиваем индекс I на 1 и продолжаем сравне- }
{ ние элементов A[I] с A[J]. Последовательное увеличение индекса I и }
{ сравнение (элементов A[I] с A[J]) продолжаем до тех пор, пока выполня- }
{ ется условие A[I] <= A[J]. Как только A[I] станет больше A[J], опять }
{ меняем местами элементы A[I] с A[J], снова начинаем уменьшать J. }
{ Чередуя уменьшение J и увеличение I, сравнение и необходимые обме- }
{ ны, приходим к некоторому элементу, называемому пороговым или главным, }
{ характеризующим условие I=J. В результате элементы массива оказываются }
{ разделенными на две части так, что все элементы слева - меньше главного }
{ элемента, а все элементы справа - больше главного элемента. }
{ К этим массивам применяем рассмотренный алгоритм, получаем четыре }
{ части и т.д. Процесс закончим, когда массив A станет полностью отсорти- }
{ рованным. }
{ При программировании алгоритма "Быстрой сортировки" удобно исполь- }
{ зовать рекурентные вызовы процедуры сортировки (рекурсию). }
{ ----------------------------------------------------------------------- }
var a : array[1..10] of integer;
n : integer;
procedure QuickSort(L, R: Integer);
var i, j, x, y: integer;
begin
i := l;
j := r;
x := a[(l + r) div 2];
repeat
while (A[i] < x) do inc(i);
while (x < A[j]) do dec(j);
if (i <= j) then
begin
y := A[i];
a[i] := a[j];
a[j] := y;
inc(i);
dec(j);
end;
until (i > j);
if (l < j) then QuickSort(l, j);
if (i < r) then QuickSort(i, r);
end;
begin
writeln('Введите 10 элементов массива:');
for n := 1 to 10 do readln(a[n]);
QuickSort(1, 10);
writeln('После сортировки:');
for n := 1 to 10 do writeln(a[n]);
end.
