Некоторые из представленных здесь реализаций используют в качестве опорного элемента один из крайних элементов подмассива. Эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра, их время работы становится порядка \Theta(n^2).
В качестве опорного элемента следует выбирать случайный элемент массива, чтобы получить гарантированное время сортировки \Theta(n \log n) в среднем. В случае, если использование случайных чисел нежелательно, в качестве опорного элемента можно выбрать, например, элемент в середине массива, но такие алгоритмы всё равно будут работать за \Theta(n^2) времени на некоторых специально-сконструированных массивах.
Работает для произвольного массива из n целых чисел.
C
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 (i < 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 элементов будет иметь следующий вид.
qs(a, 0, n-1);
Java/C#[править]
int partition (int[] array, int start, int end) {
int marker = start;
for ( int i = start; i <= end; i++ ) {
if ( array[i] <= array[end] ) {
int temp = array[marker];
array[marker] = array[i];
array[i] = temp;
marker += 1;
}
}
return marker - 1;
}
void quicksort (int[] array, int start, int end) {
int pivot;
if ( start >= end ) {
return;
}
pivot = partition (array, start, end);
quicksort (array, start, pivot-1);
quicksort (array, pivot+1, end);
}
C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable<T>
int partition<T>( T[] m, int a, int b) where T :IComparable<T>
{
int i = a;
for (int j = a; j <= b; j++) // просматриваем с a по b
{
if (m[j].CompareTo( m[b]) <= 0) // если элемент m[j] не превосходит m[b],
{
T t = m[i]; // меняем местами m[j] и m[a], m[a+1], m[a+2] и так далее...
m[i] = m[j]; // то есть переносим элементы меньшие m[b] в начало,
m[j] = t; // а затем и сам m[b] «сверху»
i++; // таким образом последний обмен: m[b] и m[i], после чего i++
}
}
return i - 1; // в индексе i хранится <новая позиция элемента m[b]> + 1
}
void quicksort<T>( T[] m, int a, int b) where T : IComparable<T>// 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);
}
//Пример вызова
//double[] arr = {9,1.5,34.4,234,1,56.5};
//quicksort<double>(arr,0,arr.Length-1);
//
C# с использованием лямбда-выражений
using System;
using System.Collections.Generic;
using System.Linq;
static public class Qsort
{
public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> list) where T : IComparable<T>
{
if (!list.Any())
{
return Enumerable.Empty<T>();
}
var pivot = list.First();
var smaller = list.Skip(1).Where(item => item.CompareTo(pivot) <= 0).QuickSort();
var larger = list.Skip(1).Where(item => item.CompareTo(pivot) > 0).QuickSort();
return smaller.Concat(new[] { pivot }).Concat(larger);
}
//(тоже самое, но записанное в одну строку, без объявления переменных)
public static IEnumerable<T> shortQuickSort<T>(this IEnumerable<T> list) where T : IComparable<T>
{
return !list.Any() ? Enumerable.Empty<T>() : list.Skip(1).Where(
item => item.CompareTo(list.First()) <= 0).shortQuickSort().Concat(new[] { list.First() })
.Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).shortQuickSort());
}
}
Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером
import java.util.Random;
import java.lang.*;
public class QuickSort {
public static void main(String[] args) {
int N=10;
int A[];
A = new int[N+1];
// заполнение массива
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[xs];
A[xs]=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
/*
* Алгоритм быстрой сортировки
*
* @param data Array
* @param compare function(a, b) - возвращает 0 если a=b, -1 если a<b и 1 если a>b (необязательная)
* @param change function(a, i, j) - меняет местами i-й и j-й элементы массива а (необязательная)
*
*/
function qsort(data, compare, change) {
var a = data,
f_compare = compare,
f_change = change;
if (!a instanceof Array) { // Данные не являются массивом
return undefined;
};
if (f_compare == undefined) { // Будем использовать простую функцию (для чисел)
f_compare = function(a, b) {return ((a == b) ? 0 : ((a > b) ? 1 : -1));};
};
if (f_change == undefined) { // Будем использовать простую смены (для чисел)
f_change = function(a, i, j) {var c = a[i];a[i] = a[j];a[j] = c;};
};
var qs = function (l, r) {
var i = l,
j = r,
x = a[l+r>>1];
//x = a[Math.floor(Math.random()*(r-l+1))+l];
// x = a[l]; // Если нет желания использовать объект Math
while(i <= j) {
while(f_compare(a[i], x) == -1) {i++;}
while(f_compare(a[j], x) == 1) {j--;}
if(i <= j) {f_change(a, i++, j--);}
};
if(l < j) {qs(l, j);}
if(i < r) {qs(i, r);}
};
qs(0, a.length-1);
};
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 + c + 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 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]])
return []
Haskell
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Математическая версия — с использованием генераторов:
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]
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[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 {это условие можно убрать} {a[i] < a[j] при сортировке по убыванию}
begin
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}
Устойчивый вариант (требует дополнительно O(n)памяти)
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,xval,y: integer;
begin
i:=l; j:=r; x:=random(r-l+1)+l; xval:=a[x]; xvaln:=num[x]{ x :=(r+l) div 2; - для выбора среднего элемента }
repeat
while (a[i]<xval)or((a[i]=xval)and(num[i]<xvaln)) do i:=i+1; {> - сортировка по убыванию}
while (xval<a[j])or((a[j]=xval)and(xvaln<num[j])) do j:=j-1; {> - сортировка по убыванию}
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=num[i]; num[i]:=num[j]; num[j]:=y;
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; {нужно только если используется выборка случайного опорного элемента}
for i:=1 to n do
num[i]:=i;
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
@out=(5,2,7,9,2,5,67,1,5,7,-8,5,0);
sub sortQ{
my($s,$e)=@_;
my$m=$s-1;
for($s..$e-1){
if($out[$_]lt$out[$e]){
++$m;
($out[$m],$out[$_])=($out[$_],$out[$m]);
}
}
++$m;
($out[$m],$out[$e])=($out[$e],$out[$m]);
sortQ($s,$m-1)if$s<$m-1;
sortQ($m+1,$e)if$m+1<$e;
}
sortQ(0,$#out);
F#
let rec quicksort = function
[] -> []
| h::t -> quicksort ([ for x in t when x<=h -> x])
@ [h] @ quicksort ([ for x in t when x>h -> x]);;
OCaml
let rec qsort l=match l with
[]->[]
|a::b-> (qsort (List.filter ((>=) a) b) lt) @ [a] @ (qsort (List.filter ((<) a) b ));;
Erlang
qsort([]) -> [];
qsort([H|T]) -> qsort([X || X <- T, X < H]) ++ [H] ++ qsort([X || X <- T, X >= H]).
D
array qsort(array)(array _a)
{
alias typeof(array.init[0]) _type;
array filter(bool delegate(_type) dg, array a){
array buffer = null;
foreach(value; a) {
if(dg(value)){
buffer ~= value;
}
}
return buffer;
}
if(_a.length <= 1) {
return _a;
}
else {
return qsort( filter((_type e){ return _a[0] >= e; }, _a[1 .. $] ) ) ~ _a[0] ~
qsort( filter((_type e){ return _a[0] < e; }, _a[1 .. $] ) );
}
}
Scala
def qsort[A <% Ordered[A]](list: List[A]): List[A] = list match
{
case head::tail =>
{
qsort( tail filter(head>=) ) ::: head :: qsort( tail filter(head<) )
}
case _ => list;
}
Clojure
Ленивая реализация:
(defn qsort [[x & xs]]
(letfn [(f [g] (qsort (filter #(g % x) xs)))]
(when x (lazy-cat (f <) [x] (f >=)))))
Shen/Qi II
(define filter
{(A --> boolean) --> (list A) --> (list A)}
_ [] -> []
T? [A | B] -> (append [A] (filter T? B)) where (T? A)
T? [_|B] -> (filter T? B)
)
(define q-sort
{(list number) --> (list number)}
[] -> []
[A | B] -> (append (q-sort (filter (> A) [A|B]))
[A]
(q-sort (filter (< A) [A|B]))))
VB.NET
Судя по тестам, сортировка пузырьком 5000 занимает в 8 с половиной раз больше времени, чем qSort'ом
Sub Swap(ByRef Val1, ByRef Val2)
Dim Proc
Proc = Val1
Val1 = Val2
Val2 = Proc
End Sub
Function partition(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer, ByRef pivot As Integer)
Dim i
Dim piv
Dim store
piv = a(pivot)
Swap(a(right - 1), a(pivot))
store = left
For i = left To right - 2
If a(i) <= piv Then
Swap(a(store), a(i))
store = store + 1
End If
Next
Swap(a(right - 1), a(store))
Return store
End Function
Function getpivot(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Return New System.Random().Next(left, right - 1)
End Function
Sub quicksort(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Dim pivot As Integer
If right - left > 1 Then
pivot = getpivot(a, left, right)
pivot = partition(a, left, right, pivot)
quicksort(a, left, pivot)
quicksort(a, pivot + 1, right)
End If
End Sub
Sub qSort(ByVal a() As Integer)
Dim i
Dim ii
For i = 0 To a.Length() - 1
ii = New System.Random().Next(0, a.Length() - 1)
If i <> ii Then
Swap(a(i), a(ii))
End If
Next
quicksort(a, 0, a.Length())
End Sub
Вызов функции:
qSort(имя сортируемого массива)
PHP
function quicksort (&$array, $l, $r) {
function swap (&$x, &$y) {
list($x, $y) = array($y, $x);
}
function qsort ($left, $right) {
global $array;
$i = $left;
$j = $right;
$x = $array[($left + $right) / 2];
do {
while ($array[$i] < $x) $i++;
while ($array[$j] > $x) $j--;
if ($i <= $j) {
if ($array[$i] > $array[$j]) swap ($array[$i], $array[$j]);
$i++;
$j--;
}
} while ($i <= $j);
if ($i < $right) qsort ($i, $right);
if ($j > $left) qsort ($left, $j);
}
qsort ($l, $r);
}
Встроенный язык 1С
Здесь приведен алгоритм сортировки на примере объекта типа «СписокЗначений», но его можно модифицировать для работы с любым объектом, для этого нужно изменить соответствующим образом код функций «СравнитьЗначения», «ПолучитьЗначение», «УстановитьЗначение».
Функция СравнитьЗначения(Знач1, Знач2)
Если Знач1>Знач2 Тогда
Возврат 1;
КонецЕсли;
Если Знач1<Знач2 Тогда
Возврат -1;
КонецЕсли;
Возврат 0;
КонецФункции
Функция ПолучитьЗначение(Список, Номер)
стр="";
Возврат Список.ПолучитьЗначение(Номер, стр);
КонецФункции
Процедура УстановитьЗначение(Список, Номер, Значение)
Список.УстановитьЗначение(Номер, Значение);
КонецПроцедуры
Процедура qs_0(s_arr, first, last)
i = first;
j = last;
x = ПолучитьЗначение(s_arr, (first + last) / 2);
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, i), x)=-1 Цикл
i=i+1;
КонецЦикла;
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, j), x)=1 Цикл
j=j-1;
КонецЦикла;
Если i <= j Тогда
Если i < j Тогда
к=ПолучитьЗначение(s_arr, i);
УстановитьЗначение(s_arr, i, ПолучитьЗначение(s_arr, j));
УстановитьЗначение(s_arr, j, к);
КонецЕсли;
i=i+1;
j=j-1;
КонецЕсли;
Пока i <= j Цикл
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, i), x)=-1 Цикл
i=i+1;
КонецЦикла;
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, j), x)=1 Цикл
j=j-1;
КонецЦикла;
Если i <= j Тогда
Если i < j Тогда
к=ПолучитьЗначение(s_arr, i);
УстановитьЗначение(s_arr, i, ПолучитьЗначение(s_arr, j));
УстановитьЗначение(s_arr, j, к);
КонецЕсли;
i=i+1;
j=j-1;
КонецЕсли;
КонецЦикла;
Если i < last Тогда
qs_0(s_arr, i, last);
КонецЕсли;
Если first < j Тогда
qs_0(s_arr, first,j);
КонецЕсли;
КонецПроцедуры
Процедура Сортировать(Список, Размер="", Первый="", Последний="")
Если ПустоеЗначение(Первый)=1 Тогда
Первый=1;
КонецЕсли;
Если ПустоеЗначение(Последний)=1 Тогда
Последний=Размер;
КонецЕсли;
qs_0(Список, Первый, Последний);
КонецПроцедуры
Turbo Basic 1.1
DEF FN QSORT(LOW,HIGH)
LOCAL I,J,X,TEMP
J=HIGH
X=Y[(LOW+HIGH)/2]
DO
WHILE Y[I]<X:I=I+1:WEND
WHILE Y[J]>X:J=J-1:WEND
IF I<=J THEN
TEMP=Y[I]
Y[I]=Y[J]
Y[J]=TEMP
I=I+1
J=J-1
END IF
LOOP WHILE I<=J
IF LOW<J THEN F=FN QSORT(LOW,J)
IF I<HIGH THEN F=FN QSORT(I,HIGH)
FN QSORT=TRUE
END DEF
Пример вызова функции FN QSORT(LOW,HIGH), входные и выходные данные в массиве DIM Y[N1:N2]
LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)