Быстрая сортировка представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой.
Для достижения наибольшей эффективности желательно производить обмен элементов на больших расстояниях. В массиве выбирается некоторый элемент, называемый разрешающим . Затем он помещается в то место массива, где ему полагается быть после упорядочивания всех элементов. В процессе отыскания подходящего места для разрешающего элемента производятся перестановки элементов так, что слева от них находятся элементы, меньшие разрешающего, и справа — большие (предполагается, что массив сортируется по возрастанию).
Тем самым массив разбивается на две части:
- не отсортированные элементы слева от разрешающего элемента;
- не отсортированные элементы справа от разрешающего элемента.
Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя.
Если требуется сортировать больше одного элемента, то нужно
- выбрать в массиве разрешающий элемент;
- переупорядочить массив, помещая элемент на его окончательное место;
- отсортировать рекурсивно элементы слева от разрешающего;
- отсортировать рекурсивно элементы справа от разрешающего.
Ключевым элементом быстрой сортировки является алгоритм переупорядочения .
Рассмотрим сортировку на примере массива:
10, 4, 2, 14, 67, 2, 11, 33, 1, 15.
Для реализации алгоритма переупорядочения используем указатель left на крайний левый элемент массива. Указатель движется вправо, пока элементы, на которые он показывает, остаются меньше разрешающего. Указатель right поставим на крайний правый элемент массива, и он движется влево, пока элементы, на которые он показывает, остаются больше разрешающего.
Пусть крайний левый элемент — разрешающий pivot . Установим указатель left на следующий за ним элемент; right — на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы. 
Движение указателей останавливается, как только встречаются элементы, порядок расположения которых относительно разрешающего элемента неправильный.
Указатель left перемещается до тех пор, пока не покажет элемент больше 10; right движется, пока не покажет элемент меньше 10.
Эти элементы меняются местами и движение указателей возобновляется.
Процесс продолжается до тех пор, пока right не окажется слева от left .
Тем самым будет определено правильное место разрешающего элемента.
Осуществляется перестановка разрешающего элемента с элементом, на который указывает right . 
Разрешающий элемент находится в нужном месте: элементы слева от него имеют меньшие значения; справа — большие. Алгоритм рекурсивно вызывается для сортировки подмассивов слева от разрешающего и справа от него.
Реализация алгоритма быстрой сортировки на Си
Результат выполнения 
Некоторые из представленных здесь реализаций используют в качестве опорного элемента один из крайних элементов подмассива. Эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра, их время работы становится порядка Θ ( n 2 ) <displaystyle Theta (n^<2>)> 
.
В качестве опорного элемента следует выбирать случайный элемент массива, чтобы получить гарантированное время сортировки Θ ( n log n ) <displaystyle Theta (nlog n)> в среднем. В случае, если использование случайных чисел нежелательно, в качестве опорного элемента можно выбрать, например, элемент в середине массива, но такие алгоритмы всё равно будут работать за Θ ( n 2 ) <displaystyle Theta (n^<2>)> времени на некоторых специально-сконструированных массивах.
Содержание
VBA [ править ]
Работает для произвольного массива из n целых чисел.
C# [ править ]
C [ править ]
Работает для произвольного массива из n целых чисел.
Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.
C# [ править ]
C# с обобщёнными типами [ править ]
Тип Т должен реализовывать интерфейс IComparable .
C# с использованием лямбда-выражений [ править ]
C++ [ править ]
Быстрая сортировка на основе библиотеки STL [ править ]
Для вещественных чисел [ править ]
Java [ править ]
Java с инициализацией и перемешиванием массива [ править ]
и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива).
Java без рекурсии, с использованием стека [ править ]
пошаговый алгоритм с возможностью вывода на экран текущего действия
JavaScript [ править ]
Python [ править ]
Через list comprehension:
Joy [ править ]
PHP [ править ]
Haskell [ править ]
Математическая версия — с использованием генераторов:
Данная версия алгоритма является самой короткой из возможных, но тратит слишком много дополнительной памяти. На практике такой алгоритм использоваться не может. Стоит также отметить, что списки — неудачный выбор для реализации быстрой сортировки.
Common Lisp [ править ]
В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" — она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp’а.
Pascal [ править ]
В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его — зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве — он проще и быстрее, хотя, теоретически, может быть хуже.
Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.
Устойчивый вариант (требует дополнительно O(n)памяти)
Быстрая сортировка, нерекурсивный вариант [ править ]
Нерекурсивная реализация быстрой сортировки через управляемый вручную стек. Функции compare и change реализуются в зависимости от типа данных.
Частично рекурсивная реализация [ править ]
Реализация на языке pascal с одной рекурсивной ветвью. После разделения массива меньшая часть сортируется рекурсивным вызовом, а бо’льшая — в цикле. Это гарантирует глубину рекурсии не более lg(N).
Пример реализации алгоритма в объектно-ориентированном стиле с обобщением по типу данных (Generics) [ править ]
В представленной реализации алгоритма быстрой сортировки элементов массива порядок сортировки определяется пользовательской функцией обратного вызова:
которая должна удовлетворять условиям контракта вызова и возвращаемого значения:
Библиотечный модуль [ править ]
Пример использования [ править ]
Prolog [ править ]
Ruby [ править ]
SML [ править ]
This example demonstrates the use of an arbitrary predicate in a functional language.
Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.
Итак, быстрая сортировка, или, по названию функции в Си, Qsort — это алгоритм сортировки, сложность которого в среднем составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.
- Выбираем опорный элемент
- Разбиваем массив на 3 части
- Создаём переменные l и r — индексы соответственно начала и конца рассматриваемого подмассива
- Увеличиваем l, пока l-й элемент меньше опорного
- Уменьшаем r, пока r-й элемент больше опорного
- Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
- Если l вдруг становится больше r, то прерываем цикл
- Повторяем рекурсивно, пока не дойдём до массива из 1 элемента
Что ж, выглядит не так уж сложно. Реализуем на Си? Нет проблем!
Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента — один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.
Писáл сам, изредка поглядывая на Википедию. Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму!
Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.