Quicksort

 Related content:

Implementations

Pseudocode

```function quicksort(array)
var list less, equal, greater
if length(array) ≤ 1
return array
select a pivot value pivot from array
for each x in array
if x < pivot then append x to less
if x = pivot then append x to equal
if x > pivot then append x to greater
return concatenate(quicksort(less), equal, quicksort(greater))
```

AppleScript

This is a straightforward implementation. It is certainly possible to come up with a more efficient one, but it will probably not be as clear as this one:

``` on sort( array, left, right ) set i to left set j to right set v to item ( ( left + right ) div 2 ) of array -- pivot repeat while ( j > i ) repeat while ( item i of array < v ) set i to i + 1 end repeat repeat while ( item j of array > v ) set j to j - 1 end repeat if ( not i > j ) then tell array to set { item i, item j } to { item j, item i } -- swap set i to i + 1 set j to j - 1 end if end repeat if ( left < j ) then sort( array, left, j ) if ( right > i ) then sort( array, i, right ) end sort ```

Hey, you're the goto exerpt. Thanks for hanging out here.

AutoIt v3

This is a straightforward implementation based on the AppleScript example. It is certainly possible to come up with a more efficient one, but it will probably not be as clear as this one:

``` Func sort( ByRef \$array, \$left, \$right ) \$i = \$left \$j = \$right \$v = \$array[Round( ( \$left + \$right ) / 2 ,0)] While ( \$j > \$i ) While (\$array[\$i] < \$v ) \$i = \$i + 1 WEnd While ( \$array[\$j] > \$v ) \$j = \$j - 1 WEnd If ( NOT (\$i > \$j) ) then swap(\$array[\$i], \$array[\$j]) \$i = \$i + 1 \$j = \$j - 1 EndIf WEnd if ( \$left < \$j ) then sort( \$array, \$left, \$j ) if ( \$right > \$i ) then sort( \$array, \$i, \$right ) EndFunc ```

C

The function `qsort()` in the C standard library can be used to sort arrays of any data type. Its use should be preferred in real code. The following implementations serve as an academic exercise.

The following implementation works with any data type, given its size and a function that compares it. This is similar to what ISO/POSIX compliant C standard libraries provide:

```#include <stdlib.h> #include <stdio.h> static void swap(void *x, void *y, size_t l) { char *a = x, *b = y, c; while(l--) { c = *a; *a++ = *b; *b++ = c; } } static void sort(char *array, size_t size, int (*cmp)(void*,void*), int begin, int end) { if (end > begin) { void *pivot = array + begin; int l = begin + size; int r = end; while(l < r) { if (cmp(array+l,pivot) <= 0) { l += size; } else { r -= size; swap(array+l, array+r, size); } } l -= size; swap(array+begin, array+l, size); sort(array, size, cmp, begin, l); sort(array, size, cmp, r, end); } } void qsort(void *array, size_t nitems, size_t size, int (*cmp)(void*,void*)) { sort(array, size, cmp, 0, (nitems-1)*size); } typedef int type; int type_cmp(void *a, void *b){ return (*(type*)a)-(*(type*)b); } main(){ /* simple test case for type=int */ int num_list[]={5,4,3,2,1}; int len=sizeof(num_list)/sizeof(type); char *sep=""; int i; qsort(num_list,len,sizeof(type),type_cmp); printf("sorted_num_list={"); for(i=0; i<len; i++){ printf("%s%d",sep,num_list[i]); sep=", "; } printf("};\n"); } ```

Result:

```sorted_num_list={2, 3, 4, 5, 1};
```

Here's yet another version with various other improvements:

```/***** macros create functional code *****/ #define pivot_index() (begin+(end-begin)/2) #define swap(a,b,t) ((t)=(a),(a)=(b),(b)=(t)) void sort(int array[], int begin, int end) { /*** Use of static here will reduce memory footprint, but will make it thread-unsafe ***/ static int pivot; static int t; /* temporary variable for swap */ if (end > begin) { int l = begin + 1; int r = end; swap(array[begin], array[pivot_index()], t); /*** choose arbitrary pivot ***/ pivot = array[begin]; while(l < r) { if (array[l] <= pivot) { l++; } else { while(l < --r && array[r] >= pivot) /*** skip superfluous swaps ***/  ; swap(array[l], array[r], t); } } l--; swap(array[begin], array[l], t); sort(array, begin, l); sort(array, r, end); } } #undef swap #undef pivot_index ```

An alternate simple C quicksort. The first C implementation above does not sort the list properly if the initial input is a reverse sorted list, or any time in which the pivot turns out be the largest element in the list. Here is another sample quick sort implementation that does address these issues. Note that the swaps are done inline in this implementation. They may be replaced with a swap function as in the above examples.

```void qsort(int arr[], int beg, int end) { int temp; if (end > beg) { int piv = arr[beg], l = beg + 1, r = end; while (l < r) { if (arr[l] <= piv) l++; else if(arr[r] >= piv) r--; else { temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; } } if(arr[l] < piv) { temp = arr[l]; arr[l] = arr[beg]; arr[beg] = temp; l--; } else { l--; temp = arr[l]; arr[l] = arr[beg]; arr[beg] = temp; } qsort(arr, beg, l); qsort(arr, r, end); } } ```

This sorts an array of integers using quicksort with in-place partition.

``` void quicksort(int x[], int first, int last) { int pivIndex = 0; if(first < last) { pivIndex = partition(x,first, last); quicksort(x,first,(pivIndex-1)); quicksort(x,(pivIndex+1),last); } } int partition(int y[], int f, int l) { int up,down,temp; int piv = y[f]; up = f; down = l; goto partLS; do { temp = y[up]; y[up] = y[down]; y[down] = temp; partLS: while (y[up] <= piv && up < l) { up++; } while (y[down] > piv && down > f ) { down--; } } while (down > up); y[f] = y[down]; y[down] = piv; return down; } ```

The following sample of C code can be compiled to sort a vector of strings (defined as char *list[ ]), integers, doubles, etc. This piece of code implements a mixed iterative-recursive strategy that avoids out of stack risks even in worst case. It runs faster than the standard C lib function qsort(), expecially when used with partially sorted arrays (compiled with free Borland bcc32 and tested with 1 million strings vector).

```/********** QuickSort(): sorts the vector 'list[]' **********/ /**** Compile QuickSort for strings ****/ #define QS_TYPE char* #define QS_COMPARE(a,b) (strcmp((a),(b))) /**** Compile QuickSort for integers ****/ //#define QS_TYPE int //#define QS_COMPARE(a,b) ((a)-(b)) /**** Compile QuickSort for doubles, sort list in inverted order ****/ //#define QS_TYPE double //#define QS_COMPARE(a,b) ((b)-(a)) void QuickSort(QS_TYPE list[], int beg, int end) { QS_TYPE piv; QS_TYPE tmp; int l,r,p; while (beg<end) // This while loop will avoid the second recursive call { l = beg; p = (beg+end)/2; r = end; piv = list[p]; while (1) { while ( (l<=r) && ( QS_COMPARE(list[l],piv) <= 0 ) ) l++; while ( (l<=r) && ( QS_COMPARE(list[r],piv) > 0 ) ) r--; if (l>r) break; tmp=list[l]; list[l]=list[r]; list[r]=tmp; if (p==r) p=l; l++; r--; } list[p]=list[r]; list[r]=piv; r--; // Recursion on the shorter side & loop (with new indexes) on the longer if ((r-beg)<(end-l)) { QuickSort(list, beg, r); beg=l; } else { QuickSort(list, l, end); end=r; } } } ```

C++

This is a generic, STL-based version of quicksort.

```#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 ) )
--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 >()
);
}
```

Here's a shorter version than the one in the core implementations section which takes advantage of the standard library's partition() function:

```#include <algorithm> #include <iterator> #include <functional> template <typename T> void sort(T begin, T end) { if (begin != end) { T middle = partition (begin, end, bind2nd( less<iterator_traits<T>::value_type>(), *begin)); sort (begin, middle); sort (max(begin + 1, middle), end); } } ```

C#

The following C# implementation uses a random pivot and is limited to integer arrays; for other value types, replace all instances of int[] with the appropriate type (for example, decimal[]). For object[] comparison, create a delegate to your custom object compare function and pass it as an added parameter to both methods:

```class Quicksort { private void swap(int[] Array, int Left, int Right) { int temp = Array[Right]; Array[Right] = Array[Left]; Array[Left] = temp; } public void sort(int[] Array, int Left, int Right) { int LHold = Left; int RHold = Right; Random ObjRan = new Random(); int Pivot = ObjRan.Next(Left,Right); swap(Array,Pivot,Left); Pivot = Left; Left++; while (Right >= Left) { if (Array[Left] >= Array[Pivot] && Array[Right] < Array[Pivot]) swap(Array, Left, Right); else if (Array[Left] >= Array[Pivot]) Right--; else if (Array[Right] < Array[Pivot]) Left++; else { Right--; Left++; } } swap(Array, Pivot, Right); Pivot = Right; if (Pivot > LHold) sort(Array, LHold, Pivot); if (RHold > Pivot+1) sort(Array, Pivot+1, RHold); } } ```

Example of QuickSort using delegates. Pass the array of objects in the constructor of the class. For comparing other type of objects rewrite your own compare function instead of CompareInt.

```class QuickSort { private delegate int CmpOp(object Left, object Right); private void swap(object[] Array, int Left, int Right, CmpOp Cmp) { object tempObj = Array[Left]; Array[Left] = Array[Right]; Array[Right] = tempObj; } private int CmpInt(object Left, object Right) { if ((int) Left < (int) Right) return -1; else return -2; } public QuickSort(object[] Array) { CmpOp Cmp = new CmpOp(CmpInt); Sort(Array, 0, Array.Length-1, Cmp); } private void Sort(object[] Array, int Left, int Right, CmpOp Cmp) { int LHold = Left; int RHold = Right; Random ObjRan = new Random(); int Pivot = ObjRan.Next(Left,Right); swap(Array, Pivot, Left, Cmp); Pivot = Left; Left++; while (Right >= Left) { if (Cmp(Array[Left], Array[Pivot])!= -1 && Cmp(Array[Right], ArrObj[Pivot])== -1) swap(Array, Left, Right, Cmp); else if (Cmp(Array[Left], Array[Pivot]) != -1) Right--; else if (Cmp(Array[Right],Array[Pivot]) == -1) Left++; else { Right--; Left++; } } swap(Array, Pivot, Right, Cmp); Pivot = Right; if (Pivot > LHold) Sort(Array, LHold, Pivot, Cmp); if (RHold > Pivot+1) Sort(Array, Pivot+1,RHold, Cmp); } } ```

The following is an example of using QuickSort to sort an array of strings.

```class Quicksort { private void quickSwap(string[] Array, int Left, int Right) { string Temp = Array[Right]; Array[Right] = Array[Left]; Array[Left] = Temp; } public void quickSort(string[] Array, int Left, int Right) { int LHold = Left; int RHold = Right; Random ObjRan = new Random(); int Pivot = ObjRan.Next(Left, Right); quickSwap(Array, Pivot, Left); Pivot = Left; Left++; while (Right >= Left) { int cmpLeftVal = Array[Left].CompareTo(Array[Pivot]); int cmpRightVal = Array[Right].CompareTo(Array[Pivot]); if ((cmpLeftVal >= 0) && (cmpRightVal < 0)) { quickSwap(Array, Left, Right); } else { if (cmpLeftVal >= 0) { Right--; } else { if (cmpRightVal < 0) { Left++; } else { Right--; Left++; } } } } quickSwap(Array, Pivot, Right); Pivot = Right; if (Pivot > LHold) { quickSort(Array, LHold, Pivot); } if (RHold > Pivot + 1) { quickSort(Array, Pivot + 1, RHold); } } } ```

Common 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))))))```

D

```void sort(T)(T arr) { if (arr.length > 1) { quickSort(arr.ptr, arr.ptr + (arr.length - 1)); } } void quickSort(T)(T *left, T *right) { if (right > left) { T pivot = left[(right - left) / 2]; T* r = right, l = left; do { while (*l < pivot) l++; while (*r > pivot) r--; if (l <= r) swap(*l++, *r--); } while (l <= r); quickSort(left, r); quickSort(l, right); } } ```

Delphi

This example sorts strings using quicksort.

Note: This can be considered bad code, as it is very slow.

```procedure QuickSort(const AList: TStrings; const AStart, AEnd: Integer); procedure Swap(const AIdx1, AIdx2: Integer); var Tmp: string; begin Tmp := AList[AIdx1]; AList[AIdx1] := AList[AIdx2]; AList[AIdx2] := Tmp; end; var Left: Integer; Pivot: string; Right: Integer; begin if AStart >= AEnd then Exit; Pivot := AList[AStart]; Left := AStart + 1; Right := AEnd; while Left < Right do begin if AList[Left] < Pivot then Inc(Left) else begin Swap(Left, Right); Dec(Right); end; end; Dec(Left); Swap(Left, AStart); Dec(Left); QuickSort(AList, AStart, Left); QuickSort(AList, Right, AEnd); end; ```

This implementation sorts an array of integers.

```procedure QSort(var A: array of Integer); procedure QuickSort(var A: array of Integer; iLo, iHi: Integer); var Lo, Hi, Mid, T: Integer; begin Lo := iLo; Hi := iHi; Mid := A[(Lo + Hi) div 2]; repeat while A[Lo] < Mid do Inc(Lo); while A[Hi] > Mid do Dec(Hi); if Lo <= Hi then begin T := A[Lo]; A[Lo] := A[Hi]; A[Hi] := T; Inc(Lo); Dec(Hi); end; until Lo > Hi; if Hi > iLo then QuickSort(A, iLo, Hi); if Lo < iHi then QuickSort(A, Lo, iHi); end; begin QuickSort(A, Low(A), High(A)); end; ```

This slightly modified implementation sorts an array of records. This is approximately 8x quicker than the previous one. Note: this is QuickSort only, more speedup can be gain with handling trivial case (comparing two values), or implementing Bubble or Shell sort on small ranges.

```type TCustomRecord = record Key: WideString; foo1:Int64; foo2:TDatetime; foo3:Extended; end; TCustomArray = array of TCustomRecord; procedure QuickSort(var A: TCustomArray; L, R: Integer; var tmp: TCustomRecord); var OrigL, OrigR: Integer; Pivot: WideString; GoodPivot, SortPartitions: Boolean; begin if L<R then begin Pivot:=A[L+Random(R-L)].Key; OrigL:=L; //saving original bounds OrigR:=R; repeat L:=OrigL; //restoring original bounds if we R:=OrigR; //have chosen a bad pivot value while L<R do begin while (L<R) and (A[L].Key<Pivot) do Inc(L); while (L<R) and (A[R].Key>=Pivot) do Dec(R); if (L<R) then begin tmp:=A[L]; A[L]:=A[R]; A[R]:=tmp; Dec(R); Inc(L); end; end; if A[L].Key>=Pivot then Dec(L); //has we managed to choose GoodPivot:=L>=OrigL; //a good pivot value? SortPartitions:=True; //if so, then sort on if not GoodPivot then begin //bad luck, the pivot is the smallest one in our range GoodPivot:=True; //let's presume that all the values are equal to pivot SortPartitions:=False; //then no need to sort it for R := OrigL to OrigR do if A[R].Key<>Pivot then begin //we have at least one different value than our pivot Pivot:=A[R].Key; //so this will be our new pivot GoodPivot:=False; //we have to start again sorting this range Break; end; end; until GoodPivot; if SortPartitions then begin QuickSort(A, OrigL, L, tmp); QuickSort(A, L+1, OrigR, tmp); end; end; end; ```

Erlang

The following Erlang code sorts lists of items of any type.

```qsort([]) -> []; qsort([Pivot|Rest]) -> qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]). ```

The Haskell code in the core implementations section is almost self explanatory but can suffer from inefficiencies because it crawls through the list "rest" twice, once for each list comprehension. A smart implementation can perform optimizations to prevent this inefficiency, but these are not required by the language. The following implementation does not have the aforementioned inefficiency, as it uses a partition function that ensures that we only traverse `xs' once:

```partition:: (Ord a) => [a] -> a -> ([a],[a]) -> ([a],[a]) partition [] _ part = part -- base case partition (x:xs) pivot (lesseq,greater) = if x<= pivot then partition xs pivot (x:lesseq,greater) else partition xs pivot (lesseq,x:greater) sort:: (Ord a) => [a] -> [a] sort [] = [] sort (x:xs) = sort lesseq ++ [x] ++ sort greater where (lesseq,greater) = partition xs x ([],[]) ```

Another version:

```quicksort :: Ord a => [a] -> [a]
quicksort []           = []
quicksort (pivot:tail) = quicksort less ++ [pivot] ++ quicksort greater
where less    = [y | y <- tail, y < pivot]
greater = [y | y <- tail, y >= pivot]
```

An even shorter version:

```qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
```

J

The J example in the core implementations section is extremely terse and difficult to understand. This implementation, from the J Dictionary, is less obtuse:

```sel=: adverb def 'x. # ['

quicksort=: verb define
if. 1 >: #y. do. y.
else.
(quicksort y. <sel e),(y. =sel e),quicksort y. >sel e=.y.{~?#y.
end.
)
```

Java

With the advent of J2SE 5.0 you can use parameterized types to avoid passing the `Comparator` used above.

The following implementations use Generics to

The following Java implementation uses a randomly selected pivot. It sorts objects that implement the `Comparator` interface using the natural ordering of their `compareTo` method.

``` import java.util.Arrays;
import java.util.Random;

public class QuickSort {
public static final Random RND = new Random();

private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}

