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

Быстрая сортировка (quick sort), или сортировка Хоара - один из самых быстрых алгоритмов сортировки данных.

Алгоритм Хоара является модифицированным вариантом метода прямого обмена. Другие варианты этого метода - Пузырьковая и Шейкерная сортировки, которые, в отличии от QuickSort, не очень эффективны.

Принцип работы алгоритма быстрой сортировки

Идея положенная в основании алгоритма следующая:

  • Необходимо выбрать опорный элемент массива, им может стать любой из элементов, от этого не зависит корректность работы алгоритма;
  • Разбить массив на три непрерывные части, в первой должны содержаться элементы меньше опорного, во второй - равные и в третьей - все элементы больше опорного;
  • Рекурсивно выполнить эту последовательность действий, для отрезков с меньшими и большими значениями, пока в них находиться больше одного элемента.

По скольку метод быстрой сортировки делит массив на части, он относиться к группе алгоритмов разделяй и властвуй.

Программа для быстрой сортировки массива

{$CODEPAGE UTF8}
program Quick_Sort;
const
  arrayLength = 50;
var
  inputArray : array [1..arrayLength] of integer;
  i : integer;

procedure QuickSort(left, right: integer);
var
  newLeft, newRight : integer; //границы массива
  temp, pivot : integer;
begin
  newLeft := left;
  newRight := right;

  {опорный элемент массива}
  pivot := inputArray[(left + right) div 2];

  repeat
    while inputArray[newLeft] < pivot do
      newLeft := newLeft + 1;

    while inputArray[newRight] > pivot do
      newRight := newRight - 1;

    if newLeft <= newRight then
    begin
      {обмен значений}
      temp := inputArray[newLeft];
      inputArray[newLeft] := inputArray[newRight];
      inputArray[newRight] := temp;

      newLeft := newLeft + 1;
      newRight := newRight - 1;
    end;
  until newLeft > newRight;

  {рекурсивный вызов сортировки для "меньших" элементов}
  if left < newRight then
    QuickSort(left, newRight);

  {сортировка - для "больших" элементов}
  if newLeft < right then
    QuickSort(newLeft, right);
end;

begin
  randomize;
  writeln ('Исходный массив: ');
  {заполнение массива случайными числами}
  for i := 1 to arrayLength do
  begin
    inputArray[i] := random(100);
    write (inputArray[i]:4);
  end;
  writeln;
  
  QuickSort(1, arrayLength);

  writeln ('Отсортированный массив: ');
  for i := 1 to arrayLength do
    write (inputArray[i]:4);
  readln;
end.

Смотрите также: