Быстрая сортировка | |
---|---|
Визуализация алгоритма быстрой сортировки. Горизонтальные линии обозначают опорные элементы. | |
Предназначение | Алгоритм сортировки |
Худшее время | O(n2) |
Лучшее время |
O(n log n) (обычное разделение) или O(n) (разделение на 3 части) |
Среднее время | O(n log n) |
Затраты памяти |
O(n) вспомогательных O(log n) вспомогательных (Седжвик 1978) |
Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.
Общая идея алгоритма состоит в следующем:
На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения (см. ниже).
Хоар разработал этот метод применительно к машинному переводу; словарь хранился на магнитной ленте, и сортировка слов обрабатываемого текста позволяла получить их переводы за один прогон ленты, без перемотки её назад. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе, где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника.
Быстрая сортировка относится к алгоритмам «разделяй и властвуй».
Алгоритм состоит из трёх шагов:
В наиболее общем виде алгоритм на псевдокоде (где A — сортируемый массив, а lo и hi — соответственно, нижняя и верхняя границы сортируемого участка этого массива) выглядит следующим образом:.
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
Здесь предполагается, что массив 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) (вернуть массив состоящий из отсортированной левой части, опорного и отсортированной правой части)
На практике она не используется, а служит лишь в образовательных целях, так как использует дополнительную память, чего можно избежать.
В ранних реализациях, как правило, опорным выбирался первый элемент, что снижало производительности на отсортированных массивах. Для улучшения эффективности может выбираться средний, случайный элемент или (для больших массивов) медиана первого, среднего и последнего элементов[2]. Медиана всей последовательности является оптимальным опорным элементом, но её вычисление слишком трудоёмко для использования в сортировке.
Выбор опорного элемента по медиане трёх для разбиения Ломуто:
mid := (lo + hi) / 2 if A[mid] < A[lo] swap A[lo] with A[mid] if A[hi] < A[lo] swap A[lo] with A[hi] if A[hi] < A[mid] swap A[hi] with A[mid] swap A[hi] with A[mid] pivot := A[hi]
Данный алгоритм разбиения был предложен Нико Ломуто[3] и популяризован в книгах Бентли (Programming Pearls) и Кормена (Введение в алгоритмы)[4]. В данном примере опорным выбирается последний элемент. Алгоритм хранит индекс в переменной i. Каждый раз, когда находится элемент, меньше или равный опорному, индекс увеличивается, и элемент вставляется перед опорным. Хоть эта схема разбиения проще и компактнее, чем схема Хоара, она менее эффективна и используется в обучающих материалах. Сложность данной быстрой сортировки падает до O(n2), когда массив уже отсортирован или все его элементы равны. Существуют различные методы оптимизации данной сортировки: алгоритмы выбора опорного элемента, использование сортировки вставками на маленьких массивах. В данном примере сортируются элементы массива A от lo до hi (включительно)[4]:
algorithm partition(A, lo, hi) is pivot := A[hi] i := lo for j := lo to hi - 1 do if A[j] ≤ pivot then swap A[i] with A[j] i := i + 1 swap A[i] with A[hi] return i
Сортировка всего массива может быть выполнена с помощью выполнения quicksort(A, 1, length(A)).
Данная схема использует два индекса (один в начале массива, другой в конце), которые приближаются друг к другу, пока не найдётся пара элементов, где один больше опорного и расположен перед ним, а второй меньше и расположен после. Эти элементы меняются местами. Обмен происходит до тех пор, пока индексы не пересекутся. Алгоритм возвращает последний индекс[5]. Схема Хоара эффективнее схемы Ломуто, так как происходит в среднем в три раза меньше обменов (swap) элементов, и разбиение эффективнее, даже когда все элементы равны[6]. Подобно схеме Ломуто, данная схема также показывает эффективность в O(n2), когда входной массив уже отсортирован. Сортировка с использованием данной схемы нестабильна. Следует заметить, что конечная позиция опорного элемента необязательно совпадает с возвращённым индексом. Псевдокод[4]:
algorithm partition(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do i := i + 1 while A[i] < pivot do j := j - 1 while A[j] > pivot if i >= j then return j swap A[i] with A[j]
Для улучшения производительности при большом количестве одинаковых элементов в массиве может быть применена процедура разбиения массива на три группы: элементы меньшие опорного, равные ему и больше него. (Бентли и Макилрой называют это «толстым разбиением». Данное разбиение используется в функции qsort в седьмой версии Unix[7]). Псевдокод:
algorithm quicksort(A, lo, hi) is if lo < hi then p := pivot(A, lo, hi) left, right := partition(A, p, lo, hi) // возвращается два значения quicksort(A, lo, left) quicksort(A, right, hi)
Ясно, что операция разделения массива на две части относительно опорного элемента занимает время . Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.
Достоинства:
Недостатки:
Улучшения алгоритма направлены, в основном, на устранение или смягчение вышеупомянутых недостатков, вследствие чего все их можно разделить на три группы: придание алгоритму устойчивости, устранение деградации производительности специальным выбором опорного элемента, и защита от переполнения стека вызовов из-за большой глубины рекурсии при неудачных входных данных.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .