Sorting algorithms/Quicksort: Difference between revisions
Line 785: | Line 785: | ||
f = v; n=length(v); |
f = v; n=length(v); |
||
if(n > 1) |
if(n > 1) |
||
vl = min(f); vh = max(f); % min, max |
vl = min(f); vh = max(f); % min, max |
||
p = (vl+vh)*0.5; % pivot |
p = (vl+vh)*0.5; % pivot |
||
ia = find(f < p); ib = find(f == p); ic=find(f > p); |
ia = find(f < p); ib = find(f == p); ic=find(f > p); |
||
f = [qsort(f(ia)); f(ib); qsort(f(ic))]; |
f = [qsort(f(ia)); f(ib); qsort(f(ic))]; |
||
end |
end |
||
return |
return |
Revision as of 12:51, 25 June 2009
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
In this task, the goal is to sort an array (or list) of elements using the Quicksort algorithm. The elements must have a strict weak order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers. The algorithm goes like this (from the wiki):
function quicksort(array) var list lessOrEqual, greater if length(array) ≤ 1 return array select a pivot value pivot from array for each x in array if x ≤ pivot then add x to lessOrEqual if x > pivot then add x to greater return concatenate(quicksort(lessOrEqual), quicksort(greater))
The "pivot" separates the dataset into two groups: those that are less than or equal to the value at the pivot and those that are greater than the pivot. The Quicksort's worst case time is O(n2) for a completely sorted set, but otherwise it is O(n * log n). Its average time is slightly faster than that of the merge sort in most cases, even though they are both O(n * log n) sorts.
ActionScript
The functional programming way
<lang actionscript>function quickSort (array:Array):Array { if (array.length <= 1) return array;
var pivot:Number = array[Math.round(array.length / 2)];
return quickSort(array.filter(function (x:Number, index:int, array:Array):Boolean { return x < pivot; })).concat( array.filter(function (x:Number, index:int, array:Array):Boolean { return x == pivot; })).concat( quickSort(array.filter(function (x:Number, index:int, array:Array):Boolean { return x > pivot; }))); }</lang>
The faster way
<lang actionscript>function quickSort (array:Array):Array { if (array.length <= 1) return array;
var pivot:Number = array[Math.round(array.length / 2)];
var less:Array = []; var equal:Array = []; var greater:Array = [];
for each (var x:Number in array) { if (x < pivot) less.push(x); if (x == pivot) equal.push(x); if (x > pivot) greater.push(x); }
return quickSort(less).concat( equal).concat( quickSort(greater)); }</lang>
Ada
This example is implemented as a generic procedure. The procedure specification is: <lang ada>
----------------------------------------------------------------------- -- Generic Quicksort procedure ----------------------------------------------------------------------- generic type Element_Type is private; type Index_Type is (<>); type Element_Array is array(Index_Type range <>) of Element_Type; with function "<" (Left, Right : Element_Type) return Boolean is <>; with function ">" (Left, Right : Element_Type) return Boolean is <>; procedure Sort(Item : in out Element_Array);</lang>
The procedure body deals with any discrete index type, either an integer type or an enumerated type. <lang ada>
----------------------------------------------------------------------- -- Generic Quicksort procedure ----------------------------------------------------------------------- procedure Sort (Item : in out Element_Array) is procedure Swap(Left, Right : in out Element_Type) is Temp : Element_Type := Left; begin Left := Right; Right := Temp; end Swap; Pivot_Index : Index_Type; Pivot_Value : Element_Type; Right : Index_Type := Item'Last; Left : Index_Type := Item'First; begin if Item'Length > 1 then Pivot_Index := Index_Type'Val((Index_Type'Pos(Item'Last) + 1 + Index_Type'Pos(Item'First)) / 2); Pivot_Value := Item(Pivot_Index); loop Left := Item'First; Right := Item'Last; while Left < Item'Last and then Item(Left) < Pivot_Value loop Left := Index_Type'Succ(Left); end loop; while Right > Item'First and then Item(Right) > Pivot_Value loop Right := Index_Type'Pred(Right); end loop; exit when Left >= Right; Swap(Item(Left), Item(Right)); if Left < Item'Last and Right > Item'First then Left := Index_Type'Succ(Left); Right := Index_Type'Pred(Right); end if; end loop; if Right > Item'First then Sort(Item(Item'First..Right)); end if; if Left < Item'Last then Sort(Item(Left..Item'Last)); end if; end if; end Sort;</lang>
An example of how this procedure may be used is: <lang ada>
with Sort; with Ada.Text_Io; with Ada.Float_Text_IO; use Ada.Float_Text_IO; procedure Sort_Test is type Days is (Mon, Tue, Wed, Thu, Fri, Sat, Sun); type Sales is array(Days range <>) of Float; procedure Sort_Days is new Sort(Float, Days, Sales); procedure Print(Item : Sales) is begin for I in Item'range loop Put(Item => Item(I), Fore => 5, Aft => 2, Exp => 0); end loop; end Print; Weekly_Sales : Sales := (Mon => 300.0, Tue => 700.0, Wed => 800.0, Thu => 500.0, Fri => 200.0, Sat => 100.0, Sun => 900.0); begin Print(Weekly_Sales); Ada.Text_Io.New_Line(2); Sort_Days(Weekly_Sales); Print(Weekly_Sales); end Sort_Test;</lang>
ALGOL 68
From: http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Quicksort#ALGOL_68
PROC partition =(REF [] DATA array, PROC (REF DATA, REF DATA) BOOL cmp)INT: ( INT begin:=LWB array; INT end:=UPB array; WHILE begin < end DO WHILE begin < end DO IF cmp(array[begin], array[end]) THEN DATA tmp=array[begin]; array[begin]:=array[end]; array[end]:=tmp; GO TO break while decr end FI; end -:= 1 OD; break while decr end: SKIP; WHILE begin < end DO IF cmp(array[begin], array[end]) THEN DATA tmp=array[begin]; array[begin]:=array[end]; array[end]:=tmp; GO TO break while incr begin FI; begin +:= 1 OD; break while incr begin: SKIP OD; begin ); PROC qsort=(REF [] DATA array, PROC (REF DATA, REF DATA) BOOL cmp)VOID: ( IF LWB array < UPB array THEN INT i := partition(array, cmp); PAR ( # remove PAR for single threaded sort # qsort(array[:i-1], cmp), qsort(array[i+1:], cmp) ) FI ); MODE DATA = INT; PROC cmp=(REF DATA a,b)BOOL: a>b; main:( []DATA const l=(5,4,3,2,1); [UPB const l]DATA l:=const l; qsort(l,cmp); printf(($g(3)$,l)) )
APL
qsort ← {1≥⍴⍵:⍵⋄e←⍵[?⍴⍵]⋄ (∇(⍵<e)/⍵) , ((⍵=e)/⍵) , ∇(⍵>e)/⍵} qsort 1 3 5 7 9 8 6 4 2 1 2 3 4 5 6 7 8 9
Of course, in real APL applications, one would use ⍋ to sort (which will pick a sorting algorithm suited to the argument).
AutoHotkey
translated from python example <lang AutoHotkey> MsgBox % quicksort("8,4,9,2,1")
quicksort(list) {
StringSplit, list, list, `, If (list0 <= 1) Return list pivot := list1 Loop, Parse, list, `, { If (A_LoopField < pivot) less = %less%,%A_LoopField% Else If (A_LoopField > pivot) more = %more%,%A_LoopField% Else pivotlist = %pivotlist%,%A_LoopField% } StringTrimLeft, less, less, 1 StringTrimLeft, more, more, 1 StringTrimLeft, pivotList, pivotList, 1 less := quicksort(less) more := quicksort(more) Return less . pivotList . more
} </lang>
C
<lang c>void quick(int *left, int *right) {
if (right > left) { int pivot = left[(right-left)/2]; int *r = right, *l = left; do { while (*l < pivot) l++; while (*r > pivot) r--; if (l <= r) { int t = *l; *l++ = *r; *r-- = t; } } while (l <= r); quick(left, r); quick(l, right); }
} void sort(int *array, int length) {
quick(array, array+length-1);
}</lang>
C++
The following implements quicksort with a median-of-three pivot. As idiomatic in C++, the argument last is a one-past-end iterator. Note that this code takes advantage of std::partition, which is O(n). Also note that it needs a random-access iterator for efficient calculation of the median-of-three pivot (more exactly, for O(1) calculation of the iterator mid). <lang cpp>
- include <iterator>
- include <algorithm> // for std::partition
- include <functional> // for std::less
// helper function for median of three template<typename T>
T median(T t1, T t2, T t3)
{
if (t1 < t2) { if (t2 < t3) return t2; else if (t1 < t3) return t3; else return t1; } else { if (t1 < t3) return t1; else if (t2 < t3) return t3; else return t2; }
}
// helper object to get <= from < template<typename Order> struct non_strict_op:
public std::binary_function<typename Order::second_argument_type, typename Order::first_argument_type, bool>
{
non_strict_op(Order o): order(o) {} bool operator()(typename Order::second_argument_type arg1, typename Order::first_argument_type arg2) const { return !order(arg2, arg1); }
private:
Order order;
};
template<typename Order> non_strict_op<Order> non_strict(Order o) {
return non_strict_op<Order>(o);
}
template<typename RandomAccessIterator,
typename Order> void quicksort(RandomAccessIterator first, RandomAccessIterator last, Order order)
{
if (first != last && first+1 != last) { typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type; RandomAccessIterator mid = first + (last - first)/2; value_type pivot = median(*first, *mid, *(last-1)); RandomAccessIterator split1 = std::partition(first, last, std::bind2nd(order, pivot)); RandomAccessIterator split2 = std::partition(split1, last, std::bind2nd(non_strict(order), pivot)); quicksort(first, split1, order); quicksort(split2, last, order); }
}
template<typename RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last)
{
quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
} </lang>
A simpler version of the above that just uses the first element as the pivot and only does one "partition". <lang cpp>
- include <iterator>
- include <algorithm> // for std::partition
- include <functional> // for std::less
template<typename RandomAccessIterator,
typename Order> void quicksort(RandomAccessIterator first, RandomAccessIterator last, Order order)
{
if (last - first > 1) { RandomAccessIterator split = std::partition(first+1, last, std::bind2nd(order, *first)); std::iter_swap(first, split-1); quicksort(first, split-1, order); quicksort(split, last, order); }
}
template<typename RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last)
{
quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
} </lang>
Clojure
A very Haskell-like solution using list comprehensions and lazy evaluation.
(defn qsort [L] (if (nil? L) '() (let [[pivot & L2] L] (lazy-cat (qsort (for [y L2 :when (<= y pivot)] y)) (list pivot) (qsort (for [y L2 :when (> y pivot)] y))))))
Another short version (using quasiquote):
(defn qsort [[pvt & rs]] (if pvt `(~@(qsort (filter #(< % pvt) rs)) ~pvt ~@(qsort (filter #(>= % pvt) rs)))))
Another, more readable version (no macros):
(defn qsort [[pivot & xs]] (when pivot (let [smaller #(< % pivot)] (lazy-cat (qsort (filter smaller xs)) [pivot] (qsort (remove smaller xs))))))
Common Lisp
The functional programming way
<lang lisp>(defun quicksort (list)
(if (<= (length list) 1) list (let ((pivot (first list)))
(append (quicksort (remove-if-not #'(lambda (x) (< x pivot)) list)) (remove-if-not #'(lambda (x) (= x pivot)) list) (quicksort (remove-if-not #'(lambda (x) (> x pivot)) list))))))</lang>
D
An implementation much similar to the C one is possible too, this is slower and simpler, derived from the Python one. This is a function template: <lang d>import std.stdio;
T[] quickSort(T)(T[] items) {
T[] less, more; if (items.length <= 1) return items; else { T pivot = items[0]; foreach(el; items[1 .. $]) if (el < pivot) less ~= el; else more ~= el; return quickSort(less) ~ pivot ~ quickSort(more); }
}
void main() {
auto a1 = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]; writefln(quickSort(a1)); auto a2 = [4.0,65.0,2.0,-31.0,0.0,99.0,2.0,83.0,782.0,1.0]; writefln(quickSort(a2));
} </lang>
E
<lang e>def quicksort := {
def swap(container, ixA, ixB) { def temp := container[ixA] container[ixA] := container[ixB] container[ixB] := temp }
def partition(array, var first :int, var last :int) { if (last <= first) { return } # Choose a pivot def pivot := array[def pivotIndex := (first + last) // 2] # Move pivot to end temporarily swap(array, pivotIndex, last) var swapWith := first # Scan array except for pivot, and... for i in first..!last { if (array[i] <= pivot) { # items ≤ the pivot swap(array, i, swapWith) # are moved to consecutive positions on the left swapWith += 1 } } # Swap pivot into between-partition position. # Because of the swapping we know that everything before swapWith is less # than or equal to the pivot, and the item at swapWith (since it was not # swapped) is greater than the pivot, so inserting the pivot at swapWith # will preserve the partition. swap(array, swapWith, last) return swapWith }
def quicksortR(array, first :int, last :int) { if (last <= first) { return } def pivot := partition(array, first, last) quicksortR(array, first, pivot - 1) quicksortR(array, pivot + 1, last) }
def quicksort(array) { # returned from block quicksortR(array, 0, array.size() - 1) }
}</lang>
Erlang
like haskell <lang erlang>qsort([]) -> []; qsort([X|Xs]) ->
qsort([ Y || Y <- Xs, Y < X]) ++ [X] ++ qsort([ Y || Y <- Xs, Y >= X]).</lang>
Forth
defer lessthan ( a@ b@ -- ? ) ' < is lessthan : mid ( l r -- mid ) over - 2/ -cell and + ; : exch ( addr1 addr2 -- ) dup @ >r over @ swap ! r> swap ! ; : partition ( l r -- l r r2 l2 ) 2dup mid @ >r ( r: pivot ) 2dup begin swap begin dup @ r@ lessthan while cell+ repeat swap begin r@ over @ lessthan while cell- repeat 2dup <= if 2dup exch >r cell+ r> cell- then 2dup > until r> drop ; : qsort ( l r -- ) partition swap rot \ 2over 2over - + < if 2swap then 2dup < if recurse else 2drop then 2dup < if recurse else 2drop then ; : sort ( array len -- ) dup 2 < if 2drop exit then 1- cells over + qsort ;
Fortran
<lang fortran>MODULE Qsort_Module
IMPLICIT NONE
CONTAINS
RECURSIVE SUBROUTINE Qsort(a)
INTEGER, INTENT(IN OUT) :: a(:) INTEGER :: split IF(size(a) > 1) THEN CALL Partition(a, split) CALL Qsort(a(:split-1)) CALL Qsort(a(split:)) END IF
END SUBROUTINE Qsort
SUBROUTINE Partition(a, marker)
INTEGER, INTENT(IN OUT) :: a(:) INTEGER, INTENT(OUT) :: marker INTEGER :: left, right, pivot, temp pivot = (a(1) + a(size(a))) / 2 ! Average of first and last elements to prevent quadratic left = 0 ! behavior with sorted or reverse sorted data right = size(a) + 1 DO WHILE (left < right) right = right - 1 DO WHILE (a(right) > pivot) right = right-1 END DO left = left + 1 DO WHILE (a(left) < pivot) left = left + 1 END DO IF (left < right) THEN temp = a(left) a(left) = a(right) a(right) = temp END IF END DO IF (left == right) THEN marker = left + 1 ELSE marker = left END IF
END SUBROUTINE Partition
END MODULE Qsort_Module
PROGRAM Quicksort
USE Qsort_Module IMPLICIT NONE INTEGER, PARAMETER :: n = 100 INTEGER :: array(n) INTEGER :: i REAL :: x CALL RANDOM_SEED DO i = 1, n CALL RANDOM_NUMBER(x) array(i) = INT(x * 10000) END DO WRITE (*, "(A)") "array is :-" WRITE (*, "(10I5)") array CALL Qsort(array) WRITE (*,*) WRITE (*, "(A)") "sorted array is :-" WRITE (*,"(10I5)") array
END PROGRAM Quicksort</lang>
Haskell
The famous two-liner, reflecting the underlying algorithm directly: <lang haskell> qsort [] = [] qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x] </lang> A more efficient version, doing only one comparison per element: <lang haskell> import Data.List
qsort [] = [] qsort (x:xs) = qsort ys ++ x : qsort zs where (ys, zs) = partition (< x) xs </lang>
IDL
IDL has a powerful optimized sort() built-in. The following is thus merely for demonstration.
function qs, arr if (count = n_elements(arr)) lt 2 then return,arr pivot = total(arr) / count ; use the average for want of a better choice return,[qs(arr[where(arr le pivot)]),qs(arr[where(arr gt pivot)])] end
Example:
IDL> print,qs([3,17,-5,12,99]) -5 3 12 17 99
J
sel=: 1 : 'x # [' quicksort=: 3 : 0 if. 1 >: #y do. y else. (quicksort y <sel e),(y =sel e),quicksort y >sel e=.y{~?#y end. )
To actually sort data in J, it is more convenient and more efficient to use /:~ .
Java
<lang java>public static <E extends Comparable<? super E>> LinkedList<E> quickSort(LinkedList<E> arr){ LinkedList<E> less= new LinkedList<E>(); LinkedList<E> pivotList= new LinkedList<E>(); LinkedList<E> more= new LinkedList<E>(); if(arr.size() <= 1) return arr; E pivot= arr.getFirst(); //This pivot can change to get faster results for(E i: arr){ if(i.compareTo(pivot)<0) less.add(i); else if(i.compareTo(pivot)>0) more.add(i); else pivotList.add(i); } less= quickSort(less); more= quickSort(more); less.addAll(pivotList); less.addAll(more); return less; }</lang>
JavaScript
<lang javascript>function sort(a,less) {
function swap(i,j) { var t=a[i]; a[i]=a[j]; a[j]=t } function qs(l,r) { if (l<r) { var pivot = a[(l+r)>>1]; var l2=l, r2=r; do { while (less(a[l2], pivot) ++l2; while (less(pivot, a[r2]) --r2; if (l2 <= r2) swap(l2++, r2--); } while (l2 <= r2); qs(l, r2); qs(l2, r); } } qs(0, a.length-1); return a;
}</lang>
The functional programming way
<lang javascript>Array.prototype.quick_sort = function () { if (this.length <= 1) return this;
var pivot = this[Math.round(this.length / 2)];
return this.filter(function (x) { return x < pivot }).quick_sort().concat( this.filter(function (x) { return x == pivot })).concat( this.filter(function (x) { return x > pivot }).quick_sort()); }</lang>
Joy
DEFINE qsort == [small] [] [uncons [>] split] [[swap] dip cons concat] binrec .
Logo
<lang logo>
- quicksort (lists, functional)
to small? :list
output or [empty? :list] [empty? butfirst :list]
end to quicksort :list
if small? :list [output :list] localmake "pivot first :list output (sentence quicksort filter [? < :pivot] butfirst :list filter [? = :pivot] :list quicksort filter [? > :pivot] butfirst :list )
end
show quicksort [1 3 5 7 9 8 6 4 2] </lang> <lang logo>
- quicksort (arrays, in-place)
to incr :name
make :name (thing :name) + 1
end to decr :name
make :name (thing :name) - 1
end to swap :i :j :a
localmake "t item :i :a setitem :i :a item :j :a setitem :j :a :t
end
to quick :a :low :high
if :high <= :low [stop] localmake "l :low localmake "h :high localmake "pivot item ashift (:l + :h) -1 :a do.while [ while [(item :l :a) < :pivot] [incr "l] while [(item :h :a) > :pivot] [decr "h] if :l <= :h [swap :l :h :a incr "l decr "h] ] [:l <= :h] quick :a :low :h quick :a :l :high
end to sort :a
quick :a first :a count :a
end
make "test {1 3 5 7 9 8 6 4 2} sort :test show :test </lang>
Lucid
qsort(a) = if eof(first a) then a else follow(qsort(b0),qsort(b1)) fi where p = first a < a; b0 = a whenever p; b1 = a whenever not p; follow(x,y) = if xdone then y upon xdone else x fi where xdone = iseod x fby xdone or iseod x; end; end
Matlab
<lang Matlab> function f=quicksort(v) % v must be a column vector f = v; n=length(v); if(n > 1)
vl = min(f); vh = max(f); % min, max p = (vl+vh)*0.5; % pivot ia = find(f < p); ib = find(f == p); ic=find(f > p); f = [qsort(f(ia)); f(ib); qsort(f(ic))];
end return
N=256*256; v=rand(N,1); tic,u=qsort(v); toc issorted(u)
</lang>
MAXScript
fn quickSort arr = ( less = #() pivotList = #() more = #() if arr.count <= 1 then ( arr ) else ( pivot = arr[arr.count/2] for i in arr do ( case of ( (i < pivot): (append less i) (i == pivot): (append pivotList i) (i > pivot): (append more i) ) ) less = quickSort less more = quickSort more less + pivotList + more ) ) a = #(4, 89, -3, 42, 5, 0, 2, 889) a = quickSort a
Nial
quicksort is fork [ >= [1 first,tally], pass, link [ quicksort sublist [ < [pass, first], pass ], sublist [ match [pass,first],pass ], quicksort sublist [ > [pass,first], pass ] ] ]
Using it.
|quicksort [5, 8, 7, 4, 3] =3 4 5 7 8
OCaml
<lang ocaml>let rec quicksort gt = function
| [] -> [] | x::xs -> let ys, zs = List.partition (gt x) xs in quicksort gt ys @ x :: quicksort gt zs
let _ =
quicksort (>) [4; 65; 2; -31; 0; 99; 83; 782; 1]</lang>
Perl
sub quick_sort { $arr = shift; local $less = []; local $pivot_list = []; local $more = []; if ($#{$arr} <= 0) { return $arr; } else { $pivot = $arr->[0]; foreach my $i (@{$arr}) { if ($i < $pivot) { push @{$less}, $i; } elsif ($i > $pivot) { push @{$more}, $i; } else { push @{$pivot_list}, $i; } } $less = quick_sort($less); $more = quick_sort($more); return [@{$less}, @{$pivot_list}, @{$more}]; } } print join(' ', @{quick_sort([4, 65, 2, -31, 0, 99, 83, 782, 1])}), "\n";
Output:
-31 0 1 2 4 65 83 99 782
Prolog
<lang prolog>qsort( [], [] ). qsort( [X], [X] ). qsort( [H|U], S ) :- splitBy(H, U, L, R), qsort(L, SL), qsort(R, SR), combine(H, SL, SR, S).
% splitBy( H, U, LS, RS ) % True if LS = { L in U | L <= H }; RS = { R in U | R > H } splitBy( H, [], LS, RS). splitBy( H, [U|T], [U|LS], RS ) :- U =< H, splitBy(H, T, LS, RS). splitBy( H, [U|T], LS, [U|RS] ) :- U > H, splitBy(H, T, LS, RS).
% combine( H, L, R, S ) % True if S is L ++ [H] ++ R (in Haskell notation) combine( H, L, R, S ) :- append(L, [H|R], S).</lang>
Python
def quickSort(arr): less = [] pivotList = [] more = [] if len(arr) <= 1: return arr else: pivot = arr[0] for i in arr: if i < pivot: less.append(i) elif i > pivot: more.append(i) else: pivotList.append(i) less = quickSort(less) more = quickSort(more) return less + pivotList + more a = [4, 65, 2, -31, 0, 99, 83, 782, 1] a = quickSort(a)
In a Haskell fashion: <lang python> def qsort(L):
return (qsort([y for y in L[1:] if y <= L[0]]) + L[:1] + qsort([y for y in L[1:] if y > L[0]])) if len(L) > 1 else L
</lang>
Ruby
<lang ruby>class Array
def quick_sort return self if length <= 1 pivot = self[length / 2] return (find_all { |i| i < pivot }).quick_sort + (find_all { |i| i == pivot }) + (find_all { |i| i > pivot }).quick_sort end
end</lang>
Scheme
<lang scheme>(define (split-by l p)
(let loop ((low (list)) (high (list)) (l l)) (if (null? l) (cons low high) (if (p (car l)) (loop low (cons (car l) high) (cdr l)) (loop (cons (car l) low) high (cdr l))))))
(define (quicksort l gt?)
(let q ((l l)) (if (null? l) l (let ((s (split-by (cdr l) (lambda (x) (gt? x (car l)))))) (append (q (car s)) (list (car l)) (q (cdr s))))))) (quicksort (list 1 3 5 7 9 8 6 4 2) >)</lang>
Seed7
const proc: quickSort (inout array elemType: arr, in integer: left, in integer: right) is func local var elemType: compare_elem is elemType.value; var integer: less_idx is 0; var integer: greater_idx is 0; var elemType: help is elemType.value; begin if right > left then compare_elem := arr[right]; less_idx := pred(left); greater_idx := right; repeat repeat incr(less_idx); until arr[less_idx] >= compare_elem; repeat decr(greater_idx); until arr[greater_idx] <= compare_elem or greater_idx = left; if less_idx < greater_idx then help := arr[less_idx]; arr[less_idx] := arr[greater_idx]; arr[greater_idx] := help; end if; until less_idx >= greater_idx; arr[right] := arr[less_idx]; arr[less_idx] := compare_elem; quickSort(arr, left, pred(less_idx)); quickSort(arr, succ(less_idx), right); end if; end func; const proc: quickSort (inout array elemType: arr) is func begin quickSort(arr, 1, length(arr)); end func;
Original source: [2]
SETL
In-place sort (looks much the same as the C version) <lang SETL>a := [2,5,8,7,0,9,1,3,6,4]; qsort(a); print(a);
proc qsort(rw a);
if #a > 1 then pivot := a(#a div 2 + 1); l := 1; r := #a; (while l < r) (while a(l) < pivot) l +:= 1; end; (while a(r) > pivot) r -:= 1; end; swap(a(l), a(r)); end; qsort(a(1..l-1)); qsort(a(r+1..#a)); end if;
end proc;
proc swap(rw x, rw y);
[y,x] := [x,y];
end proc;</lang>
Copying sort using comprehensions:
<lang SETL>a := [2,5,8,7,0,9,1,3,6,4]; print(qsort(a));
proc qsort(a);
if #a > 1 then pivot := a(#a div 2 + 1); a := qsort([x in a | x < pivot]) + [x in a | x = pivot] + qsort([x in a | x > pivot]); end if; return a;
end proc;</lang>
Standard ML
fun quicksort [] = [] | quicksort (x::xs) = let val (left, right) = List.partition (fn y => y<x) xs in quicksort left @ [x] @ quicksort right end
Tcl
<lang tcl> package require Tcl 8.5
proc quicksort {m} {
if {[llength $m] <= 1} { return $m } set pivot [lindex $m 0] set less [set equal [set greater [list]]] foreach x $m { lappend [expr {$x < $pivot ? "less" : $x > $pivot ? "greater" : "equal"}] $x } return [concat [quicksort $less] $equal [quicksort $greater]]
}
puts [quicksort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</lang>
UnixPipes
split() { (while read n ; do test $1 -gt $n && echo $n > $2 || echo $n > $3 done) }
qsort() { (read p; test -n "$p" && ( lc="1.$1" ; gc="2.$1" split $p >(qsort $lc >$lc) >(qsort $gc >$gc); cat $lc <(echo $p) $gc rm -f $lc $gc; )) }
cat to.sort | qsort
V
[qsort [joinparts [p [*l1] [*l2] : [*l1 p *l2]] view]. [split_on_first uncons [>] split]. [small?] [] [split_on_first [l1 l2 : [l1 qsort l2 qsort joinparts]] view i] ifte].
The way of joy (using binrec)
[qsort [small?] [] [uncons [>] split] [[p [*l] [*g] : [*l p *g]] view] binrec].