Метод быстрой сортировки был разработан Ч. Ф. Р. Хоаром и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки.

В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве "основы" и затем весь массив разбивается на две части. Одну часть составляют все элементы, равные или большие "основы", а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован. Например, для массива "fedacb" при использовании в качестве значения разбиения "d" будут получены следующие проходы при выполнении быстрой сортировки:

исходное состояние: f e d a c b;

первый проход: d c a d e f;

второй проход: a b c d e f.

Этот процесс продолжается для каждой части "abc" и "def". Фактически этот процесс имеет рекурсивную природу. И действительно, наиболее "аккуратно" быстрая сортировка реализуется посредством рекурсивного алгоритма. Выбор значения разбиения можно сделать двумя способами. Это значение можно выбирать случайным образом или путем усреднения небольшого числа значений, выбранных из массива. Для оптимальной сортировки требуется выбрать значение, которое будет находиться в точности посередине всех элементов.

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

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

{ быстрая сортировка }

procedure QuickSort(var item: DataArray; count:integer);

procedure qs(l, r: integer; var it: DataArray);

var

i, j: integer;

x, y: DataItem;

begin

i:=l; j:=r;

x:=it[(l+r) div 2];

repeat

while it[i]<x do i := i+1;

while x<it[j] do j := j-1;

if y<=j then

begin

y := it[i];

it[i] := it[j];

it[j] := y;

i := i+1; j := j-1;

end;

until i>j;

if l<j then qs(l, j, it);

if l<r then qs(i, r, it)

end;

begin

qs(1, count, item);

end; { конец быстрой сортировки }

В данном примере процедура быстрой сортировки обращается к основной процедуре сортировки с именем "qs". Это обеспечивает доступ к данным "item" и "count" при всех вызовах "qs".

Можно считать, что число операций сравнения равно n*log2n, а число операций обмена равно приблизительно n/6*log2n. Эти характеристики значительно лучше характеристик рассмотренных ранее сортировок.

Однако, следует иметь в виду одно неприятное свойство быстрой сортировки. Если выбираемое для разбиения значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную с временем выполнения n. Однако на практике этот случай не встречается.