Постановка проблемы: есть набор неотсортированных данных. Необходимо произвести сортировку по возрастанию/убыванию, то есть упорядочивание однотипных элементов.

Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию (наш случай в разборе), то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.

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

Непосредственно сам алгоритм:

  1. Выбираем опорный элемент v - как правило, берут середину рассматриваемого отрезка
  2. Разбиваем массив на 3 части:
  3. В конце концов, просмотры слева-направо и справа-налево сходятся в одной точке j, которая нам разделит рассматриваемый массив на два подмассива. Повторяем рекурсивно алгоритм уже для них, пока не дойдём до массива из 1 элемента - это контролируется условием if l < r в основной функции quicksort.
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.