program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;

type
   NArr = array of Integer;

procedure Output(Arr: NArr);
var
   i: Integer;
begin
   Writeln('Отсортированный массив : ');
   for i := 0 to High(Arr) do
      Write(Arr[i],' ');
end;


procedure BinaryInsertionSorting(var Arr: NArr);
var
   LeftEdge, RightEdge : Integer;
   Mid: Integer;
   i, j, ArrElement: Integer;
begin
   for i := 1 to High(Arr) do
   begin
      if Arr[i - 1] > Arr[i] then
      begin
         ArrElement := Arr[i];
         LeftEdge := 0;
         RightEdge := i - 1;
         repeat
            Mid := (LeftEdge + RightEdge ) div 2;
            if Arr[Mid] < ArrElement then
               LeftEdge := Mid + 1
            else
               RightEdge := Mid - 1;
         until LeftEdge > RightEdge;
         for j := i - 1 downto LeftEdge do
            Arr[j + 1] := Arr[j];
            Arr[LeftEdge] := ArrElement;
      end;
   end;
   Output(Arr);
end;


procedure BoobleSort(var Arr: NArr);
var
   i, Temp: Integer;
   Sort: Boolean;
begin
   Sort := True;
   while Sort do
   begin
      Sort := False;
      for i := 0 to High(Arr) - 1 do
      if Arr[i] > Arr[i + 1] then
         begin
            Sort := True;
            Temp := Arr[i];
            Arr[i] := Arr[i + 1];
            Arr[i + 1] := Temp;
         end;
   end;
   Output(Arr);
end;


procedure ShakerSort(var Arr: NArr);
var
   i, j: Integer;
   Mid, Temp: Integer;
   Min, Max : Integer;
begin
   Mid := High(Arr) div 2;
   for i := 1 to Mid do
   begin
      if Arr[i] > Arr[i+1] then
      begin
         Min := i + 1;
         Max := i;
      end
      else
      begin
         Min := i;
         Max := i + 1;
      end;
      for j := i + 2 to (High(Arr) - i + 1) do
      if Arr[j] > Arr[Max] then
         Max := j
      else
         if Arr[j] < Arr[Min] then
         begin
            Min := j;
            Temp := Arr[i];
            Arr[i] := Arr[Min];
            Arr[Min]:= Temp;
         end;
         if Max = i then
         begin
            Max := min;
            Temp := Arr[High(Arr) - i + 1];
            Arr[High(Arr) - i + 1] := Arr[Max];
            Arr[max]:= Temp;
         end;
   end;
   Output(Arr);
end;

var
   Arr: NArr;
   Size, Option: Integer;
   i: Integer;
begin
   Write('Введите размер массива : ');
   Readln(Size);
   SetLength(Arr, Size);
   Writeln('Введите элементы массива :');
   for i := 0 to High(Arr) do
      Read(Arr[i]);
   Writeln('Выберете сортировку : ');
   Readln(Option);
   case Option of
      1 : BinaryInsertionSorting(Arr);
      2 : BoobleSort(Arr);
      3 : ShakerSort(Arr);
      else
         BinaryInsertionSorting(Arr);
   end;
end.