Сортировка массива

program test;
uses crt;
var
  arr : array[1..20] of integer;
  i, j, t : integer;
begin
randomize;
for i := 1 to 20 do 
begin
  arr[i] := -100 + random(201);
  write(arr[i], ' ');
end;
writeln;
for i := 1 to 19 do
begin
  for j := i + 1 to 20 do
  begin
    if arr[i] > arr[j] then
    begin
    t := arr[i];
    arr[i] := arr[j];
    arr[j] := t;
    end;
  end;
end;
for i := 1 to 20 do
begin
write(arr[i], ' ');
end;
readln;
end.

procedure Swap(var a, b: integer);
  begin
    var c:=a;
    a:=b;
    b:=c;
  end;

{
За каждый проход элементы последовательно сравниваются попарно и, 
если порядок в паре неверный, выполняется обмен элементов. 
Проходы по массиву повторяются N-1 раз или до тех пор, 
пока на очередном проходе не окажется, что обмены больше не нужны, 
что означает — массив отсортирован. 
При каждом проходе алгоритма по внутреннему циклу, 
очередной наибольший элемент массива ставится на своё место 
в конце массива рядом с предыдущим наибольшим элементом, 
а наименьший элемент перемещается на одну позицию к началу массива 
(«всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
 
 
Сложность: O(n*n)
}
 
procedure sort(a: array of integer);
begin
  for var i:=0 to a.Length-2 do
    for var j:=i+1 to a.length-1 do
      if a[i]>a[j]
        then swap(a[i],a[j]);
end;

{
На каждом шаге алгоритма мы выбираем один из элементов входных данных и 
вставляем его на нужную позицию в уже отсортированном списке, до тех пор, 
пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; 
может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), 
элементы вставляются по порядку их появления во входном массиве.
 
Сложность: O(n*n)
}
 
procedure sort(a: array of integer);
begin
  for var i:=1 to a.Length-1 do
    begin
      var j:=i-1;
      var key:=a[i];
      while (j>0) and (key<a[j]) do
        begin
          a[j+1]:=a[j];
          dec(j);
        end;
    end;    
end;

{
Алгоритм сортировки, похожий на сортировку вставками, 
но в отличие от последней перед вставкой на нужное место 
происходит серия обменов, как в сортировке пузырьком.
 
Сложность: O(n*n)
}
 
procedure sort(a: array of integer);
begin
  for var i:=1 to a.Length-1 do
    begin
      var j:=i;
      while (j>0) and (a[j]<a[j-1]) do
        begin
          swap(a[j],a[j-1]);
          dec(j);
        end;
    end;    
end;

{
На каждом шаге основного цикла рассматривается массив a[Left]÷a[Right], 
после выполнения двух внутренних циклов минимальный и максимальный элемент 
в исходном массиве перетекают к краям, минимальный в — a[Left], максимальный — в a[Right]. 
Пусть максимальный элемент имеет индекс k, тогда массив можно изобразить так: 
a[Left],a[1],..,a[k-1],A[k],a[k+1],..,a[Right];
После сравнения A[k] с a[k+1] значение A[k] перейдет в k+1-ую ячейку,
после сравнения k+1-ой c k+2-ой – в k+2-eю,и так далее,
пока он не сместится в крайне правое положение с индексом Right. 
Аналогично для минимального. После выполнения цикла по всем подмассивам он отсортируется. 
 
Сложность: O(n*n)
}
 
procedure sort(a: array of integer);
begin
  var first:=0;
  var last:=a.Length-1;
  while first < last do
    begin
      for var i:= first to last-1 do
        if a[i]>a[i+1] 
          then swap(a[i],a[i+1]);
      dec(last);
      for var i:= last downto first+1 do
        if a[i]<a[i-1]
          then swap(a[i],a[i-1]);
      inc(first);
    end;
end;

{
Шаги алгоритма:
 
    1. находим номер минимального значения в текущем списке
    2. производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
    3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Сложность: O(n*n)
}
 
procedure sort(a: array of integer);
begin
  var current: integer;
  for var i:=0 to a.Length-2 do
    begin
      current:=i;
      for var j:=i+1 to a.length-1 do
        if a[current]>a[j]
          then current:=j;
      swap(a[current],a[i]);
    end;
end;

{
1. Выстраиваем элементы массива в виде сортирующего дерева
 
2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. 
То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. 
Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. 
Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. 
Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.
 
Сложность: O(n log n)
}
 
procedure heapify(a: array of integer; i,max: integer);
begin
    var temp:=i;
    if (2*i<max) and (a[2*i]>a[i-1]) and (a[2*i]>a[2*i-1])
      then temp:=2*i+1 else
    if (2*i-1<max) and (a[2*i-1]>a[i-1])
      then temp:=2*i;
    if temp<>i then
      begin
        swap(a[i-1],a[temp-1]);
        heapify(a,temp,max);
      end;
end;
procedure sort(a: array of integer);
begin
  var max:=a.Length;
  //generate tree
  for var i:=a.Length downto 1 do
    heapify(a,i,max);
  //sorting
  while max>1 do
    begin
      swap(a[0],a[max-1]);
      dec(max);
      heapify(a,1,max);
    end;
end;