Быстрая сортировка (quick sort), или сортировка Хоара — один из самых быстрых алгоритмов сортировки данных.
Алгоритм Хоара является модифицированным вариантом метода прямого обмена. Другие варианты этого метода — Пузырьковая и Шейкерная сортировки, которые, в отличии от QuickSort, не очень эффективны.
Принцип работы алгоритма быстрой сортировки
Идея положенная в основании алгоритма следующая:
- Необходимо выбрать опорный элемент массива, им может стать любой из элементов, от этого не зависит корректность работы алгоритма;
- Разбить массив на три непрерывные части, в первой должны содержаться элементы меньше опорного, во второй — равные и в третьей — все элементы больше опорного;
- Рекурсивно выполнить эту последовательность действий, для отрезков с меньшими и большими значениями, пока в них находиться больше одного элемента.
По скольку метод быстрой сортировки делит массив на части, он относиться к группе алгоритмов разделяй и властвуй.
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.