Классические сортировки и их производительность

Наиболее известные простые алгоритмы сортировок - это сортировка выбором, пузырьковая сортировка и сортировка вставками. Сравним их производительность.

Код сортировки выбором

procedure SortByChoice(a: array of integer);
begin
  for var i := 0 to a.Length-2 do
  begin
    var min := a[i];
    var imin := i;
    for var j := i + 1 to a.Length-1 do
      if a[j] < min then
      begin        
        min := a[j];
        imin := j;
      end;  
    Swap(a[imin],a[i]);
  end;
end;

Код пузырьковой сортировки

procedure BubbleSort(a: array of integer);
begin
  for var i := 1 to a.Length-1 do
    for var j := a.Length-1 downto i do
      if a[j] < a[j-1] then
        Swap(a[j], a[j-1]);
end;

Код сортировки вставками

procedure SortByInsert(a: array of integer);
begin
  for var i:=1 to a.Length-1 do
  begin
    var x := a[i];
    var j := i - 1;
    while (j >= 0) and (x < a[j]) do
    begin
      a[j+1] := a[j];
      j -= 1;
    end;
    a[j+1] := x;
  end;
end;

Основная программа для определения производительности

uses Utils;
// процедуры сортировок
begin
  var n := 50000;
  var a := ArrRandomInteger(n,0,integer.MaxValue-1);
  var b := Copy(a);
  Benchmark(procedure -> SortByChoice(b),1).Println;
  b := Copy(a);
  Benchmark(procedure -> BubbleSort(b),1).Println;
  b := Copy(a);
  Benchmark(procedure -> SortByInsert(b),1).Println;
  b := Copy(a);
  Benchmark(procedure -> Sort(b),1).Println;
end.

В конце - как мы видим - для сравнения - вызов процедуры Sort(a) из стандартной библиотеки

Результаты

Выводы. Сортировка выбором по сравнению с двумя другими сортировками - самая производительная. Пузырьковая сортировка в 5 раз более медленная. Однако все приведенные сортировки имеют квадратичную сложность и неэффективны на больших объёмах данных. Уже при n=50000 время вычислений измеряется секундами. Стандартная сортировка имеет сложность n*log(n) и существенно более производительная. При n=50000 она работает за миллисекунду.