private static <E extends Comparable<? super E>> int partition(E[] array, int begin, int end) {
int index = begin + RND.nextInt(end - begin + 1);
E pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++i) {
if (array[i].compareTo(pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}

private static <E extends Comparable<? super E>> void qsort(E[] array, int begin, int end) {
if (end > begin) {
int index = partition(array, begin, end);
qsort(array, begin, index - 1);
qsort(array, index + 1, end);
}
}

public static <E extends Comparable<? super E>> void sort(E[] array) {
qsort(array, 0, array.length - 1);
}

// Example uses
public static void main(String[] args) {
Integer[] l1 = { 5, 1024, 1, 88, 0, 1024 };
System.out.println("l1  start:" + Arrays.toString(l1));
QuickSort.sort(l1);
System.out.println("l1 sorted:" + Arrays.toString(l1));

String[] l2 = { "gamma", "beta", "alpha", "zoolander" };
System.out.println("l2  start:" + Arrays.toString(l2));
QuickSort.sort(l2);
System.out.println("l2 sorted:" + Arrays.toString(l2));
}
}

Analogously to the Erlang solution above, a user-supplied {{Javadoc:SE|java/util|Comparator}} determines the partial ordering of array elements:

import java.util.Comparator;
import java.util.Random;

public class Quicksort {
public static final Random RND = new Random();
private static void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> 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 static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1,  end,  cmp);
}
}
public static <E> void sort(E[] array, Comparator<? super E> cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
```

another

```import java.util.*;
public class QuickSort
{
public static final Random RND = new Random();

public static void main(String[] args)
{
/* Data to be sorted */
List<Integer> data = createRandomData();

/* Generate a random permutation of the data.
* This sometimes improves the performance of QuickSort
*/
Collections.shuffle(data);

/* Call quick sort */
List<Integer> sorted = quickSort(data);

/* Print sorted data to the standard output */
System.out.println(sorted);
}

/* Add data to be sorted to the list */
public static List<Integer> createRandomData()
{
int max = 1000000;
int len = 1000;
List<Integer> list = new ArrayList<Integer>();
for (int i=0; i<len; i++)
{
/* You can add any type that implements
* the Comparable interface */
}
return list;
}

public static <E extends Comparable<? super E>> List<E> quickSort(List<E> data)
{
List<E> sorted = new ArrayList<E>();
rQuickSort(data, sorted);
return sorted;
}

/**
* A recursive implementation of QuickSort. Pivot selection
* is random. The algorithm is stable.
*/
public static <E extends Comparable<? super E>> void rQuickSort(List<E> data, List<E> sorted)
{
if (data.size() == 1)
{
return;
}

if (data.size() == 0)
{
return;
}

/* choose the pivot randomly */
int pivot = RND.nextInt(data.size());
E pivotI = data.get(pivot);
List<E> fatPivot = new ArrayList<E>();
List<E> left = new ArrayList<E>();
List<E> right = new ArrayList<E>();

// partition data
for (E next : data)
{
int compare = pivotI.compareTo(next);
if (compare < 0)
{
}
else if (compare > 0)
{
}
else
{
}
}
rQuickSort(left, sorted);
rQuickSort(right, sorted);
}
}
```

JavaScript

```function qsort(a) { if (a.length == 0) return []; var left = []; var right = []; var pivot = a[0]; for (var i = a.length; --i;) { if (a[i] < pivot) left.push(a[i]); else right.push(a[i]); } return qsort(left).concat(pivot, qsort(right)); } ```

Mathematica

Here's a functional-style implementation:

```QSort[{}] := {} QSort[{h_, t___}] := Join[QSort[Select[{t}, # < h &]], {h}, QSort[Select[{t}, # >= h &]]] ```

Here's a test driver which should yield `True`:

```OrderedQ[QSort[Table[Random[Integer, {1, 10000}], {i, 1, 10000}]]] ```

MATLAB

``` function [y]=quicksort(x)  % Uses quicksort to sort an array. Two dimensional arrays are sorted column-wise. [n,m]=size(x); if(m>1) y=x; for j=1:m y(:,j)=quicksort(x(:,j)); end return; end % The trivial cases if(n<=1);y=x;return;end; if(n==2) if(x(1)>x(2)) x=[x(2); x(1)]; end y=x; return; end % The non-trivial case % Find a pivot, and divide the array into two parts. % All elements of the first part are less than the % pivot, and the elements of the other part are greater % than or equal to the pivot. m=fix(n/2); pivot=x(m); ltIndices=find(x<pivot); % Indices of all elements less than pivot. if(isempty(ltIndices)) % This happens when pivot is miniumum of all elements. ind=find(x>pivot); % Find the indices of elements greater than pivot. if(isempty(ind));y= x;return;end; % This happens when all elements are the same. pivot=x(ind(1)); % Use new pivot. ltIndices=find(x<pivot); end  % Now find the indices of all elements not less than pivot. % Since the pivot is an element of the array, % geIndices cannot be empty. geIndices=find(x>=pivot); % Recursively sort the two parts of the array and concatenate % the sorted parts. y= [quicksort(x(ltIndices));quicksort(x(geIndices))]; ```

Miranda

``` sort [] = [] sort (pivot:rest) = sort [ y | y <- rest; y <= pivot ] ++ [pivot] ++ sort [ y | y <- rest; y > pivot ] ```

OCaml

```let rec sort = function [] -> [] | pivot :: rest -> let left, right = List.partition (( > ) pivot) rest in sort left @ pivot :: sort right ```

Perl

```sub quicksort {
my @list = @_;

if ( scalar @list <= 1 ) {
return (@list);
}

my \$pivot   = shift @list;

my @less    = grep(\$_ < \$pivot, @list);
my @greater = grep(\$_ > \$pivot, @list);

return ( quicksort(@less), \$pivot, quicksort(@greater));
}
```

Laconic:

```sub qsort {
return () if !@_;
return (qsort(grep { \$_ < \$_[0] } (@_)[1..\$#_]), \$_[0],
qsort(grep { \$_ >= \$_[0] } (@_)[1..\$#_]));
}
```

Or:

```sub qsort {
@_ or return ();
my \$p = shift;
(qsort(grep \$_ < \$p, @_), \$p, qsort(grep \$_ >= \$p, @_));
}
```

Perl 6

```multi quicksort () { () }
multi quicksort (*\$x, *@xs) {
my @pre  = @xs.grep:{ \$_ <  \$x };
my @post = @xs.grep:{ \$_ >= \$x };
(@pre.quicksort, \$x, @post.quicksort);
}
```

PHP

```function quicksort(\$seq)
{
if(!count(\$seq)) return \$seq;

\$k = \$seq[0];
\$x = \$y = array();

for(\$i=count(\$seq); --\$i;)
{
if(\$seq[\$i] <= \$k)
{
\$x[] = \$seq[\$i];
}
else
{
\$y[] = \$seq[\$i];
}
}

return array_merge(quicksort(\$x), array(\$k), quicksort(\$y));
}
```

Prolog

The version in the core implementations section is concise and, because it uses tail recursion, efficient. Here's another version:

```append([], L, L). append([H | L1], L2, [H | Result]) :- append(L1, L2, Result). partition([], _, [], []). partition([H | T], X, [H | Left], Right) :- H =< X, partition(T, X, Left, Right). partition([H | T], X, Left, [H | Right]) :- H > X, partition(T, X, Left, Right). qsort([],[]). qsort([H | Tail], Sorted) :- partition(Tail, H, Left, Right), qsort(Left, SortedLeft), qsort(Right, SortedRight), append(SortedLeft, [X | SortedRight], Sorted). ```

Another version:

```quicksort([], []).
quicksort([Pivot|Tail], Sorted) :-
partition(Pivot, Tail, Smaller, Greater),
quicksort(Smaller, SmallerSorted),
quicksort(Greater, GreaterSorted),
append(SmallerSorted, [Pivot|GreaterSorted], Sorted).
```
```partition(_, [], [], []).
partition(Pivot, Tail, Smaller, Greater).
partition(Pivot, Tail, Smaller, Greater).
```

Python

Using list comprehensions and conditional espressions:

```def qsort(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]]) ) if L else []) ```

Using a less functional approach:

```def qsort2(L): if len(L)<=1: return L pivot=L[0] less= [x for x in L if x<pivot] equal= [x for x in L if x==pivot] greater= [x for x in L if x>pivot] return qsort2(less)+equal+qsort2(greater) ```

In-place, O(log n) space and very readable(IMHO) version

```
def qsort3(arr, l, r):
def swap(arr, s, d):
if s != d:
tmp = arr[s]
arr[s] = arr[d]
arr[d] = tmp
if l >= r:
return
m = l
for i in range(l, r):
if arr[i] <= arr[r]:
swap(arr, i, m)
m += 1
swap(arr, m, r)
qsort3(arr, l, m-1)
qsort3(arr, m+1, r)
return arr

```

Ruby

```def quicksort(list) return list if list.size <= 1 pivot = list.sample left, right = list.partition { |e| e < pivot } quicksort(left) + quicksort(right) end ```

Scheme

This uses SRFI 1 and SRFI 8. It avoids redundantly traversing the list: it partitions it with the pivot in one traversal, not two, and it avoids copying entire lists to append them, by instead only adding elements on the front of the output list's tail.

```(define (quicksort list elt<) (let qsort ((list list) (tail '())) (if (null-list? list) tail (let ((pivot (car list))) (receive (smaller larger) (partition (lambda (x) (elt< x pivot)) (cdr list)) (qsort smaller (cons pivot (qsort larger tail)))))))) ```

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: [1]

Standard ML

The following example—though less general than the snippet in the core implementations section in that it does not accept a predicate argument—strives to more closely resemble the implementations in the other functional languages. The use of `List.partition` in both examples enables the implementation to walk the list only once per call, thereby reducing the constant factor of the algorithm.

```fun qsort [] = [] | qsort (h::t) = let val (left, right) = List.partition (fn x => x < h) t in qsort left @ h :: qsort right end; ```

Replacing the predicate is trivial:

```fun qsort pred [] = [] | qsort pred (h::t) = let val (left, right) = List.partition (fn x => pred (x, h)) t in qsort pred left @ h :: qsort pred right end; ```

A cleaner version that sacrifices the efficiency of `List.partition` and resembles the list-comprehension versions in other functional languages:

```fun qsort [] = [] | qsort (h::t) = qsort (List.filter (fn x => x < h) t) @ h :: qsort (List.filter (fn x => x >= h) t); ```

Tcl

```proc qsort list {
if {[llength \$list] <= 1} {return \$list}
set pivot [lindex \$list 0]
set left [set equal [set right[list]]]
foreach x \$list {
lappend [expr {\$x<\$pivot ? "left" : \$x>\$pivot ? "right" : "equal"}] \$x
}
return [concat [qsort \$left] \$equal [qsort \$right]]
}
```

TorqueScript

This is an implementation of Quicksort using script from the Torque game Builder (aka TorqueScript).

```// Sorts unordered set %uSet, which must be of the class SimSet. function Quicksort(%uSet) {  %less = new SimSet();  %pivots = new SimSet();  %greater = new SimSet(); if(%uSet.getCount() <= 1) return %uSet;  %pivotVal = %uSet.getObject(getRandom(0, %uSet.getCount()-1)).myValue; for(%i = 0; %i < %uSet.getCount(); %i ++) { // A new SimObject must be created in order to store it in a SimSet.  %valObj = new SimObject(val) { myValue = %uSet.getObject(%i).myValue; }; if(%pivotVal > %valObj.myValue)  %less.add(%valObj); else if(%pivotVal == %valObj.myValue)  %pivots.add(%valObj); else //if(%pivotVal < %valObj.myValue)  %greater.add(%valObj); } return qConcatenate(Quicksort(%less), %pivots, Quicksort(%greater)); } function qConcatenate(%less, %equal, %greater) {  %all = new SimSet(); // Concatenate the three arrays, adding them to the SimSet one at a time. for(%i = 0; %i < %less.getCount(); %i ++) {  %all.add(%less.getObject(%i)); } for(%i = 0; %i < %equal.getCount(); %i ++) {  %all.add(%equal.getObject(%i)); } for(%i = 0; %i < %greater.getCount(); %i ++) {  %all.add(%greater.getObject(%i)); } return %all; } ```

Visual Basic

```Option Explicit ' a position, which is *hopefully* never used: Public Const N_POS = -2147483648# Public Sub Swap(ByRef Data() As Variant, _ Index1 As Long, _ Index2 As Long) If Index1 <> Index2 Then Dim tmp As Variant If IsObject(Data(Index1)) Then Set tmp = Data(Index1) Else tmp = Data(Index1) End If If IsObject(Data(Index2)) Then Set Data(Index1) = Data(Index2) Else Data(Index1) = Data(Index2) End If If IsObject(tmp) Then Set Data(Index2) = tmp Else Data(Index2) = tmp End If Set tmp = Nothing End If End Sub Public Sub QuickSort(ByRef Data() As Variant, _ Optional ByVal Lower As Long = N_POS, _ Optional ByVal Upper As Long = N_POS) If Lower = N_POS Then Lower = LBound(Data) End If If Upper = N_POS Then Upper = UBound(Data) End If If Lower < Upper Then Dim Right As Long Dim Left As Long Left = Lower + 1 Right = Upper + 1 Do While Left < Right If Data(Left) <= Data(Lower) Then Left = Left + 1 Else Right = Right - 1 Swap Data, Left, Right End If Loop Left = Left - 1 Swap Data, Lower, Left QuickSort Data, Lower, Left - 1 QuickSort Data, Right, Upper End If End Sub ```

Another implementation:

```Function Quicksort(ByRef aData() As Long) As Long() Dim lPivot As Long Dim aLesser() As Long Dim aPivotList() As Long Dim aBigger() As Long Dim i As Long Dim count As Long Dim ret() As Long On Error Resume Next count = UBound(aData) If Err Then Exit Function ElseIf count = 0 Then Quicksort = aData Exit Function End If On Error GoTo 0 Randomize lPivot = aData(Int(Rnd * count)) For i = 0 To count If aData(i) < lPivot Then AddTo aData(i), aLesser If aData(i) = lPivot Then AddTo aData(i), aPivotList If aData(i) > lPivot Then AddTo aData(i), aBigger Next aLesser = Quicksort(aLesser) aPivotList = aPivotList aBigger = Quicksort(aBigger) ret = JoinLists(aLesser, aPivotList, aBigger) Quicksort = ret End Function Sub AddTo(ByVal lData As Long, ByRef aWhere() As Long) Dim count As Long On Error Resume Next count = UBound(aWhere) + 1 ReDim Preserve aWhere(count) aWhere(count) = lData On Error GoTo 0 End Sub Function JoinLists(ByRef Arr1() As Long, ByRef Arr2() As Long, ByRef Arr3() As Long) As Long() Dim count1 As Long Dim count2 As Long Dim count3 As Long Dim i As Long Dim ret() As Long Dim cnt As Long On Error Resume Next Err.Clear count1 = UBound(Arr1) If Err Then count1 = -1 Err.Clear count2 = UBound(Arr2) If Err Then count2 = -1 Err.Clear count3 = UBound(Arr3) If Err Then count3 = -1 Err.Clear On Error GoTo 0 ReDim ret(count1 + (count2 + 1) + (count3 + 1)) For i = 0 To count1 ret(i) = Arr1(i) Next For i = count1 + 1 To (count2 + 1) + count1 ret(i) = Arr2(i - count1 - 1) Next For i = count2 + 1 + count1 + 1 To (count3 + 1) + (count2 + 1) + count1 ret(i) = Arr3(i - count2 - 1 - count1 - 1) Next JoinLists = ret End Function ```

To generalize it, simply change types to Variant.

Visual Basic for Applications

This is an Excel 2003 VBA implementation based on the Visual Basic implementation. I couldn't make it work with Variant so it is implemented as Date. Change Date to the data type relevant to you.

```Sub Swap(ByRef Data() As Date, _ Index1 As Long, _ Index2 As Long) If Index1 <> Index2 Then Dim tmp As Variant tmp = Data(Index1) Data(Index1) = Data(Index2) Data(Index2) = tmp Set tmp = Nothing End If End Sub Sub QuickSort(ByRef Data() As Date, Lower As Long, Upper As Long) If Lower < Upper Then Dim Right As Long Dim Left As Long Left = Lower + 1 Right = Upper + 1 Do While Left < Right If Data(Left) <= Data(Lower) Then Left = Left + 1 Else Right = Right - 1 Swap Data, Left, Right End If Loop Left = Left - 1 Swap Data, Lower, Left QuickSort Data, Lower, Left - 1 QuickSort Data, Right, Upper End If End Sub ```

Zilog Z80000 Assembly

This implementation is in z80 assembly code. The processor is really ancient, and so its basically a register-stack recursion juggling feat. More on it and the author's comments here. It takes the register pairs BC and HL which point to the start and end memory locations to the list of one-byte elements to be sorted. All registers are filled with "garbage" data in the process, so they need to be pushed to the stack to be saved. The script is about 44 bytes long, and doesn't have pivot-optimizing code.

```; ; Usage: bc->first, de->last, ; call qsort ; Destroys: abcdefhl ; qsort ld hl,0 push hl qsloop ld h,b ld l,c or a sbc hl,de jp c,next1 ;loop until lo<hi pop bc ld a,b or c ret z  ;bottom of stack pop de jp qsloop next1 push de  ;save hi,lo push bc ld a,(bc)  ;pivot ld h,a dec bc inc de fleft inc bc  ;do i++ while cur<piv ld a,(bc) cp h jp c,fleft fright dec de  ;do i-- while cur>piv ld a,(de) ld l,a ld a,h cp l jp c,fright push hl  ;save pivot ld h,d  ;exit if lo>hi ld l,e or a sbc hl,bc jp c,next2 ld a,(bc)  ;swap (bc),(de) ld h,a ld a,(de) ld (bc),a ld a,h ld (de),a pop hl  ;restore pivot jp fleft next2 pop hl  ;restore pivot pop hl  ;pop lo push bc  ;stack=left-hi ld b,h ld c,l  ;bc=lo,de=right jp qsloop ```