Быстрая сортировка
Материал из Википедии — свободной энциклопедии
Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.
Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если отсортировать все слова в тексте, их переводы можно получить за один прогон ленты.
Содержание |
[править] Алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
- Выбираем в массиве некоторый элемент, который будем называть опорным элементом.
- Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
- Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.
Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже отсортированы. Алгоритм всегда завершается, поскольку за каждую итерацию он ставит по крайней мере один элемент на его окончательное место.
[править] Улучшения
При выборе опорного элемента из данного диапазона случайным образом, худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки - O(n log n).
[править] Примеры реализации
[править] C
Для массива целых чисел:
int partition (int *a, int p, int r)
{
int x = a[r];
int i = p - 1;
int j;
int tmp;
for (j = p; j < r; j++)
{
if (a[j] <= x)
{
i++;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
tmp = a[r];
a[r] = a[i+1];
a[i+1] = tmp;
return i + 1;
}
void quicksort (int *a, int p, int r)
{
int q;
if (p < r)
{
q = partition (a, p, r);
quicksort (a, p, q-1);
quicksort (a, q+1, r);
}
}
[править] C++
Быстрая сортировка на основе библиотеки STL.
#include <functional>
#include <algorithm>
#include <iterator>
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
if( first != last ) {
BidirectionalIterator left = first;
BidirectionalIterator right = last;
BidirectionalIterator pivot = left++;
while( left != right ) {
if( cmp( *left, *pivot ) ) {
++left;
} else {
while( (left != --right) && cmp( *pivot, *right ) )
;
std::iter_swap( left, right );
}
}
--left;
std::iter_swap( first, left );
quick_sort( first, left, cmp );
quick_sort( right, last, cmp );
}
}
template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
quick_sort( first, last,
std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
);
}
[править] 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[index];
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);
}
}
[править] Глагол
ЗАДАЧА Упоряд-(ряд+:РЯД ИЗ Доступ; всего:ЦЕЛ; сравнить:ЗАДАЧА(с1-,с2-:Вид):ЦЕЛ);
ПЕР
Л,П:ЦЕЛ; (* текущий участок *)
л,п:ЦЕЛ; (* новый участок *)
граница:Доступ; (* граничное значение для разделение *)
рядл:Доступ; (* промежуточное значение для обмена *)
глубина:ЦЕЛ; (* текущая глубина стека *)
(* стек для новых участков *)
стек:РЯД 32 ИЗ НАБОР Л,П:ЦЕЛ КОН;
УКАЗ
глубина:=0;
стек[глубина].Л:=0;
стек[глубина].П:=всего-1;
ПОВТОРЯТЬ
(* выбор из стека последнего запроса *)
Л:=стек[глубина].Л;
П:=стек[глубина].П;
УМЕНЬШИТЬ(глубина);
ПОВТОРЯТЬ
(* разделение ряд[Л]...ряд[П] *)
л:=Л; п:=П;
граница:=ряд[(Л+П) ДЕЛИТЬ 2];
ПОВТОРЯТЬ
ПОКА сравнить(ряд[л]^,граница^) < 0 ВЫП УВЕЛИЧИТЬ(л) КОН;
ПОКА сравнить(граница^,ряд[п]^) < 0 ВЫП УМЕНЬШИТЬ(п) КОН;
ЕСЛИ л <= п ТО (* обмен ряд[л] с ряд[п] *)
рядл:=ряд[л];
ряд[л]:=ряд[п];
ряд[п]:=рядл;
УВЕЛИЧИТЬ(л);
УМЕНЬШИТЬ(п)
КОН
ДО л > п;
ЕСЛИ п-Л < П-л ТО
ЕСЛИ л < П ТО (* запись в стек запроса на упорядочивание правой части *)
УВЕЛИЧИТЬ(глубина);
стек[глубина].Л:=л;
стек[глубина].П:=П
КОН;
П:=п (* продолжение упорядочивания левой части *)
ИНАЧЕ
ЕСЛИ Л < п ТО (* запись в стек запроса на упорядочивание левой части *)
УВЕЛИЧИТЬ(глубина);
стек[глубина].Л:=Л;
стек[глубина].П:=п
КОН;
Л:=л (* продолжение упорядочивания правой части *)
КОН
ДО Л >= П
ДО глубина < 0
КОН Упоряд;
[править] 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]])
[править] Joy
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
[править] PHP
function qsort($s) {
for($i=0, $x=$y=array(); $i<count($s)-1; $s[++$i]<=$s[0] ? $x[]=$s[$i] : $y[]=$s[$i]);
return count($s)<=1 ? $s : array_merge(qsort($x), array($s[0]), qsort($y));
}
[править] Haskell
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (pivot:rest) = sort [y | y <- rest, y < pivot]
++ [pivot] ++
sort [y | y <- rest, y >=pivot]
[править] 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).
[править] Ruby
def sort(array)
return [] if array.empty?
left, right = array[1..-1].partition { |y| y <= array.first }
sort(left) + [ array.first ] + sort(right)
end
[править] SML
This example demonstrates the use of an arbitrary predicate in a functional language.
fun quicksort lt lst =
let val rec sort =
fn [] => []
| (x::xs) =>
let
val (left,right) = List.partition (fn y => lt (y, x)) xs
in sort left @ x :: sort right
end
in sort lst
end
[править] JavaScript
function QuickSort(A, p, r)
{
if(p<r)
{
var q = Partition(A, p, r);
QuickSort(A, p, q);
QuickSort(A, q+1, r);
}
}
function Partition(A, p, r)
{
var x = A[r];
var i=p-1;
for(var j=p; j<=r ;j++ )
{
if(A[j] <= x)
{
i++;
var temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
return i<r ?i : i-1;
}
[править] TCL
# Функция выбирает подсписок из списка используя условие condition
proc lfind {data arg condition} {
set foo [list]
foreach item $data {
set $arg $item
if {[expr $condition]} {lappend foo $item}
}
return $foo
}
# Сама сотрировка
proc QSort data {
set result {}
if {[llength $data] != 0} {
set check [lindex $data 0]
set result [
concat \
[QSort [lfind $data argument "\$argument < $check"]] \
[list $check] \
[QSort [lfind $data argument "\$argument > $check"]]]
}
return $result
}
