Быстрая сортировка, сортировка Хоара (), часто называемая (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Общее описание
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного в том числе своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы (таким образом улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов).
Общая идея алгоритма состоит в следующем:
Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность (см. ниже). Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие»Очевидно, что после такой перестановки для получения отсортированного массива не понадобится перемещать ни один из элементов между получившимися отрезками, то есть достаточно будет произвести сортировку «меньшего» и «большего» отрезков как самостоятельных массивов.. Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения (см. ниже).
Хоар разработал этот метод применительно к машинному переводу; словарь хранился на магнитной ленте, и сортировка слов обрабатываемого текста позволяла получить их переводы за один прогон ленты, без перемотки её назад. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе, где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника.
Алгоритм
Общий механизм сортировки Быстрая сортировка относится к алгоритмам «разделяй и властвуй».
Алгоритм состоит из трёх шагов: Выбрать элемент из массива. Назовём его опорным. Разбиение: перераспределение элементов в массиве таким образом, что элементы, меньшие опорного, помещаются перед ним, а большие или равные — после. Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.
В наиболее общем виде алгоритм на псевдокоде (где A — сортируемый массив, а low и high — соответственно, нижняя и верхняя границы сортируемого участка этого массива) выглядит следующим образом:
algorithm quicksort(A, low, high) is if low < high then p:= partition(A, low, high) quicksort(A, low, p - 1) quicksort(A, p, high)
Здесь предполагается, что массив A передаётся по ссылке, то есть сортировка происходит «на том же месте», а неописанная функция partition возвращает индекс опорного элемента.
Для выбора опорного элемента и операции разбиения существуют разные подходы, влияющие на производительность алгоритма.
Возможна также следующая реализация быстрой сортировки: algorithm quicksort(A) is if A is empty return A pivot:= A.pop() (извлечь последний или первый элемент из массива) lA:= A.filter(where e <= pivot) (создать массив с элементами меньше опорного) rA := A.filter(where e > pivot) (создать массив с элементами больше опорного) return quicksort(lA) + [pivot] + quicksort(rA) (вернуть массив, состоящий из отсортированной левой части, опорного и отсортированной правой части).
На практике она не используется, а служит лишь в образовательных целях, так как использует дополнительную память, чего можно избежать.
Выбор опорного элемента В ранних реализациях, как правило, опорным выбирался первый элемент, что снижало производительность на отсортированных массивах. Для улучшения эффективности может выбираться средний, случайный элемент или (для больших массивов) медиана первого, среднего и последнего элементов. Медиана всей последовательности является оптимальным опорным элементом, но её вычисление слишком трудоёмко для использования в сортировке.
Выбор опорного элемента по медиане трёх для разбиения Ломуто: mid := (low + high) / 2 if A[mid] < A[low] swap A[low] with A[mid] if A[high] < A[low] swap A[low] with A[high] if A[high] < A[mid] swap A[high] with A[mid] pivot:= A[mid]
Разбиение Ломуто Данный алгоритм разбиения был предложен Нико Ломуто и популяризован в книгах Бентли (Programming Pearls) и Кормена (Введение в алгоритмы). В данном примере опорным выбирается последний элемент. Алгоритм хранит индекс в переменной i. Каждый раз, когда находится элемент, меньше или равный опорному, индекс увеличивается и элемент вставляется перед опорным. После разбиения опорный элемент окажется в позиции i — на границе между двумя подмножествами. Хоть эта схема разбиения проще и компактнее, чем схема Хоара, она менее эффективна и используется в обучающих материалах. Сложность данной быстрой сортировки возрастает до , когда массив уже отсортирован или все его элементы равны. Существуют различные методы оптимизации данной сортировки: алгоритмы выбора опорного элемента, использование сортировки вставками на маленьких массивах. В данном примере сортируются элементы массива от до (включительно):
algorithm partition(A, low, high) is pivot := A[high] i := low for j := low to high do if A[j] ≤ pivot then swap A[i] with A[j] i := i + 1 swap A[i] with A[high] return i
Сортировка всего массива может быть выполнена с помощью выполнения .
Схема Хоара Данная схема использует два индекса (один в начале массива, другой — в конце), которые приближаются друг к другу, пока не найдётся пара элементов, где один больше опорного и расположен перед ним, а второй — меньше и расположен после. Эти элементы меняются местами. Обмен происходит до тех пор, пока индексы не пересекутся. Алгоритм возвращает последний индекс. Схема Хоара эффективнее схемы Ломуто, так как происходит в среднем в три раза меньше обменов (swap) элементов и разбиение эффективнее, даже когда все элементы равны. Подобно разбиению Ломуто, данная схема также показывает эффективность в , когда входной массив уже отсортирован. Сортировка с использованием данной схемы нестабильна. Следует заметить, что конечная позиция опорного элемента необязательно совпадает с возвращённым индексом. Псевдокод: algorithm quicksort(A, lo, hi) is if lo < hi then p:= partition(A, lo, hi) quicksort(A, lo, p) quicksort(A, p + 1, hi) algorithm partition(A, low, high) is pivot:= A[(low + high) / 2] i:= low j:= high loop forever while A[i] < pivot i:= i + 1 while A[j] > pivot j:= j - 1 if i >= j then return j swap A[i++] with A[j--] В книге упоминается, что такая реализация алгоритма имеет «много тонких моментов». Вот один из них: выбор в качестве опорного элемента уже существующего элемента в массиве может привести к переполнению стека вызовов из-за того, что номер элемента вычисляется как среднее, а это не целое число. Поэтому логичнее в данном алгоритме выбирать в качестве опорного элемента среднее значение между начальным и конечным элементом: pivot := A[(low + high) / 2]Но нет никаких оснований выбирать в качестве опорного элемента A[ (low + high) / 2]. Оптимальным может оказаться любой элемент от low до high с равной вероятностью. Тем более, что A[ (low + high) / 2] — это не среднее значение, а просто элемент из середины массива. Гораздо разумнее выбирать случайный элемент A[ random( low .. high) ]. Это гарантирует, что никто злонамеренно не сможет соорудить массив, который этот алгоритм введёт в очень длинный цикл с переполнением стека. В этом случае вероятность неудачи при сортировке массива из примерно 37 000 элементов, по самой завышенной оценке, составляет примерно 10 в минус 16 степени, что на 3 порядка меньше, чем вероятность выхода из строя компьютера в результате прямого попадания в него метеорита. Неудачей считается число итераций (полного перебора всех элементов массива с целью сравнения и перестановки) более чем 200.
Повторяющиеся элементы Для улучшения производительности при большом количестве одинаковых элементов в массиве может быть применена процедура разбиения массива на три группы: элементы меньшие опорного, равные ему и больше него (Бентли и Макилрой называют это «толстым разбиением». Данное разбиение используется в функции в седьмой версии Unix). Псевдокод:
algorithm quicksort(A, low, high) is if low < high then p := pivot(A, low, high) left, right := partition(A, p, low, high) // возвращается два значения quicksort(A, low, left) quicksort(A, right, high) Быстрая сортировка используется в стандарте языка C++, в частности, в методе sort структуры данных list# include <iostream> # include <list>
int main() { // quick sort std::list<int> list; const int N = 20; for (int i = 0; i < N; i++) { if (i % 2 == 0) list.push_back(N - i); else list.push_front(N - i); } for (std::list<int>::iterator it = list.begin(); it != list.end(); it++) { std::cout << (*it) << " "; } std::cout << std::endl; list.sort(); for (std::list<int>::iterator it = list.begin(); it != list.end(); it++) { std::cout << (*it) << " "; } //quick sort end std::cout << std::endl; //sort greater list.sort(std::greater<int>()); for (std::list<int>::iterator it = list.begin(); it != list.end(); it++) { std::cout << (*it) << " "; } std::cout << std::endl; //sort greater end
std::cin.ignore(); }
Оценка сложности алгоритма Ясно, что операция разделения массива на две части относительно опорного элемента занимает время . Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.
Лучший случай. В наиболее сбалансированном варианте при каждой операции разделения массив делится на две одинаковые части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит . В результате количество сравнений, совершаемых быстрой сортировкой, было бы равно значению рекурсивного выражения , что даёт общую сложность алгоритма . Среднее. Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно. Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 % и 25 % от исходного, глубина рекурсии будет равна , а это по-прежнему даёт сложность . Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами.