Постановка проблемы: есть набор неотсортированных данных. Необходимо произвести сортировку по возрастанию/убыванию, то есть упорядочивание однотипных элементов.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию (наш случай в разборе), то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Выбор опорного элемента не влияет на результат, и поэтому может пасть на произвольный элемент. Тем не менее, наибольшая эффективность алгоритма достигается при выборе опорного элемента, делящего последовательность на равные или примерно равные части.
Непосредственно сам алгоритм:
void quick_sort(int *array, int left, int right) {
int center = 0, i = 0, j = 0;
if (left >= right) return;
i = left;
j = right;
center = array[(left + right) / 2];
while (i <= j) {
while (array[i] < center) i++;
while (array[j] > center) j--;
if (i <= j) {
swap(&array[i], &array[j]);
i++;
j--;
}
}
quick_sort(array, left, j);
quick_sort(array, i, right);
}
int partition(a: T[n], int l, int r)
T v = a[(l + r) / 2]
int i = l
int j = r
while (i ⩽ j) {
while (a[i] < v)
i++
while (a[j] > v)
j--
if (i ⩾ j)
break
swap(a[i++], a[j--])
}
return j
void quicksort(a: T[n], int l, int r)
if l < r
int q = partition(a, l, r)
quicksort(a, l, q)
quicksort(a, q + 1, r)
Для сортировки всего массива необходимо выполнить процедуру
quicksort(a,0,length[a]−1)
Оценка сложности алгоритма:
Каждое разделение требует O(n) операций - в силу того, что мы идем слева-направо и справа-налево, пробегая все элементы текущего отрезка. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике. Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n^2) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, или вообще уже массив изначально отсортирован. В таких случаях у нас всё время массив длины N будет делиться на два подмассива длины 1 и N - 1.