Вариант 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 endendВариант 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 endendPython 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 {это условие можно убрать} {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)памяти)
Быстрая сортировка, нерекурсивный вариант
Нерекурсивная реализация быстрой сортировки через стек. Функции 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= nilend; Prologsplit (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 "; 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; } PHPfunction 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СЗдесь приведен алгоритм сортировки на примере объекта типа "СписокЗначений", но его можно модифицировать для работы с любым объектом, для этого нужно изменить соответствующим образом код функций "СравнитьЗначения", "ПолучитьЗначение", "УстановитьЗначение".