Быстрая сортировка

Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком сэром Тони Хоаром. Один из самых быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов).

Краткое описание алгоритма

• выбрать элемент, называемый опорным;
• сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие;
• повторить рекурсивно для «меньших» и «больших».

Реализация на C (случай массива целых чисел)

#include <iostream>
#include <iterator>

#include <cstdlib>

using std::rand;
using std::swap;

// pivot - "опорный" элемент
// partition - переупорядочивает элементы части массива,
// заданной отрезком [left, right), так что в начале
// следуют элементы меньшие pivot, а в конце - большие;
// возвращает место pivot после переупорядочивания;
int * partition(int * left, int *  right, int pivot) {
	int * store = left; // место для вставки элементов, меньших pivot
	for (int * p = left; p != right; ++p)
		if (*p < pivot)
			swap(*p, *store++);
	return store;
}

void my_qsort(int * arr, int n) {
	if (n <= 1)
		return; // массив в 1 или 0 элементов уже упорядочен
	int * pivotPtr = arr + rand() % n; // случайный выбор опорного элемента
	int newPivotIdx = partition(arr, arr + n, *pivotPtr) - arr;
	my_qsort(arr, newPivotIdx + 1);
	my_qsort(arr + newPivotIdx, n - (newPivotIdx + 1));
}

См. также

• Википедия: Быстрая сортировка