Швидке сортування

Швидке сортування (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.

Дивіться також: