Sorting algorithms/Quicksort
From Rosetta Code
< Sorting algorithms(Redirected from Quicksort)
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.
Heapsort | Mergesort | Quicksort
O(n log2n) Sorts
Shell Sort
O(n2) Sorts
Bubble Sort | Cocktail Sort | Comb Sort | Gnome Sort | Insertion Sort | Selection Sort
Other Sorts
Bead Sort | Bogosort | Counting Sort | Pancake Sort | Permutation Sort | Stooge 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
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), concatenate(pivot, 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. An optimally selected pivot will result in partitions of equal length (or lengths differing by 1). The partitioning step may be thought of as a special sorting step using the attribute x ≤ pivot as the sort key, with possible values <true, false>. Quicksort's worst case time is O(n2),e.g., for a completely sorted set with the pivot chosen as the first or last element, 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.
Quicksort may be thought of as being situated at one end of the spectrum of divide-conquer algorithms, with Mergesort at the other end. In Quicksort, which some have called a conquer-divide algorithm, most of the work is done in the partitioning and recursive calls. The subsequent reassembly of the sorted segments involves trivial effort. In Mergesort, in contrast, the partitioning is done in a trivial way by splitting the input array in half. In Quicksort, every element in the first partition is less or equal to every element in the second partition. It is this property that makes the merge phase of Quicksort so trivial that it does not even need mentioning.
[edit] ActionScript
Works with: ActionScript version 3
The functional programming way
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; })));
}
The faster way
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));
}
[edit] Ada
This example is implemented as a generic procedure. The procedure specification is:
-----------------------------------------------------------------------
-- 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);
The procedure body deals with any discrete index type, either an integer type or an enumerated type.
-----------------------------------------------------------------------
-- 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);
Left := Item'First;
Right := Item'Last;
loop
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..Index_Type'Pred(Right)));
end if;
if Left < Item'Last then
Sort(Item(Left..Item'Last));
end if;
end if;
end Sort;
An example of how this procedure may be used is:
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;
[edit] 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))
)
[edit] APL
Works with: Dyalog APLTranslation of: J
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).
[edit] AutoHotkey
translated from python example
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
}
[edit] BCPL
// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.
GET "libhdr.h"
LET quicksort(v, n) BE qsort(v+1, v+n)
AND qsort(l, r) BE
{ WHILE l+8<r DO
{ LET midpt = (l+r)/2
// Select a good(ish) median value.
LET val = middle(!l, !midpt, !r)
LET i = partition(val, l, r)
// Only use recursion on the smaller partition.
TEST i>midpt THEN { qsort(i, r); r := i-1 }
ELSE { qsort(l, i-1); l := i }
}
FOR p = l+1 TO r DO // Now perform insertion sort.
FOR q = p-1 TO l BY -1 TEST q!0<=q!1 THEN BREAK
ELSE { LET t = q!0
q!0 := q!1
q!1 := t
}
}
AND middle(a, b, c) = a<b -> b<c -> b,
a<c -> c,
a,
b<c -> a<c -> a,
c,
b
AND partition(median, p, q) = VALOF
{ LET t = ?
WHILE !p < median DO p := p+1
WHILE !q > median DO q := q-1
IF p>=q RESULTIS p
t := !p
!p := !q
!q := t
p, q := p+1, q-1
} REPEAT
LET start() = VALOF {
LET v = VEC 1000
FOR i = 1 TO 1000 DO v!i := randno(1_000_000)
quicksort(v, 1000)
FOR i = 1 TO 1000 DO
{ IF i MOD 10 = 0 DO newline()
writef(" %i6", v!i)
}
newline()
}
[edit] 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);
}
[edit] 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).
#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>());
}
A simpler version of the above that just uses the first element as the pivot and only does one "partition".
#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>());
}
[edit] C#
Note that actually Array.Sort and ArrayList.Sort both use an unstable implementation of the quicksort algorithm.
using System;
using System.Collections.Generic;
namespace QuickSort
{
class Program
{
static void Main(string[] args)
{
List<int> unsorted = new List<int> { 1, 3, 5, 7, 9, 8, 6, 4, 2 };
List<int> sorted = quicksort(unsorted);
Console.WriteLine(string.Join(",", sorted));
Console.ReadKey();
}
private static List<int> quicksort(List<int> arr)
{
List<int> loe = new List<int>(), gt = new List<int>();
if (arr.Count < 2)
return arr;
int pivot = arr.Count / 2;
int pivot_val = arr[pivot];
arr.RemoveAt(pivot);
foreach (int i in arr)
{
if (i <= pivot_val)
loe.Add(i);
else if (i > pivot_val)
gt.Add(i);
}
List<int> resultSet = new List<int>();
resultSet.AddRange(quicksort(loe));
gt.Add(pivot_val);
resultSet.AddRange(quicksort(gt));
return resultSet;
}
}
}
[edit] 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))))))
[edit] Common Lisp
The functional programming way
(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))))))
With macrolet
(defun qs (list)
(if (< (length list) 2)
list
(macrolet ((pivot (test) `(remove (first list) list :test-not #',test)))
(append (qs (pivot >)) (pivot =) (qs (pivot <))))))
In-place non-functional
(defun quicksort (sequence)
(labels ((swap (a b) (rotatef (elt sequence a) (elt sequence b)))
(sub-sort (left right)
(when (< left right)
(let ((pivot (elt sequence right))
(index left))
(loop for i from left below right
when (<= (elt sequence i) pivot)
do (swap i (prog1 index (incf index))))
(swap right index)
(sub-sort left (1- index))
(sub-sort (1+ index) right)))))
(sub-sort 0 (1- (length sequence)))
sequence))
[edit] Curry
Copied from Curry: Example Programs.
-- quicksort using higher-order functions:
qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:l) = qsort (filter (<x) l) ++ x : qsort (filter (>=x) l)
goal = qsort [2,3,1,0]
[edit] 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:
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));
}
[edit] 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)
}
}
[edit] Erlang
like haskell
qsort([]) -> [];
qsort([X|Xs]) ->
qsort([ Y || Y <- Xs, Y < X]) ++ [X] ++ qsort([ Y || Y <- Xs, Y >= X]).
[edit] F#
let rec qsort = function
[] -> []
| x::xs ->
qsort [for a in xs do if a < x then yield a]@x::
qsort [for a in xs do if a >= x then yield a]
[edit] Factor
: qsort ( seq -- seq )
dup empty? [
unclip [ [ < ] curry partition [ qsort ] bi@ ] keep
prefix append
] unless ;
[edit] 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 ;
[edit] Fortran
Works with: Fortran version 90 and later
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
[edit] Haskell
The famous two-liner, reflecting the underlying algorithm directly:
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]
A more efficient version, doing only one comparison per element:
import Data.List
qsort [] = []
qsort (x:xs) = qsort ys ++ x : qsort zs where (ys, zs) = partition (< x) xs
[edit] 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
[edit] Io
List do(
quickSort := method(
if(size > 1) then(
pivot := at(size / 2 floor)
return select(x, x < pivot) quickSort appendSeq(
select(x, x == pivot) appendSeq(select(x, x > pivot) quickSort)
)
) else(return self)
)
quickSortInPlace := method(
copy(quickSort)
)
)
lst := list(5, -1, -4, 2, 9)
lst quickSort println # ==> list(-4, -1, 2, 5, 9)
lst quickSortInPlace println # ==> list(-4, -1, 2, 5, 9)
Another more low-level Quicksort implementation can be found in Io's [github ] repository.
[edit] J
sel=: 1 : 'x # ['
quicksort=: 3 : 0
if.
1 >: #y
do.
y
else.
e=. y{~?#y
(quicksort y <sel e),(y =sel e),quicksort y >sel e
end.
)
See the Quicksort essay in the J Wiki for additional explanations and examples.
[edit] Java
Works with: Java version 1.5+
Translation of: Python
public static <E extends Comparable<? super E>> List<E> quickSort(List<E> arr) {
if (arr.size() <= 1)
return arr;
E pivot = arr.getFirst(); //This pivot can change to get faster results
List<E> less = new LinkedList<E>();
List<E> pivotList = new LinkedList<E>();
List<E> more = new LinkedList<E>();
// Partition
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);
}
// Recursively sort sublists
less = quickSort(less);
more = quickSort(more);
// Concatenate results
less.addAll(pivotList);
less.addAll(more);
return less;
}
[edit] JavaScript
function sort(array, less) {
function swap(i, j) { var t=array[i]; array[i]=array[j]; array[j]=t }
function quicksort(left, right) {
if (left < right) {
var pivot = array[(left + right) >> 1];
var left_new = left, right_new = right;
do {
while (less(array[left_new], pivot)
left_new++;
while (less(pivot, array[right_new])
right_new--;
if (left_new <= right_new)
swap(left_new++, right_new--);
} while (left_new <= right_new);
quicksort(left, right_new);
quicksort(left_new, right);
}
}
quicksort(0, array.length-1);
return array;
}
The functional programming way
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());
}
[edit] Joy
DEFINE qsort ==
[small]
[]
[uncons [>] split]
[swapd cons concat]
binrec .
[edit] 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]
; 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
[edit] Lua
--in-place quicksort
function quicksort(t, start, endi)
start, endi = start or 1, endi or #t
--partition w.r.t. first element
if(endi - start < 2) then return t end
local pivot = start
for i = start + 1, endi do
if t[i] <= t[pivot] then
local temp = t[pivot + 1]
t[pivot + 1] = t[pivot]
if(i == pivot + 1) then
t[pivot] = temp
else
t[pivot] = t[i]
t[i] = temp
end
pivot = pivot + 1
end
end
t = quicksort(t, start, pivot - 1)
return quicksort(t, pivot + 1, endi)
end
--example
print(unpack(quicksort{5, 2, 7, 3, 4, 7, 1}))
[edit] 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
[edit] M4
dnl return the first element of a list when called in the funny way seen below
define(`arg1', `$1')dnl
dnl
dnl append lists 1 and 2
define(`append',
`ifelse(`$1',`()',
`$2',
`ifelse(`$2',`()',
`$1',
`substr($1,0,decr(len($1))),substr($2,1)')')')dnl
dnl
dnl separate list 2 based on pivot 1, appending to left 3 and right 4,
dnl until 2 is empty, and then combine the sort of left with pivot with
dnl sort of right
define(`sep',
`ifelse(`$2', `()',
`append(append(quicksort($3),($1)),quicksort($4))',
`ifelse(eval(arg1$2<=$1),1,
`sep($1,(shift$2),append($3,(arg1$2)),$4)',
`sep($1,(shift$2),$3,append($4,(arg1$2)))')')')dnl
dnl
dnl pick first element of list 1 as pivot and separate based on that
define(`quicksort',
`ifelse(`$1', `()',
`()',
`sep(arg1$1,(shift$1),`()',`()')')')dnl
dnl
quicksort((3,1,4,1,5,9))
Output:
(1,1,3,4,5,9)
[edit] Mathematica
QuickSort[x_List] := Module[{pivot},
If[Length@x <= 1, Return[x]];
pivot = RandomChoice@x;
Flatten@{QuickSort[Cases[x, j_ /; j < pivot]], Cases[x, j_ /; j == pivot], QuickSort[Cases[x, j_ /; j > pivot]]}
]
[edit] MATLAB
This implements the pseudo-code in the specification. The input can be either a row or column vector, but the returned vector will always be a row vector. This can be modified to operate on any built-in primitive or user defined class by replacing the "<=" and ">" comparisons with "le" and "gt" functions respectively. This is because operators can not be overloaded, but the functions that are equivalent to the operators can be overloaded in class definitions.
This should be placed in a file named quickSort.m.
function sortedArray = quickSort(array)
if numel(array) <= 1 %If the array has 1 element then it can't be sorted
sortedArray = array;
return
end
pivot = array(end);
array(end) = [];
%Create two new arrays which contain the elements that are less than or
%equal to the pivot called "less" and greater than the pivot called
%"greater"
less = array( array <= pivot );
greater = array( array > pivot );
%The sorted array is the concatenation of the sorted "less" array, the
%pivot and the sorted "greater" array in that order
sortedArray = [quickSort(less) pivot quickSort(greater)];
end
A slightly more vectorized version of the above code that removes the need for the less and greater arrays:
function sortedArray = quickSort(array)
if numel(array) <= 1 %If the array has 1 element then it can't be sorted
sortedArray = array;
return
end
pivot = array(end);
array(end) = [];
sortedArray = [quickSort( array(array <= pivot) ) pivot quickSort( array(array > pivot) )];
end
Sample usage:
quickSort([4,3,7,-2,9,1])
ans =
-2 1 3 4 7 9
[edit] 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
[edit] 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
[edit] Nimrod
proc QuickSort(list: seq[int]): seq[int] =
if len(list) == 0:
return @[]
var pivot = list[0]
var left: seq[int] = @[]
var right: seq[int] = @[]
for i in low(list)+1..high(list):
if list[i] <= pivot:
left.add(list[i])
elif list[i] > pivot:
right.add(list[i])
result = QuickSort(left)
result.add(pivot)
result.add(QuickSort(right))
Usage:
var sorted: seq[int] = QuickSort(@[5,2,1,6,2,3,1,2,123,21,54,6,1])
for i in items(sorted):
echo(i)
[edit] 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]
[edit] Octave
Translation of: MATLAB (The MATLAB version works as is in Octave, provided that the code is put in a file named quicksort.m, and everything below the return must be typed in the prompt of course)
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 = [quicksort(f(ia)); f(ib); quicksort(f(ic))];
end
endfunction
N=30; v=rand(N,1); tic,u=quicksort(v); toc
u
[edit] Oz
declare
fun {QuickSort Xs}
case Xs of nil then nil
[] Pivot|Xr then
fun {IsSmaller X} X < Pivot end
Smaller Larger
in
{List.partition Xr IsSmaller ?Smaller ?Larger}
{Append {QuickSort Smaller} Pivot|{QuickSort Larger}}
end
end
in
{Show {QuickSort [3 1 4 1 5 9 2 6 5]}}
[edit] Perl
sub quick_sort {
my @arr = @_;
my @less, @pivot_list , @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
In a more functional style:
sub quicksort {
@_ <= 1 ? @_ : do {
my $pivot = pop;
quicksort( grep {$_ <= $pivot} @_ ),
$pivot,
quicksort( grep {$_ > $pivot} @_ )
}
}
Accepting a sort function:
sub quicksort (&@) {
my $c = shift;
@_ <= 1 ? @_ : do {
local ($a, $b) = splice @_, rand @_, 1;
my (@low, @high);
for $b (@_) {
$c->() <= 0 ?
$high[@high] : $low[@low] = $b
}
quicksort( $c => @low ), $a, quicksort( $c => @high )
}
}
print join ', ' => quicksort { $a <=> $b } 3, 5, 7, 1, -6, 12, 2;
[edit] Perl 6
# Empty list sorts to the empty list
multi quicksort([]) { () }
# Otherwise, extract first item as pivot...
multi quicksort([$pivot, *@rest]) {
# Partition.
my @before := @rest.grep(* before $pivot);
my @after := @rest.grep(* !before $pivot);
# Sort the partitions.
(quicksort(@before), $pivot, quicksort(@after))
}
Note that @before and @after are bound to lazy lists, so the partitions can (at least in theory) be sorted in parallel.
[edit] PHP
function quicksort($arr){
$loe = $gt = array();
if(count($arr) < 2){
return $arr;
}
$pivot_key = key($arr);
$pivot = array_shift($arr);
foreach($arr as $val){
if($val <= $pivot){
$loe[] = $val;
}elseif ($val > $pivot){
$gt[] = $val;
}
}
return array_merge(quicksort($loe),array($pivot_key=>$pivot),quicksort($gt));
}
$arr = array(1, 3, 5, 7, 9, 8, 6, 4, 2);
$arr = quicksort($arr);
echo implode(',',$arr);
1,2,3,4,5,6,7,8,9
[edit] PicoLisp
(de quicksort (L)
(if (cdr L)
(let Pivot (car L)
(append (quicksort (filter '((A) (< A Pivot)) (cdr L)))
(filter '((A) (= A Pivot)) L )
(quicksort (filter '((A) (> A Pivot)) (cdr L)))) )
L) )
[edit] PL/I
DCL (T(20)) FIXED BIN(31); /* scratch space of length N */
QUICKSORT: PROCEDURE (A,AMIN,AMAX,N) RECURSIVE ;
DECLARE (A(*)) FIXED BIN(31);
DECLARE (N,AMIN,AMAX) FIXED BIN(31) NONASGN;
DECLARE (I,J,IA,IB,IC,PIV) FIXED BIN(31);
DECLARE (P,Q) POINTER;
DECLARE (AP(1)) FIXED BIN(31) BASED(P);
IF(N <= 1)THEN RETURN;
IA=0; IB=0; IC=N+1;
PIV=(AMIN+AMAX)/2;
DO I=1 TO N;
IF(A(I) < PIV)THEN DO;
IA+=1; A(IA)=A(I);
END; ELSE IF(A(I) > PIV) THEN DO;
IC-=1; T(IC)=A(I);
END; ELSE DO;
IB+=1; T(IB)=A(I);
END;
END;
DO I=1 TO IB; A(I+IA)=T(I); END;
DO I=IC TO N; A(I)=T(N+IC-I); END;
P=ADDR(A(IC));
IC=N+1-IC;
IF(IA > 1) THEN CALL QUICKSORT(A, AMIN, PIV-1,IA);
IF(IC > 1) THEN CALL QUICKSORT(AP,PIV+1,AMAX, IC);
RETURN;
END QUICKSORT;
MINMAX: PROC(A,AMIN,AMAX,N);
DCL (AMIN,AMAX) FIXED BIN(31),
(N,A(*)) FIXED BIN(31) NONASGN ;
DCL (I,X,Y) FIXED BIN(31);
AMIN=A(N); AMAX=AMIN;
DO I=1 TO N-1;
X=A(I); Y=A(I+1);
IF (X < Y)THEN DO;
IF (X < AMIN) THEN AMIN=X;
IF (Y > AMAX) THEN AMAX=Y;
END; ELSE DO;
IF (X > AMAX) THEN AMAX=X;
IF (Y < AMIN) THEN AMIN=Y;
END;
END;
RETURN;
END MINMAX;
CALL MINMAX(A,AMIN,AMAX,N);
CALL QUICKSORT(A,AMIN,AMAX,N);
[edit] 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).
[edit] PureBasic
Procedure qSort(Array a(1), firstIndex, lastIndex)
Protected low, high, pivotValue
low = firstIndex
high = lastIndex
pivotValue = a((firstIndex + lastIndex) / 2)
Repeat
While a(low) < pivotValue
low + 1
Wend
While a(high) > pivotValue
high - 1
Wend
If low <= high
Swap a(low), a(high)
low + 1
high - 1
EndIf
Until low > high
If firstIndex < high
qSort(a(), firstIndex, high)
EndIf
If low < lastIndex
qSort(a(), low, lastIndex)
EndIf
EndProcedure
Procedure quickSort(Array a(1))
qSort(a(),0,ArraySize(a()))
EndProcedure
[edit] 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 --
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
More readable, but still using list comprehensions:
def qsort(list):
if not list:
return []
else:
pivot = list[0]
less = [x for x in list if x < pivot]
more = [x for x in list[1:] if x >= pivot]
return qsort(less) + [pivot] + qsort(more)
[edit] R
Translation of: Octave
qsort <- function(v) {
if ( length(v) > 1 )
{
pivot <- (min(v) + max(v))/2.0 # Could also use pivot <- median(v)
c(qsort(v[v < pivot]), v[v == pivot], qsort(v[v > pivot]))
} else v
}
N <- 100
vs <- runif(N)
system.time(u <- qsort(vs))
print(u)
[edit] Ruby
class Array
def quick_sort
return self if length <= 1
pivot = self[length / 2]
find_all { |i| i < pivot }.quick_sort +
find_all { |i| i == pivot } +
find_all { |i| i > pivot }.quick_sort
end
end
or
class Array
def quick_sort
return self if length <= 1
pivot = self[0]
less, greatereq = self[1..-1].partition { |x| x < pivot }
less.quick_sort +
[pivot] +
greatereq.quick_sort
end
end
[edit] Sather
class SORT{T < $IS_LT{T}} is
private afilter(a:ARRAY{T}, cmp:ROUT{T,T}:BOOL, p:T):ARRAY{T} is
filtered ::= #ARRAY{T};
loop v ::= a.elt!;
if cmp.call(v, p) then
filtered := filtered.append(|v|);
end;
end;
return filtered;
end;
private mlt(a, b:T):BOOL is return a < b; end;
private mgt(a, b:T):BOOL is return a > b; end;
quick_sort(inout a:ARRAY{T}) is
if a.size < 2 then return; end;
pivot ::= a.median;
left:ARRAY{T} := afilter(a, bind(mlt(_,_)), pivot);
right:ARRAY{T} := afilter(a, bind(mgt(_,_)), pivot);
quick_sort(inout left);
quick_sort(inout right);
res ::= #ARRAY{T};
res := res.append(left, |pivot|, right);
a := res;
end;
end;
class MAIN is
main is
a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4, 656, -11|;
b ::= a.copy;
SORT{INT}::quick_sort(inout a);
#OUT + a + "\n" + b.sort + "\n";
end;
end;
The ARRAY class has a builtin sorting method, which is quicksort (but under certain condition an insertion sort is used instead), exactly quicksort_range; this implementation is original.
[edit] Scala
I'll show a progression on genericity here.
First, a quick sort of a list of integers:
def quicksortInt(coll: List[Int]): List[Int] =
if (coll.isEmpty) {
coll
} else {
val (smaller, bigger) = coll.tail partition (_ < coll.head)
quicksortInt(smaller) ::: coll.head :: quicksortInt(bigger)
}
Next, a quick sort of a list of some type T, given a lessThan function:
def quicksortFunc[T](coll: List[T], lessThan: (T, T) => Boolean): List[T] =
if (coll.isEmpty) {
coll
} else {
val (smaller, bigger) = coll.tail partition (lessThan(_, coll.head))
quicksortFunc(smaller, lessThan) ::: coll.head :: quicksortFunc(bigger, lessThan)
}
To take advantage of known orderings, a quick sort of a list of some type T, for which exists an implicit (or explicit) Ordered[T]:
def quicksortOrd[T <% Ordered[T]](coll: List[T]): List[T] =
if (coll.isEmpty) {
coll
} else {
val (smaller, bigger) = coll.tail partition (_ < coll.head)
quicksortOrd(smaller) ::: coll.head :: quicksortOrd(bigger)
}
That last one could have worked with Ordering, but Ordering is Java, and doesn't have the less than operator. Ordered is Scala-specific, and provides it.
What hasn't changed in all these examples is that I'm ordering a list. It is possible to write a generic quicksort in Scala, which will order any kind of collection. To do so, however, requires that the type of the collection, itself, be made a parameter to the function. Let's see it below, and then remark upon it:
def quicksort
[T, CC[X] <: Traversable[X] with TraversableLike[X, CC[X]]] // My type parameters
(coll: CC[T]) // My explicit parameter
(implicit o: T => Ordered[T], cbf: CanBuildFrom[CC[T], T, CC[T]]) // My implicit parameters
: CC[T] = // My return type
if (coll.isEmpty) {
coll
} else {
val (smaller, bigger) = coll.tail partition (_ < coll.head)
quicksort(smaller) ++ coll.companion(coll.head) ++ quicksort(bigger)
}
That will only work starting with Scala 2.8. The type of our collection is "CC", and, by providing CC[X] as a type parameter to TraversableLike, we ensure CC is capable of returing instances of type CC. Traversable is the base type of all collections, and TraversableLike is a trait which contains the implementation of most Traversable methods.
We need another parameter, though, which is a factory capable of building a CC collection. That is being passed implicitly, so callers to this method do not need to provide them, as the collection they are using should already provide such implicit. Because we need that implicit, then we need to ask for the "T => Ordered[T]" as well, as the "T <% Ordered[T]" which provides it cannot be used in conjunction with implicit parameters.
The body of the function is pretty much the same of the body for the list variant, but using "++" instead of list-specific methods "::" and ":::", and using "coll.companion" to build a collection out of one element.
[edit] 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) >)
[edit] 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]
[edit] SETL
In-place sort (looks much the same as the C version)
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;
Copying sort using comprehensions:
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;
[edit] 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
[edit] 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
[edit] UnixPipes
Works with: Zsh
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
[edit] Ursala
The distributing bipartition operator, *|, is useful for this algorithm. The pivot is chosen as the greater of the first two items, this being the least sophisticated method sufficient to ensure termination. The quicksort function is a higher order function parameterized by the relational predicate p, which can be chosen appropriately for the type of items in the list being sorted. This example demonstrates sorting a list of natural numbers.
#import nat
quicksort "p" = ~&itB^?a\~&a ^|WrlT/~& "p"*|^\~& "p"?hthPX/~&th ~&h
#cast %nL
example = quicksort(nleq) <694,1377,367,506,3712,381,1704,1580,475,1872>
output:
<367,381,475,506,694,1377,1580,1704,1872,3712>
[edit] 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].
Categories: Programming Tasks | Sorting Algorithms | Recursion | ActionScript | Ada | ALGOL 68 | APL | AutoHotkey | BCPL | C | C++ | C sharp | Clojure | Common Lisp | Curry | D | E | Erlang | F Sharp | Factor | Forth | Fortran | Haskell | IDL | Io | J | Java | JavaScript | Joy | Logo | Lua | Lucid | M4 | Mathematica | MATLAB | MAXScript | Nial | Nimrod | OCaml | Octave | Oz | Perl | Perl 6 | PHP | PicoLisp | PL/I | Prolog | PureBasic | Python | R | Ruby | Sather | Scala | Scheme | Seed7 | SETL | Standard ML | Tcl | UnixPipes | Ursala | V
