Метод Хоара - Быстрая сортировка(Quick-sort). Быстрая сортировка Как сделать быструю сортировку с
Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.
Итак, быстрая сортировка, или, по названию функции в Си, Qsort - это алгоритм сортировки, сложность которого в среднем
составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.
Алгоритм
- Выбираем опорный элемент
- Разбиваем массив на 3 части
- Создаём переменные l и r - индексы соответственно начала и конца рассматриваемого подмассива
- Увеличиваем l, пока l-й элемент меньше опорного
- Уменьшаем r, пока r-й элемент больше опорного
- Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
- Если l вдруг становится больше r, то прерываем цикл
- Повторяем рекурсивно, пока не дойдём до массива из 1 элемента
void qsort (int b, int e)
{
int l = b, r = e;
int piv = arr[(l + r) / 2]; // Опорным элементом для примера возьмём средний
while (l <= r)
{
while (arr[l] < piv)
l++;
while (arr[r] > piv)
r--;
if (l <= r)
swap (arr, arr);
}
if (b < r)
qsort (b, r);
if (e > l)
qsort (l, e);
} /* ----- end of function qsort ----- */// qsort (0, n-1);
* This source code was highlighted with Source Code Highlighter .
Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента - один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.
Писáл сам, изредка поглядывая на Википедию . Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму!
Теги: Qsort, быстрая сортировка, алгоритмы сортировки, алгоритмы, C
Краткое описание алгоритма
- выбрать элемент, называемый опорным.
- сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три - «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
- повторить рекурсивно для «меньших» и «больших».
Примечание: на практике обычно разделяют сортируемое множество не на три, а на две части: например, «меньшие опорного» и «равные и большие». Такой подход в общем случае оказывается эффективнее, так как для осуществления такого разделения достаточно одного прохода по сортируемому множеству и однократного обмена лишь некоторых выбранных элементов.
Алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй ». Шаги алгоритма таковы:
- Выбираем в массиве некоторый элемент, который будем называть опорным элементом . С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана , но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
- Операция разделения
массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного - справа от него. Обычный алгоритм операции:
- Два индекса - l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
- Вычисляется индекс опорного элемента m.
- Индекс l последовательно увеличивается до тех пор, пока l-й элемент не превысит опорный.
- Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
- Если r = l - найдена середина массива - операция разделения закончена, оба индекса указывают на опорный элемент.
- Если l < r - найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
- Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
- Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.
Интересно, что Хоар разработал этот метод применительно к машинному переводу : дело в том, что в то время словарь хранился на магнитной ленте , и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе , где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника (говорят, этот алгоритм был подслушан им у русских студентов).
//алгоритм на языке java public static void qSort(int A, int low, int high) { int i = low; int j = high; int x = A[ (low+ high) / 2 ] ; 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) ; } |
//алгоритм на языке pascal
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]
|
//алгоритм на языке Visual Basic //при первом вызове 2-ой аргумент должен быть равен 1 //3-ий аргумент должен быть равен числу элементов массива Sub qSort(ByVal 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 += 1 Loop Do While ar(j) > m j -= 1 Loop If (i <= j) Then wsp = ar(i) ar(i) = ar(j) ar(j) = wsp i += 1 j -= 1 End If Loop If (low < j) Then qSort(ar, low, j) If (i < high) Then qSort(ar, i, high) End Sub |
Оценка эффективности
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 2 n, а в худшем случае вырожденного разделения она вообще будет не более 2 - вся обработка пройдёт в цикле первого уровня рекурсии.
- Разбивать массив не на две, а на три части (см. Dual Pivot Quicksort).
Достоинства и недостатки
Достоинства:
Недостатки:
Примечания
Литература
- Ананий В. Левитин Глава 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
Быстрая сортировка (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) - широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
Реализация алгоритма на различных языках программирования:
C
Работает для произвольного массива из n целых чисел.
Int n, a[n]; //n - количество элементов void qs(int* s_arr, int first, int last) { int i = first, j = last, x = s_arr[(first + last) / 2]; do { while (s_arr[i] < x) i++; while (s_arr[j] > x) j--; if(i <= j) { if (s_arr[i] > s_arr[j]) swap(&s_arr[i], &s_arr[j]); i++; j--; } } while (i <= j); if (i < last) qs(s_arr, i, last); if (first < j) qs(s_arr, first, j); }
Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.
Java/C#
Int partition (int array, int start, int end) { int marker = start; for (int i = start; i <= end; i++) { if (array[i] <= array) { int temp = array; // swap array = array[i]; array[i] = temp; marker += 1; } } return marker - 1; } void quicksort (int array, int start, int end) { if (start >= end) { return; } int pivot = partition (array, start, end); quicksort (array, start, pivot-1); quicksort (array, pivot+1, end); }
C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable
Int partition
C# с использованием лямбда-выражений
Using System;
using System.Collections.Generic;
using System.Linq;
static public class Qsort
{
public static IEnumerable
C++
Быстрая сортировка на основе библиотеки STL.
#include
Java
import java.util.Comparator; import java.util.Random; public class Quicksort { public static final Random RND = new Random(); private void swap(Object array, int i, int j) { Object tmp = array[i]; array[i] = array[j]; array[j] = tmp; } private int partition(Object array, int begin, int end, Comparator cmp) { int index = begin + RND.nextInt(end - begin + 1); Object pivot = array; swap(array, index, end); for (int i = index = begin; i < end; ++ i) { if (cmp.compare(array[i], pivot) <= 0) { swap(array, index++, i); } } swap(array, index, end); return (index); } private void qsort(Object array, int begin, int end, Comparator cmp) { if (end > begin) { int index = partition(array, begin, end, cmp); qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp); } } public void sort(Object array, Comparator cmp) { qsort(array, 0, array.length - 1, cmp); }Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)
<=N;i=i+1) { A[i]=N-i; System.out.print(A[i]+" "); } System.out.println("\nBefore qSort\n"); // перемешивание массива Random r = new Random(); //инициализация от таймера int yd,xs; for (int i=0;i<=N;i=i+1) { yd=A[i]; xs=r.nextInt(N+1); A[i]=A; A=yd; } for (int i=0;i<=N;i=i+1) System.out.print(A[i]+" "); System.out.println("\nAfter randomization\n"); long start, end; int low=0; int high=N; start=System.nanoTime(); // получить начальное время qSort(A,low,high); end=System.nanoTime(); // получить конечное время for (int i=0;i<=N;i++) System.out.print(A[i]+" "); System.out.println("\nAfter qSort"); System.out.println("\nTime of running: "+(end-start)+"nanosec"); } //описание функции qSort public static void qSort(int A, int low, int high) { int i = low; int j = high; int x = A[(low+high)/2]; 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); //рекурсивные вызовы функции qSort if(low < j) qSort(A, low, j); if(i < high) qSort(A, i, high); } }
JavaScript
Import java.util.Random; public class QuickSort { public static void main(String args) { int N=10; int A; A = new int; // заполнение массива for (int i=0;i<=N;i=i+1) { A[i]=N-i; System.out.print(A[i]+" "); } System.out.println("\nBefore qSort\n"); // перемешивание массива Random r = new Random(); //инициализация от таймера int yd,xs; for (int i=0;i<=N;i=i+1) { yd=A[i]; xs=r.nextInt(N+1); A[i]=A; A=yd; } for (int i=0;i<=N;i=i+1) System.out.print(A[i]+" "); System.out.println("\nAfter randomization\n"); long start, end; int low=0; int high=N; start=System.nanoTime(); // получить начальное время qSort(A,low,high); end=System.nanoTime(); // получить конечное время for (int i=0;i<=N;i++) System.out.print(A[i]+" "); System.out.println("\nAfter qSort"); System.out.println("\nTime of running: "+(end-start)+"nanosec"); } //описание функции qSort public static void qSort(int A, int low, int high) { int i = low; int j = high; int x = A[(low+high)/2]; 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); //рекурсивные вызовы функции qSort if(low < j) qSort(A, low, j); if(i < high) qSort(A, i, high); } }
Python
С использованием генераторов:
Def qsort(L):
if L: return qsort( if x
Математическая версия:
Def qsort(L): if L: return qsort(filter(lambda x: x < L, L)) + L + qsort(filter(lambda x: x >= L, L)) return
Joy
DEFINE sort == split] [ dip cons concat] binrec .PHP
function qsort($s) { for($i=0, $x=$y=array(); $iQsort = qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Математическая версия - с использованием генераторов:
Qsort = qsort (x:xs) = qsort ++ [x] ++ qsort
Common Lisp
В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" - она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp"а.
(defun quickSort (array l r) (let ((i l) (j r) (p (svref array (round (+ l r) 2)))) (while (<= i j) (while (< (svref array i) p) (incf i)) (while (> (svref array j) p) (decf j)) (when (<= i j) (rotatef (svref array i) (svref array j)) (incf i) (decf j))) (if (>= (- j l) 1) (quickSort array l j)) (if (>= (- r i) 1) (quickSort array i r))) array)
Pascal
В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его - зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве - он проще и быстрее, хотя, теоретически, может быть хуже.
Внутреннее условие, помеченное комментарием «это условие можно убрать» - необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии - будут обменены местами. Что займёт больше времени - проверки или лишние перестановки, - зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.
Const max=20; { можно и больше... }
type
list = array of integer;
procedure quicksort(var a: list; Lo,Hi: integer);
procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=a; { x:= a[(r+l) div 2]; - для выбора среднего элемента }
repeat
while a[i] Устойчивый вариант (требует дополнительно O(n)памяти)