Quicksort
From CodeCodex
| Related content: |
[edit] Implementations
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))
[edit] ALGOL 68
Quick sort in ALGOL 68 using the PAR clause to break the job into multiple threads.
MODE DATA = INT;
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
);
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] 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
[edit] ARM Assembly
This ARM RISC assembly language implementation for sorting an array of 32-bit integers demonstrates how well quicksort takes advantage of the register model and capabilities of a typical machine instruction set (note that this particular implementation does not meet standard calling conventions and may use more than O(log n) space):
qsort: @ Takes three parameters:
@ a: Pointer to base of array a to be sorted (arrives in r0)
@ left: First of the range of indexes to sort (arrives in r1)
@ right: One past last of range of indexes to sort (arrives in r2)
@ This function destroys: r1, r2, r3, r5, r7
stmfd sp!, {r4, r6, lr} @ Save r4 and r6 for caller
mov r6, r2 @ r6 <- right
qsort_tailcall_entry:
sub r7, r6, r1 @ If right - left <= 1 (already sorted),
cmp r7, #1
ldmlefd sp!, {r4, r6, pc} @ Return, restoring r4 and r6
ldr r7, [r0, r1, asl #2] @ r7 <- a[left], gets pivot element
add r2, r1, #1 @ l <- left + 1
mov r4, r6 @ r <- right
partition_loop:
ldr r3, [r0, r2, asl #2] @ r3 <- a[l]
cmp r3, r7 @ If a[l] <= pivot_element,
addle r2, r2, #1 @ ... increment l, and
ble partition_test @ ... continue to next iteration.
sub r4, r4, #1 @ Otherwise, decrement r,
ldr r5, [r0, r4, asl #2] @ ... and swap a[l] and a[r].
str r5, [r0, r2, asl #2]
str r3, [r0, r4, asl #2]
partition_test:
cmp r2, r4 @ If l < r,
blt partition_loop @ ... continue iterating.
partition_finish:
sub r2, r2, #1 @ Decrement l
ldr r3, [r0, r2, asl #2] @ Swap a[l] and pivot
str r3, [r0, r1, asl #2]
str r7, [r0, r2, asl #2]
bl qsort @ Call self recursively on left part,
@ with args a (r0), left (r1), r (r2),
@ also preserves r4 and r6
mov r1, r4
b qsort_tailcall_entry @ Tail-call self on right part,
@ with args a (r0), l (r1), right (r6)
The call produces 3 words of stack per recursive call and is able to take advantage of its knowledge of its own behavior. A more efficient implementation would sort small ranges by a more efficient method. If an implementation obeying standard calling conventions were needed, a simple wrapper could be written for the initial call to the above function that saves the appropriate registers.
[edit] 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
[edit] C
The implementation in the core implementations section is limited to arrays of integers. 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;
}
}
}
[edit] 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);
}
}
[edit] 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);
}
}
}
[edit] Common Lisp
(defun partition (fun array)
(list (remove-if-not fun array) (remove-if fun array)))
(defun sort (array)
(if (null array) nil
(let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
(append (sort (car part)) (cons (car array) (sort (cadr part)))))))
[edit] 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;
[edit] Erlang programming language
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]).
[edit] Haskell
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] ++ 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)
[edit] 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.
)
[edit] 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 Template:Javadoc:SE 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);
}
}
[edit] 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(data);
/* 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 */
list.add(new Integer(RND.nextInt(max)));
}
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)
{
sorted.add(data.get(0));
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)
{
right.add(next);
}
else if (compare > 0)
{
left.add(next);
}
else
{
fatPivot.add(next);
}
}
rQuickSort(left, sorted);
sorted.addAll(fatPivot);
rQuickSort(right, sorted);
}
}
[edit] 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.
)
[edit] JavaScript
function qsort(a) {
if (a.length == 0) return new Array();
var left = new Array();
var right = new Array();
var pivot = a[0];
for (var i = 1; i < a.length; i++) {
if (a[i] < pivot)
left.push(a[i]);
else
right.push(a[i]);
}
return qsort(left).concat(pivot, qsort(right));
}
[edit] 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}]]]
[edit] 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))];
[edit] Miranda
sort [] = []
sort (pivot:rest) = sort [ y | y <- rest; y <= pivot ]
++ [pivot] ++
sort [ y | y <- rest; y > pivot ]
[edit] OCaml
let rec sort = function
[] -> []
| pivot :: rest ->
let left, right = List.partition (( > ) pivot) rest in
sort left @ pivot :: sort right
[edit] Perl
Readable:
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, @_));
}
[edit] Perl 6
multi quicksort () { () }
multi quicksort (*$x, *@xs) {
my @pre = @xs.grep:{ $_ < $x };
my @post = @xs.grep:{ $_ >= $x };
(@pre.quicksort, $x, @post.quicksort);
}
[edit] PHP
function quicksort($seq)
{
if(!count($seq)) return $seq;
$k = $seq[0];
$x = $y = array();
for($i=1; $i<count($seq); $i++)
{
if($seq[$i] <= $k)
{
$x[] = $seq[$i];
}
else
{
$y[] = $seq[$i];
}
}
return array_merge(quicksort($x), array($k), quicksort($y));
}
[edit] 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, [Head|Tail], [Head|Smaller], Greater) :-
Pivot > Head,
partition(Pivot, Tail, Smaller, Greater).
partition(Pivot, [Head|Tail], Smaller, [Head|Greater]) :-
Pivot =< Head,
partition(Pivot, Tail, Smaller, Greater).
[edit] 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)
[edit] Ruby
def quicksort(list)
return list if list.size <= 1
pivot = list.pop
left, right = list.partition { |e| e < pivot }
quicksort(left) + [pivot] + quicksort(right)
end
[edit] 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))))))))
[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: [1]
[edit] 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);
[edit] 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.
[edit] 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
[edit] 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
[edit] 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;
}
- Original Source: Wikibooks
Categories: Sort algorithms | Pseudocode | ALGOL 68 | AppleScript | ARM Assembly | AutoIt | C | C++ | C sharp | Common Lisp | Delphi | Erlang programming language | Haskell | J | Java | JavaScript | Mathematica | MATLAB | Miranda | Objective Caml | Perl | Perl 6 | PHP | Prolog | Python | Ruby | Scheme | Seed7 | Standard ML | Visual Basic | Zilog Z80000 Assembly | TorqueScript
