{  реурсивные алгоритмы: быстрая сортировка, см. программу внизу           }
{  ----------------------------------------------------------------------- }
{                           БЫСТРАЯ СОРТИРОВКА.                            }
{       Устанавливаем 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 ); { Быстрая сортировка массива A[] }
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.
