Быстрая сортировка
Материал из Википедии — свободной энциклопедии
Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Самый быстрый из известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов).
Содержание |
[править] Алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
- Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
- Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
- два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;
- вычисляется опорный элемент m;
- индекс l последовательно увеличивается до m или до тех пор, пока l-й элемент не превысит опорный;
- индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного;
- если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент;
- если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.
- Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
- Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.
Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты.
[править] Оценка эффективности
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь меняются местами наиболее удалённые друг от друга элементы массива. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате самый эффективный улучшенный метод.
- Лучший случай. Для этого алгоритма самый лучший случай — если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N. Это дало бы наименьшее время сортировки.
- Среднее. Даёт в среднем O(n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
На практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N — это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N. - Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
Худший случай даёт O(n²) обменов, но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
[править] Улучшения
- При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(n log n).
- Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит lg2n, а в худшем случае она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.
- Использовать в качестве опорного элемента медиану-средний элемент массива. Т.к. медиана ищется за O(n), алгоритм всегда будет работать за O(n log n).
[править] Достоинства и недостатки
Достоинства:
- Самый быстродействующий из всех существующих алгоритмов обменной сортировки — быстрее него только специализированные алгоритмы, использующие специфику сортируемых данных.
- Простая реализация.
- Хорошо сочетается с алгоритмами кэширования и подкачки памяти.
- Хорошо работает на «почти отсортированных» данных — если исходный массив уже близок к отсортированному, алгоритм не приводит к излишним перестановкам уже стоящих в правильном порядке элементов.
Недостатки:
- При классической реализации требует в худшем случае много дополнительной памяти. Правда, вероятность возникновения худшего случая ничтожна.
- Неустойчив — если требуется устойчивость, приходится расширять ключ.
[править] Примеры реализации
Представленные здесь реализации, кроме варианта на языке Паскаль, используют в качестве опорного элемента один из крайних элементов подмассива. Все эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра они приводят к самому худшему случаю. Реализация на Паскале выбирает в качестве опорного средний элемент, в результате отсортированный массив становится лучшим случаем - он сортируется за наименьшее время, потому что каждый раз опорным элементом оказывается медиана.
[править] C
Первый вариант Работает для любых чисел
int partition (mytype * m, int a, int b) { int i = a; for (int j = a; j <= b; j++) // просматриваем с a по b { if (m[j] <= m[b]) // если элемент m[j] не превосходит m[b], { swap(m[i], m[j]); // меняем местами m[j] и m[a], m[a+1], m[a+2] и так далее... // то есть переносим элементы меньшие m[b] в начало, // а затем и сам m[b] «сверху» i++; // таким образом последний обмен: m[b] и m[i], после чего i++ } } return i-1; // в индексе i хранится <новая позиция элемента m[b]> + 1 } void quicksort (mytype * m, int a, int b) // a - начало подмножества, b - конец { // для первого вызова: a = 0, b = <элементов в массиве> - 1 if (a >= b) return; int c = partition (m, a, b); quicksort (m, a, c-1); quicksort (m, c+1, b); }
Второй вариант. Работает для любых чисел
void qsrt (mytype &v, int l, int r) /* рекурсивная подпрограмма быстрой сортировки Входные параметры &v - ссылка на сортируемый массив (Поправка (3.06.2008: если сортируемый массив объявлен статически, то необходим не параметр int &v, а int (&v)[N], где N длина массива.)) И просьба к автору, приводить пример функции, откуда осуществляется вызов данной функции. l, r - левая и правая граница сортируемой области */ { if (l>=r) return; // Условие выхода из рекурсии (достигнута база рекурсии) int l1, r1, m; mytype tmp; l1 = l; r1 = r; // Запомнить начальное значение границ m = (r+l)/2; // вычисление опорного элемента while(l<r){ // Итеративное разделение массива while ((v[l]<=v[m])&&(l<m)) l++; // сдвиг левой границы while (v[r]>v[m]) r--; // сдвиг правой границы tmp = v[l]; // обмен граничных элементов v[l] = v[r]; v[r] = tmp; if (l == m) m = r; // обновление индекса опорного элемента в случае else if (r == m) m = l; // если опорный элемент участвовал в обмене } qsrt(v, l1, m-1); // рекурсивная сортировка полученных массивов qsrt(v, m+1, r1); }
Третий вариант. (шаблон на C++)
// A - сортируемый массив, a и b - границы template <class T> void Qsort(T *A, int a, int b){ int i, j, m; T c; if (a>=b) return; for (i=a, j=b, m=1; i<j; m>0?j--:i++){ if (A[i]>A[j]){ c = A[i]; A[i] = A[j]; A[j] = c; m = -m;}} Qsort(A, a, i-1); Qsort(A, i+1, b); return; } /* Данная шаблонная функция упорядочивает массив данных любого типа, для которого определён оператор "больше". */ // пример вызова #include <math.h> int main(){ double A[10]; int B[10]; for (int i=0; i<10; i++){ // Заполнение массивов A[i] = sin(i); // Псевдослучайными числами B[i] = int(sin(i)*10);} Qsort(A, 0, 9); // Сортировка вещественных чисел Qsort(B, 0, 9); // Сортировка целых чисел }
[править] C#
int partition (int[] m, int a, int b) { int i = a; for (int j = a; j <= b; j++) // просматриваем с a по b { if (m[j] <= m[b]) // если элемент a[j] не превосходит a[b], { int t = m[i]; // меняем местами a[j] и a[a], a[a+1], a[a+2] и так далее... m[i] = m[j]; // то есть переносим элементы меньшие a[b] в начало, m[j] = t; // а затем и сам a[b] «сверху» i++; // таким образом последний обмен: a[b] и a[i], после чего i++ } } return i-1; // в индексе i хранится <новая позиция элемента a[b]> + 1 } void quicksort (int[] m, int a, int b) // a - начало подмножества, b - конец { // для первого вызова: a = 0, b = <элементов в массиве> - 1 if (a >= b) return; int c = partition (m, a, b); quicksort (m, a, c-1); quicksort (m, c+1, b); }
[править] Ruby
Вариант 1:
class Array def qsort return self.dup if size <=1 l,r = partition {|x| x <= self.first} c,l = l.partition {|x| x == self.first} l.qsort + с + r.qsort end end
Вариант 2:
class Array def partition3 a = Array.new(3) {|i| []} each do |x| a[yield(x)].push x end a end def qsort return self.dup if size <=1 c,l,r = partition3 {|x| first <=> x} l.qsort + c + r.qsort end end
[править] Python
def qsort(L): if L == []: return [] return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + qsort([x for x in L[1:] if x>=L[0]])
[править] Haskell
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
[править] Pascal
В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его — зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве — он проще и быстрее, хотя, теоретически, может быть хуже.
Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.
const max=20; { можно и больше... } type list = array[1..max] 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[random(r-l+1)+l]; { x := a[(r+l) div 2]; - для выбора среднего элемента } repeat while a[i]<x do i:=i+1; { a[i] > x - сортировка по убыванию} while x<a[j] do j:=j-1; { x > a[j] - сортировка по убыванию} if i<=j then begin if a[i] > a[j] then begin { это условие можно убрать } {a[i] < a[j] при сортировке по убыванию} y:=a[i]; a[i]:=a[j]; a[j]:=y; end; i:=i+1; j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; {sort} begin {quicksort}; randomize; { нужно только если используется выборка случайного опорного элемента } sort(Lo,Hi); end; {quicksort}
Быстрая сортировка, нерекурсивный вариант Нерекурсивная реализация "Быстрой сортировки" реализованной через "стэк" (односторонний список). Функции compare и change реализуются в зависимости от типа данных.
procedure quickSort(var X: itemArray; n: integer); type p_node = ^node; node = record node: integer; next: p_node; end; var l,r,i,j: integer; stack: p_node; temp: item; procedure push(i: integer); var temp: p_node; begin new(temp); temp^.node:=i; temp^.next:=stack; stack:=temp; end; function pop: integer; var temp: p_node; begin if stack=nil then pop:=0 else begin temp:=stack; pop:=stack^.node; stack:=stack^.next; dispose(temp); end; end; begin stack:=nil; push(n-1); push(0); repeat l:=pop; r:=pop; if r-l=1 then begin if compare(X[l],X[r]) then change(X[l],X[r]) end else begin temp:=x[(l+r) div 2]; {random(r-l+1)+l} i:=l; j:=r; repeat while compare(temp,X[i]) do i:=i+1; while compare(X[j],temp) do j:=j-1; if i<=j then begin change(X[i],X[j]); i:=i+1; j:=j-1; end; until i>j; if l<j then begin push(j); push(l); end; if i<r then begin push(r); push(i); end; end; until stack=nil; end;
[править] Prolog
split(H, [A|X], [A|Y], Z) :- order(A, H), split(H, X, Y, Z). split(H, [A|X], Y, [A|Z]) :- not(order(A, H)), split(H, X, Y, Z). split(_, [], [], []). quicksort([], X, X). quicksort([H|T], S, X) :- split(H, T, A, B), quicksort(A, S, [H|Y]), quicksort(B, Y, X).
[править] Perl
#! /usr/bin/perl
use strict;
sub qsort {
my ($q, $s, $e) = @_;
my $m = $s-1;
for (my $i = $s; $i < $e; $i++) {
if ($q->[$i] < $q->[$e]) {
$m++;
($q->[$m], $q->[$i]) = ($q->[$i], $q->[$m]);
}
}
$m++;
($q->[$m], $q->[$e]) = ($q->[$e], $q->[$m]);
qsort($q, $s, $m-1) if $s < $m-1;
qsort($q, $m+1, $e) if $m+1 < $e;
}
my @data = map { int(rand(10)) } (1 .. 30);
print "@data\n";
qsort(\@data, 0, $#data);
print "@data\n";
[править] Литература
- Ананий В. Левитин Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 174-179. — ISBN 0-201-74395-7
- Томас Х. Кормен и др. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
