Быстрая сортировка (quicksort) иначе называется сортировкой Хоара. Её идея предельно проста: в массиве выбирают некий опорный элемент (pivot), разбивают массив на две части: слева элементы меньше опорного, справа — больше. Затем процесс рекурсивно повторяется для левой и правой частей массива.

Существуют разные модификации быстрой сортировки и способы её реализации. В данном варианте в функцию передаётся массив и индексы крайних элементов: quickSort(data, 0, n- 1);. В другом варианте можно было бы передавать адрес начала массива и его размер: quickSort(data, n);.

Обратим внимание на два фрагмента из кода, который расположен далее. В каждом рекурсивном вызове водятся l = left; и r = right;, они хранят индексы крайнего левого и крайнего правого элементов.

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

while (l <= r && data[l] < pivot) 

{

    ++l; 

}

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

while (r >= l && data[r] > pivot) 

{

    --r; 

}

Так находят два элемента, которые нужно поменять местами, и продолжают до тех пор, пока массив не разделится на две части (меньше опорного и больше опорного).

Опорный элемент можно выбирать по-разному: элемент из центра массива, элемент с того или иного края, среднее арифметическое между крайними, случайный элемент и т. д. Обратите внимание, что переключатель ниже меняет одну строку в коде.

function quickSort(data[], left, right)
{
    pivot = data[(left + right) / 2];
    l = left, r = right;
    while (l <= r)
    {
        while (l <= r && data[l] < pivot) 
        {
            ++l; 
        }
        while (r >= l && data[r] > pivot) 
        {
            --r; 
        }
        if (l == r && l == left) 
        {
            ++l; 
        }
        if (l == r && l == right) 
        {
            --r; 
        }
        if (l < r) 
        {
            swap(data[l], data[r]); 
            ++l; 
            --r; 
        }
        else
        {
            break;
        }
    }
    if (r - left + 1 >= 2) 
    {
        quickSort(data, left, r); 
    }
    if (right - r >= 2) 
    {
        quickSort(data, r + 1, right); 
    }
}