uses crt const 10 type index item record key integer end mas array of

uses crt;
const n=10;
type index = 0..n;
     item = record
                key:integer;
            end;
     mas = array[0..n] of item;
var a:mas;
    t:byte;
{------------------------------------------------------------}
Procedure initArray(var arr:mas);
var i:integer;
begin
    for i:=1 to n do
        arr[i].key:=random(20)-10;
end;
{------------------------------------------------------------}
Procedure printArray(arr:mas);
var i:integer;
begin
    for i:=1 to n do
        write(arr[i].key:2, ' ');
    writeln;
end;
{------------------------------------------------------------}
procedure straightInsertion(var a:mas);
var i,j,count:integer;
    x:item;
begin
    count:=0;
    for i:=2 to n do
    begin
        x:=a[i];
        j:=i-1;

        while (j>=1) and (x.key < a[j].key) do
        begin
            a[j+1]:=a[j];
            j:=j-1;
        end;
        a[j+1]:=x;
        inc(count);
    end;
    writeln('Count: ',count);
end;
{------------------------------------------------------------}
procedure straightSelection(var a:mas);
var i,j,min:index;
    x:item;
    count:integer;
begin
    count:=0;
    for i:=1 to n-1 do
    begin
        min:=i;
        x:=a[min];
        for j:=i+1 to n do
            if a[j].key < x.key then
            begin
                min:=j;
                x:=a[j];
            end;
        a[min]:=a[i];
        a[i]:=x;
        inc(count);
    end;
    writeln('Count: ',count);
end;
{------------------------------------------------------------}
procedure bubleSort(var a:mas);
var i,j:index;
    x:item;
    count:integer;
begin
    count:=0;
    for i:=2 to n do
        for j:=n downto i do
            if a[j-1].key > a[j].key then
            begin
                x:=a[j-1];
                a[j-1]:=a[j];
                a[j]:=x;
                inc(count);
            end;
    writeln('Count: ',count);
end;
{------------------------------------------------------------}
procedure shakerSort(var a:mas);
var k,j,left,right:index;
    x:item;
    count:integer;
begin
    left:=2;
    right:=n;
    k:=n;
    count:=0;
    repeat
        {right to left}
        for j:=right downto left do
            if a[j-1].key > a[j].key then
            begin
                x:=a[j-1];
                a[j-1]:=a[j];
                a[j]:=x;
                k:=j;
                inc(count);
            end;
        {write('right to left: ');
        printArray(a); }
        left:=k+1;
        {left ot right}
        for j:=left to right do
            if a[j-1].key > a[j].key  then
            begin
                x:=a[j-1];
                a[j-1]:=a[j];
                a[j]:=x;
                k:=j;
                inc(count);
            end;
        {write('left to right: ');
        printArray(a); }
        right:=k-1;
    until left > right;
    writeln('Count: ',count);
end;
{------------------------------------------------------------}
procedure quickSort(var a:mas; lo,hi:integer);
    var count:integer;
    procedure sort(left,right:index);
    var i,j:index;
        x,y:item;
        {count:integer;}
    begin
        i:=left;
        j:=right;
        x:=a[(left+right) div 2];
        repeat
            while (a[i].key < x.key) do inc(i);
            while (a[j].key > x.key) do dec(j);
            if (i<=j) then
            begin
                if a[i].key > a[j].key then
                begin
                    y:=a[i];
                    a[i]:=a[j];
                    a[j]:=y;
                end;
                inc(i);
                dec(j);
                inc(count);
            end;
        until i>j;
        if left < j then sort(left,j);
        if i < right then sort(i,right);

    end;
begin
        count:=0;
        sort(lo,hi);
        writeln('Count: ',count);
end;

{------------------------------------------------------------}
begin
    clrscr;
    {randomize;}
    initArray(a);
    printArray(a);
    write('Enter the type of sort: ');
    readln(t);
    case t of
        1: straightInsertion(a);
        2: straightSelection(a);
        3: bubleSort(a);
        4: shakerSort(a);
        5: quickSort(a,1,n);
        else writeln('wrong type');
    end;
    printArray(a);
    readkey;
end.