Program Algorithm;

{ Quick sort.
  Described on page 114 of "The Art of Computer Programming"
  volume 3 / "Sorting and Searching" by Donald E. Knuth.
  Programmed as in: Turbo Pascal 7, The Complete Reference, page 705 }

const
  N = 25;

type
  Int_Arr = array[1..N] of Integer;

var
  Infile : text;
  m : integer;
  A : Int_Arr;

procedure Quick(var Item : Int_Arr; Count : integer);

  procedure PartialSort(Left, Right : integer ; var A : Int_Arr);

  var ii, l1, r1, i, j, k : integer;

    procedure Switch(var A, B : integer);
    var
      C : integer;
    begin
      if A <> B then
      begin
        C := A;
        A := B;
        B := C;
      end;
    end;

  begin
    k := (A[left] + A[right]) div 2;
    i := left;
    j := right;
    repeat
      while A[i] < k do
        Inc(I,1);
      while k < A[j] do
        Dec(J,1);
      if i <= j then
      begin
        Switch(A[i],A[j]);
        Inc(i,1);
        Dec(j,1);
      end;
    until i > j;
    if left < j then
     PartialSort(left, j, A);
    if i < right then
     PartialSort(i, right, A);
  end;

begin
  PartialSort(1, Count, Item);
end;

begin
  m := Random(5*N)+1;
  for m := 1 to N do
    A[m] := Random(5*N)+1;
  for m := 1 to N do
    Write(A[m],' ');
  Writeln;

  Quick(A, N);

  for m := 1 to N do
    Write(A[m],' ');
  Writeln;
end.