Записки программиста Программирование и не только

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

Продолжаю публиковать алгоритмы. Уже есть Сортировка Шелла

А сегодня у нас: Быстрая сортировка (англ. quicksort)

ПедиВикия:

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

Алгоритм.

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
   2.1.    два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;
   2.2.    вычисляется опорный элемент m;
   2.3.    индекс l последовательно увеличивается до m или до тех пор, пока l-й элемент не превысит опорный;
   2.4.    индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного;
   2.5.    если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент;
   2.6.    если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.

Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты.

И, наконец, мой вариант реализации:

void quickSort(int l, int h, arr &mArray)
{
	int i = l;
	int j = h;
	int mid = mArray.at((l + h) / 2);
	do
	{
		while (mArray.at(i) < mid) ++i;
		while (mArray.at(j) > mid) --j;
		if (i < = j)
		{
			if (i < j)
				swap(mArray.at(i),mArray.at(j));
			i++;
			j--;
		}
	} while (i <= j);
	if (l < j) quickSort(l, j, mArray);
	if (i < h) quickSort(i, h, mArray);
}