Алгоритм быстрой сортировки обладает привлекательными особенностями: он принадлежит к категории обменных (in-place) сортировок (т.е., требует всего лишь небольшого вспомогательного стека), на выполнение сортировки N элементов в среднем затрачивается время, пропорциональное N log N и для него характерны исключительно короткие внутренний циклы.
Его недостатком является то, что он неустойчив, для его выполнения в наихудшем случае требуется N2 операций, он хрупок в том смысле, что даже простая ошибка в реализации может пройти незамеченной и вызвать ошибки в работе алгоритма на некоторых видах массивов.
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй". Он делит сортируемый массив на две части, затем сортирует эти части независимо друг от друга. Суть метода заключается в процессе разбиения массива, который переупорядочивает массив таким образом, что выполняются следующие условия:
Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве.
Ни один из элементов a[i],..., a[i-l] не превышает a[i].
Ни один из элементов a[i+l],..., а[г] не является меньшим a[i].
Быстрая сортировка представляет собой рекурсивный процесс разбиения массива на части: мы разбиваем его, помещая некоторый (разделяющий) элемент в свою окончательную позицию и выполняем перегруппировку массива таким образом, что элементы, меньшие по значению, остаются слева от разделяющего элемента, а элементы, большие по значению, — справа. Далее мы рекурсивно сортируем левую и правую части массива. Конечным результатом такого вида сортировки является полностью отсортированный массив.
Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент а[r], лучше чтобы r был ближе к середине — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Мы продолжаем дальше в том же духе, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.
Листинг: Алгоритм быстрой сортировки
// Шаблон quicksort задает рекурсивную функцию сортировки
// элементов массива методом быстрой сортировки.
// - Key - класс, задающий тип элементов массива;
// - array - упорядочиваемый массив;
// -.low, high - индексы, задающие диапазон сортировки.
template <class Кеу>
void quicksort(Key * array, int low, int high) {
// Предполагается, что в начале работы low <= high
// В результате сортировки получается упорядоченный фрагмент
// массива в диапазоне от low до high
int pLow = low,
pHigh - high; // указатели концов фрагмента массива
Key elem = array[low]; // выбранный произвольный элемент
while (pLow != pHigh) {
// 1. Просмотр элементов массива снизу
while (pHigh > pLow && array[pHigh] >= elem) pHigh--;
if (pHigh > pLow) {
array[pLow] =array[pHigh]; // Обмен местами элементов
// 2. Просмотр элементов массива "сверху"
while (pLow < pHigh && array[pLow] <= elem) pLow++;
array[pHigh] = array [pLow]; // Еще один обмен
}
}
// Теперь указатели pLow и pHigh столкнулись, массив разделен,
array[pLow] = elem;
// Далее следуют рекурсивные вызовы функции для двух половинок
if (pLow - low > 1) quickSort<Key>(array, low, pLow-1);
if (high - pHigh > 1) quickSort<Key>(array, pHigh+1, high);
}