Быстрая сортировка

DP.20 · Алгоритмы

Задача

Отсортировать массив методом Хоара.

Алгоритм

Выбирается опорный элемент, массив делится на меньшие и большие, каждая часть сортируется рекурсивно.

Исходный код

⇩ Скачать 20-bystraya-sortirovka.dpr

program BystrayaSortirovka;
{$mode delphi}{$apptype console}
var a: array[0..9] of Integer = (5, 2, 9, 1, 7, 3, 8, 4, 6, 0);
procedure QSort(var arr: array of Integer; lo, hi: Integer);
var i, j, p, t: Integer;
begin
  i := lo; j := hi; p := arr[(lo + hi) div 2];
  repeat
    while arr[i] < p do Inc(i);
    while arr[j] > p do Dec(j);
    if i <= j then begin
      t := arr[i]; arr[i] := arr[j]; arr[j] := t;
      Inc(i); Dec(j);
    end;
  until i > j;
  if lo < j then QSort(arr, lo, j);
  if i < hi then QSort(arr, i, hi);
end;
var k: Integer;
begin
  QSort(a, 0, High(a));
  for k := 0 to High(a) do Write(a[k], ' ');
  WriteLn;
  ReadLn;
end.

Пояснения

Средняя сложность O(n log n). Параметр var array of Integer — открытый массив по ссылке.