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

Анимированная схема алгоритма

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

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

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

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

Алгоритм

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы (Алгоритм, приведённый ниже, неверен: если в массиве оказалось два элемента, равных опорному и индексы l и r достигли их одновременно, то шаг 2.6 не изменяет массива при обмене этих элементов и алгоритм оказывается в вечном цикле. В англоязычной версии статьи приведён правильно действующий псевдо-код):

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

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

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

//алгоритм на языке java public static void qSort(int[] A, int low, int high) { int i = low; int j = high; int x = A[(low+high)/2]; // x - опорный элемент посредине между low и high do { while(A[i] < x) ++i; // поиск элемента для переноса в старшую часть while(A[j] > x) --j; // поиск элемента для переноса в младшую часть if(i <= j){ // обмен элементов местами: int temp = A[i]; A[i] = A[j]; A[j] = temp; // переход к следующим элементам: i++; j--; } } while(i < j); if(low < j) qSort(A, low, j); if(i < high) qSort(A, i, high); }

// Алгоритм на языке C/C++ // Вариант реализации быстрой сортировки наподобие qsort из стандартной библиотеки typedef int (*PTF)(const void *, const void *); void qqsort(void* base, size_t n, size_t sz, PTF cmp) { if (n <= 1) { return; } char* b = (char*)base; char* bm = b + (n/2)*sz; char* tm = (char*)malloc(sizeof(char)*sz); // Скопируем в "буфер" центральный элемент. for (int k = 0; k < sz; ++k) { tm[k] = bm[k]; } char* lb = b; // Вычислим адрес крайнего левого элемента. char* rb = b + (n-1)*sz; // Вычислим адрес крайнего правого элемента. while (lb < rb) { while (cmp(tm, lb) > 0) { lb += sz; } while (cmp(tm, rb) < 0) { rb -= sz; } if (lb < rb) { // Переместим элементы. for (int k = 0; k < sz; ++k) { char tmp = lb[k]; lb[k] = rb[k]; rb[k] = tmp; } lb += sz; rb -= sz; } else if (lb == rb) { lb += sz; rb -= sz; } } free(tm); qqsort(b, (rb - b)/sz + 1, sz, cmp); qqsort(lb, ((b + n*sz) - b)/sz - (lb - b)/sz, sz, cmp); }

//алгоритм на языке pascal //при первом вызове 2-ой аргумент должен быть равен 0 //3-ий аргумент должен быть равен числу элементов массива - 1 procedure qSort(var ar: array of real; low, high: integer); var i, j: integer; m, wsp: real; begin i:=low; j:=high; m:=ar[(i+j) div 2]; repeat while ar[i]<m do Inc(i); //Инкремент i. Эквивалентно коду i:=i+1, но компилируется оптимальнее while ar[j]>m do Dec(j); //Декремент j. Эквивалентно коду j:=j-1; if i<=j then begin wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp; Inc(i); Dec(j); end; until i>j; if low<j then qSort(ar, low, j); if i<high then qSort(ar, i, high); end;

//алгоритм на языке Visual Basic //при первом вызове 2-ой аргумент должен быть равен 1 (или 0, в зависимости от базы) //3-ий аргумент должен быть равен числу элементов массива (или числу элементов массива - 1, если база = 0) Sub qSort(ByRef ar() As Double, ByVal low As Integer, ByVal high As Integer) Dim i, j As Integer Dim m, wsp As Double i = low j = high m = ar((i + j) \ 2) Do Until i > j Do While ar(i) < m i = i + 1 Loop Do While ar(j) > m j = j - 1 Loop If i <= j Then wsp = ar(i) ar(i) = ar(j) ar(j) = wsp i = i + 1 j = j - 1 End If Loop If low < j Then Call qSort(ar, low, j) If i < high Then Call qSort(ar, i, high) End Sub

%% алгоритм на языке Erlang qsort([]) -> []; qsort([Pivot|Rest]) -> qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).

Оценка эффективности

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод.

• Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C_N = 2C_N/2+N, что в явном выражении дает примерно N lg N сравнений. Это дало бы наименьшее время сортировки.
• Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
  На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n lg n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2C_N/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C_N = N lg N.
• Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
  Худший случай даёт O(n²) обменов. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Улучшения

• При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(n lg n).
• Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов). Такой выбор также направлен против худшего случая.
• Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит log₂n, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.
• Разбивать массив не на две, а на три части (см. Dual Pivot Quicksort).

Достоинства и недостатки

Достоинства:

• Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
• Прост в реализации.
• Требует лишь $O(\lg n)$ дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае $O(n)$ памяти)
• Хорошо сочетается с механизмами кэширования и виртуальной памяти.
• Существует эффективная модификация (алгоритм Седжвика) для сортировки строк — сначала сравнение с опорным элементом только по нулевому символу строки, далее применение аналогичной сортировки для «большего» и «меньшего» массивов тоже по нулевому символу, и для «равного» массива по уже первому символу.
• Работает на связанных списках и других структурах с последовательным доступом.

Недостатки:

• Сильно деградирует по скорости (до $\Theta(n^2)$) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, используя такие модификации алгоритма, как Introsort, или вероятностно, выбирая опорный элемент случайно, а не фиксированным образом.
• Наивная реализация алгоритма может привести к ошибке переполнения стека, так как ей может потребоваться сделать $O(n)$ вложенных рекурсивных вызовов. В улучшенных реализациях, в которых рекурсивный вызов происходит только для сортировки меньшей из двух частей массива, глубина рекурсии гарантированно не превысит $O(\lg n)$.
• Неустойчив — если требуется устойчивость, приходится расширять ключ.

Литература

• Ананий В. Левитин Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 174-179. — ISBN 5-8459-0987-2
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 198-219. — ISBN 5-8459-0857-4

См. также

• Список алгоритмов сортировки

Ссылки

• Анимированное сравнение алгоритмов сортировки
• Пошаговый разбор быстрой сортировки
• Визуализаторы: [1], [2], [3]