uses
  crt;
const
  n = 100;
  n_sorts = 3;
type
  tm = array[1 .. n] of integer;
  tvector = array[1 .. n_sorts] of integer;
  tgist = array[1 .. 2] of tvector;

const
  names: array[1 .. n_sorts] of string = (
    ' VYBOR', 'PR_VKL', ' QUICK'
  );

procedure print_array(const a: tm);
var i: integer;
begin
  for i := 1 to n do write(a[i]:4);
  writeln;
end;

var
  data: tgist;


  function isGreater(a, b: integer; var srav: integer): boolean;
  begin
    inc(srav);
    isGreater := (a > b);
  end;


procedure pr_vkl(var a: tm; var peres, srav: integer);
var
  i, j, m, r: integer;
begin
  peres := 0; srav := 0;

  for i := 2 to n do begin
    r := a[i];
    j := i - 1;
    while (j >= 1) and (not isGreater(r, a[j], srav)) do begin
      a[j+1] := a[j]; Inc(Peres);
      dec(j);
    end;
    a[j+1] := r;
  end;

  print_array(a);
  writeln('Metod priamogo vklycheniia:');
  writeln('Chislo perestanovok = ',peres);
  writeln('Chislo sravneniy = ',srav);
  readln;
end;

procedure vybor(var a: tm; var peres, srav: integer);
var i, j, k, temp: integer;
begin
  peres := 0; srav := 0;

  for i := 1 to n-1 do begin
    k := i;
    temp := a[i];
    for j := i+1 to n do begin
      if not isGreater(a[j], temp, srav) then begin
        k := j;
        temp := a[j];
      end;
    end;
    a[k] := a[i];
    if k <> i then inc(peres);
    a[i] := temp;
  end;

  print_array(a);
  writeln('Metod VYBOR:');
  writeln('Chislo perestanovok = ',peres);
  writeln('Chislo sravneniy = ',srav);
  readln;
end;


procedure quicksort(var a: tm; var peres, srav: integer);

  procedure hoars(var x: tm; l, u:integer);
  var
    i, j, T: integer;
  begin
    while u > l do begin
      i:=l; j:=u; t:=x[l];
      while i<j do begin
        while isGreater(x[j], t, srav) do j:=j-1;
        x[i]:=x[j]; inc(peres);

        while(i<j) and (not isGreater(x[i], t, srav)) do i:=i+1;
        x[j]:=x[i]; inc(peres);
      end;

      x[i]:=t;
      hoars(x,l,i-1);
      inc(l);
    end;

  end;

begin
  peres := 0; srav := 0;

  hoars(a, 1, n);

  write('Sortirovka');
  print_array(a);

  writeln('Quick sort:');
  writeln('Chislo perestanovok = ',peres);
  writeln('Chislo sravneniy = ',srav);
end;


procedure show_gist(const title: string;
          const labels: array of string;
          const v: tvector);
const
  start = 20;
  len = 50;
var
  i, j, max: integer;
  mult: real;
begin

  max := v[1];
  for i := 1 to n_sorts do
    if max < v[i] then max := v[i];

  mult := len / max;
  writeln(title);
  for i := 1 to n_sorts do begin
    write(labels[pred(i)] + ' : ', v[i]:6);
    gotoxy(start, wherey);
    for j := 1 to trunc(v[i] * mult) do write(#176);
    writeln;
  end;

end;

var
  i: integer;
  a, b: tm;

begin
  clrscr;
  writeln('Neotsortirovannyu massiv:');
  randomize;

  for i := 1 to n do a[i]:=random(100);
  print_array(a);

  fillchar(data, sizeof(data), 0);

  b := a;
  vybor(b, data[1][1], data[2][1]);
  b := a;
  pr_vkl(b, data[1][2], data[2][2]);
  b := a;
  quicksort(b, data[1][3], data[2][3]);

  show_gist('perestanovki', names, data[1]);
  writeln;
  show_gist('sravneniya', names, data[2]);

end.