Algorithm Implementation/Sorting/Quicksort
From Wikibooks, open books for an open world
The
 |
A Wikibookian suggests that Transwiki:Quicksort
be merged
into this book or chapter. Discuss whether or not this merger should happen on the discussion page. |
Contents
- 1 Pseudocode
- 2 ALGOL 68
- 3 AppleScript
- 4 ARM Assembly
- 5 AutoIt v3
- 6 C
- 7 C++
- 8 C#
- 9 Common Lisp
- 10 D
- 11 Delphi
- 12 Erlang
- 13 F#
- 14 Groovy
- 15 Haskell
- 16 J
- 17 Java
- 18 JavaScript
- 19 Mathematica
- 20 MATLAB
- 21 Miranda
- 22 ML
- 23 OCaml
- 24 Perl
- 25 Perl 6
- 26 PHP
- 27 Prolog
- 28 Python
- 29 Ruby
- 30 Scala
- 31 Scheme
- 32 Shen
- 33 Shell
- 34 Standard ML
- 35 Visual Basic
- 36 Zilog Z80000 Assembly
- 37 TorqueScript
- 38 FORTRAN 90/95
Pseudocode[edit]
Iterative version[edit]
function QuickSort(Array, Left, Right)
var
L2, R2, PivotValue
begin
Stack.Push(Left, Right); // pushes Left, and then Right, on to a stack
while not Stack.Empty do
begin
Stack.Pop(Left, Right); // pops 2 values, storing them in Right and then Left
repeat
PivotValue := Array[(Left + Right) div 2];
L2 := Left;
R2 := Right;
repeat
while Array[L2] < PivotValue do // scan left partition
L2 := L2 + 1;
while Array[R2] > PivotValue do // scan right partition
R2 := R2 - 1;
if L2 <= R2 then
begin
if L2 != R2 then
Swap(Array[L2], Array[R2]); // swaps the data at L2 and R2
L2 := L2 + 1;
R2 := R2 - 1;
end;
until L2 >= R2;
if R2 - Left > Right - L2 then // is left side piece larger?
begin
if Left < R2 then
Stack.Push(Left, R2);
Left := L2;
end;
else
begin
if L2 < Right then // if left side isn't, right side is larger
Stack.Push(L2, Right);
Right := R2;
end;
until Left >= Right;
end;
end;
ALGOL 68[edit]
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)) )
AppleScript[edit]
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
ARM Assembly[edit]
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.
AutoIt v3[edit]
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[edit]
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); } int main(void){ /* 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"); return 0; }
Result:
sorted_num_list={2, 3, 4, 5, 1}; // why?
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 quick(int array[], int start, int end){ if(start < end){ int l=start+1, r=end, p = array[start]; while(l<r){ if(array[l] <= p) l++; else if(array[r] >= p) r--; else swap(array[l],array[r]); } if(array[l] < p){ swap(array[l],array[start]); l--; } else{ l--; swap(array[l],array[start]); } quick(array, start, l); quick(array, 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(), especially 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-beg)/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; } } }
Iterative Quicksort[edit]
Quicksort could also be implemented iteratively with the help of a little stack. Here a simple version with random selection of the pivot element:
typedef long type; /* array type */ #define MAX 64 /* stack size for max 2^(64/2) array elements */ void quicksort_iterative(type array[], unsigned len) { unsigned left = 0, stack[MAX], pos = 0, seed = rand(); for ( ; ; ) { /* outer loop */ for (; left+1 < len; len++) { /* sort left to len-1 */ if (pos == MAX) len = stack[pos = 0]; /* stack overflow, reset */ type pivot = array[left+seed%(len-left)]; /* pick random pivot */ seed = seed*69069+1; /* next pseudorandom number */ stack[pos++] = len; /* sort right part later */ for (unsigned right = left-1; ; ) { /* inner loop: partitioning */ while (array[++right] < pivot); /* look for greater element */ while (pivot < array[--len]); /* look for smaller element */ if (right >= len) break; /* partition point found? */ type temp = array[right]; array[right] = array[len]; /* the only swap */ array[len] = temp; } /* partitioned, continue left part */ } if (pos == 0) break; /* stack empty? */ left = len; /* left to right is sorted */ len = stack[--pos]; /* get next range to sort */ } }
The pseudorandom selection of the pivot element ensures efficient sorting in O(n log n) under all input conditions (increasing, decreasing order, equal elements). The size of the needed stack is smaller than 2·log2(n) entries (about 99.9% probability). If a limited stack overflows the sorting simply restarts.
C++[edit]
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( pivot, 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> using namespace std; template <typename T> void sort(T begin, T end) { if (begin != end) { T middle = partition (begin, end, bind2nd( less<typename iterator_traits<T>::value_type>(), *begin)); sort (begin, middle); // sort (max(begin + 1, middle), end); T new_middle = begin; sort (++new_middle, end); } }
C#[edit]
The following C# implementation uses a random pivot.
static class Quicksort { private static void Swap<T>(T[] array, int left, int right) { var temp = array[right]; array[right] = array[left]; array[left] = temp; } public static void Sort<T>(T[] array, IComparer<T> comparer = null) { Sort(array, 0, array.Length - 1, comparer); } public static void Sort<T>(T[] array, int startIndex, int endIndex, IComparer<T> comparer = null) { if (comparer == null) comparer = Comparer<T>.Default; int left = startIndex; int right = endIndex; int pivot = startIndex; startIndex++; while (endIndex >= startIndex) { if (comparer.Compare(array[startIndex], array[pivot]) >= 0 && comparer.Compare(array[endIndex], array[pivot]) < 0) Swap(array, startIndex, endIndex); else if (comparer.Compare(array[startIndex], array[pivot]) >= 0) endIndex--; else if (comparer.Compare(array[endIndex], array[pivot]) < 0) startIndex++; else { endIndex--; startIndex++; } } Swap(array, pivot, endIndex); pivot = endIndex; if (pivot > left) Sort(array, left, pivot); if (right > pivot + 1) Sort(array, pivot + 1, right); } }
Common Lisp[edit]
(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)))))))
D[edit]
Based on the C code posted at rossetacode.org
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[edit]
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[edit]
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]).
F#[edit]
let rec quicksort l = match l with | [] -> [] | h::t -> quicksort (List.filter (fun x -> x < h) t) @ h :: quicksort (List.filter (fun x -> x >= h) t)
Groovy[edit]
static def quicksort(v) { if (!v || v.size <= 1) return v def (less, more) = v[1..-1].split { it <= v[0] } quicksort(less) + v[0] + quicksort(more) }
Haskell[edit]
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:
import Data.List (partition) sort:: (Ord a) => [a] -> [a] sort [] = [] sort (x:xs) = sort less ++ [x] ++ sort greatereq where (less,greatereq) = partition (< x) xs
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)
A rather fast version which builds the list from the end, making the use of (++) ok, it only traverses the list of lower parts, prepending them to head of the higher and equal lists. One draw back is that it requires the whole list be sorted, it's not very good for laziness:
qsort xs = qsort' xs []
qsort' [] end = end
qsort' (x:xs) end = qsort' lower (equal ++ qsort' higher end)
where (lower, equal, higher) = partit x xs ([],[x],[])
partit s [] part = part
partit s (x:xs) (l,e,h)
|x < s = partit s xs (x:l, e, h)
|x > s = partit s xs (l, e, x:h)
|otherwise = partit s xs (l, x:e, h)
J[edit]
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[edit]
Here is a sample Java implementation that sorts an ArrayList of numbers.
import java.util.ArrayList; import java.util.Random; public class QuickSort { public static final int NUMBERS_TO_SORT = 25; public QuickSort() { } public static void main(String[] args) { ArrayList<Integer> numbers = new ArrayList<Integer>(); Random rand = new Random(); for (int i = 0; i < NUMBERS_TO_SORT; i++) numbers.add(rand.nextInt(NUMBERS_TO_SORT + 1)); for (int number : numbers) System.out.print(number + " "); System.out.println("\nBefore quick sort\n\n"); for (int number : quicksort(numbers)) System.out.print(number + " "); System.out.println("\nAfter quick sort\n\n"); } public static ArrayList<Integer> quicksort(ArrayList<Integer> numbers) { if (numbers.size() <= 1) return numbers; int pivot = numbers.size() / 2; ArrayList<Integer> lesser = new ArrayList<Integer>(); ArrayList<Integer> greater = new ArrayList<Integer>(); int sameAsPivot = 0; for (int number : numbers) { if (number > numbers.get(pivot)) greater.add(number); else if (number < numbers.get(pivot)) lesser.add(number); else sameAsPivot++; } lesser = quicksort(lesser); for (int i = 0; i < sameAsPivot; i++) lesser.add(numbers.get(pivot)); greater = quicksort(greater); ArrayList<Integer> sorted = new ArrayList<Integer>(); for (int number : lesser) sorted.add(number); for (int number: greater) sorted.add(number); return sorted; } }
The following Java implementation uses a randomly selected pivot. 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); E 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); } }
With the advent of J2SE
5.0 you can use parameterized
types to avoid passing the Comparator used above.
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>> int 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>> int 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)); } }
Another implementation.
import java.util.*; public class QuickSort { 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); } private static final Random rand = new Random(); /* 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(Integer.valueOf(rand.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.iterator().next()); return; } if(data.size() == 0) { return; } /* choose the pivot randomly */ int pivot = rand.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); } }
Here is a sample that uses recursion, like the Groovy implementation:
import java.util.Iterator; import java.util.LinkedList; import java.util.List; public class Quicksort { @SuppressWarnings("unchecked") public static <E extends Comparable<? super E>> List<E>[] split(List<E> v) { List<E>[] results = (List<E>[])new List[] { new LinkedList<E>(), new LinkedList<E>() }; Iterator<E> it = v.iterator(); E pivot = it.next(); while (it.hasNext()) { E x = it.next(); if (x.compareTo(pivot) < 0) results[0].add(x); else results[1].add(x); } return results; } public static <E extends Comparable<? super E>> List<E> quicksort(List<E> v) { if (v == null || v.size() <= 1) return v; final List<E> result = new LinkedList<E>(); final List<E>[] lists = split(v); result.addAll(quicksort(lists[0])); result.add(v.get(0)); result.addAll(quicksort(lists[1])); return result; } }
JavaScript[edit]
function qsort(a) { if (a.length == 0) return []; var left = [], right = [], pivot = a[0]; for (var i = 1; i < a.length; i++) { a[i] < pivot ? left.push(a[i]) : right.push(a[i]); } return qsort(left).concat(pivot, qsort(right)); }
Mathematica[edit]
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[edit]
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[edit]
sort [] = []
sort (pivot:rest) = sort [ y | y <- rest; y <= pivot ]
++ [pivot] ++
sort [ y | y <- rest; y > pivot ]
ML[edit]
(* quicksort_r recurses down the list partitioning it into elements smaller than the pivot and others.
it then combines the lists at the end with the pivot in the middle.
It can be generalised to take a comparison function and thus remove the "int" type restriction.
It could also be generalised to use a Cons() function instead of the :: abbreviation allowing for
other sorts of lists.
*)
fun quicksort [] = []
| quicksort (p::lst) =
let fun quicksort_r pivot ([], front, back) = (quicksort front) @ [pivot] @ (quicksort back)
| quicksort_r pivot (x::xs, front, back) =
if x < pivot then
quicksort_r pivot (xs, x::front, back)
else
quicksort_r pivot (xs, front, x::back)
in
quicksort_r p (lst, [], [])
end
;
(* val quicksort = fn : int list -> int list *)
OCaml[edit]
let rec sort = function [] -> [] | pivot :: rest -> let left, right = List.partition (( > ) pivot) rest in sort left @ pivot :: sort right
Perl[edit]
sub qsort { return () unless @_; (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[edit]
multi quicksort () { () } multi quicksort (*$x, *@xs) { my @pre = @xs.grep:{ $_ < $x }; my @post = @xs.grep:{ $_ >= $x }; (@pre.quicksort, $x, @post.quicksort); }
PHP[edit]
function quicksort($array) { if(count($array) < 2) return $array; $left = $right = array(); reset($array); $pivot_key = key($array); $pivot = array_shift($array); foreach($array as $k => $v) { if($v < $pivot) $left[$k] = $v; else $right[$k] = $v; } return array_merge(quicksort($left), array($pivot_key => $pivot), quicksort($right)); }
With array_filter and consecutive numerical keys
function quicksort($array) { if (count($array) <= 1) { return $array; } $pivot_value = array_shift($array); return array_merge( quicksort(array_filter($array, function ($v) use($pivot_value) {return $v < $pivot_value;})), array($pivot_value), quicksort($higher = array_filter($array, function ($v) use($pivot_value) {return $v >= $pivot_value;})) ); }
Prolog[edit]
The version in the core implementations section is concise and, because it uses tail recursion, efficient. Here's another version:
partition([], _, [], []). partition([X|Xs], Pivot, Smalls, Bigs) :- ( X @< Pivot -> Smalls = [X|Rest], partition(Xs, Pivot, Rest, Bigs) ; Bigs = [X|Rest], partition(Xs, Pivot, Smalls, Rest) ). quicksort([]) --> []. quicksort([X|Xs]) --> { partition(Xs, X, Smaller, Bigger) }, quicksort(Smaller), [X], quicksort(Bigger).
Python[edit]
Using list comprehensions:
def qsort(L): if L == []: return [] return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \ qsort([x for x in L[1:] if x>=L[0]])
With in place partitioning and random pivot selection:
import random def _doquicksort(values, left, right): """Quick sort""" def partition(values, left, right, pivotidx): """In place paritioning from left to right using the element at pivotidx as the pivot. Returns the new pivot position.""" pivot = values[pivotidx] # swap pivot and the last element values[right], values[pivotidx] = values[pivotidx], values[right] storeidx = left for idx in range(left, right): if values[idx] < pivot: values[idx], values[storeidx] = values[storeidx], values[idx] storeidx += 1 # move pivot to the proper place values[storeidx], values[right] = values[right], values[storeidx] return storeidx if right > left: # random pivot pivotidx = random.randint(left, right) pivotidx = partition(values, left, right, pivotidx) _doquicksort(values, left, pivotidx) _doquicksort(values, pivotidx + 1, right) return values def quicksort(mylist): return _doquicksort(mylist, 0, len(mylist) - 1)
Ruby[edit]
class QuickSort def self.sort!(keys) quick(keys,0,keys.size-1) end private def self.quick(keys, left, right) if left < right pivot = partition(keys, left, right) quick(keys, left, pivot-1) quick(keys, pivot+1, right) end keys end def self.partition(keys, left, right) x = keys[right] i = left-1 for j in left..right-1 if keys[j] <= x i += 1 keys[i], keys[j] = keys[j], keys[i] end end keys[i+1], keys[right] = keys[right], keys[i+1] i+1 end end
Using Closures:
def quicksort(list) return list if list.length <= 1 pivot = list.shift left, right = list.partition { |el| el < pivot } quicksort(left) + [pivot] + quicksort(right) end
Scala[edit]
def qsort(l: List[Int]): List[Int] = { l match { case List() => l case _ => qsort(for(x <- l.tail if x < l.head) yield x) ::: List(l.head) ::: qsort(for(x <-1.tail if x >= l.head) yield x) } }
Or shorter version:
def qsort: List[Int] => List[Int] = { case Nil => Nil case pivot :: tail => val (smaller, rest) = tail.partition(_ < pivot) qsort(smaller) ::: pivot :: qsort(rest) }
Scheme[edit]
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))))))))
Shen[edit]
(define filter {(A --> boolean) --> (list A) --> (list A)} _ [] -> [] T? [A | B] -> (append [A] (filter T? B)) where (T? A) T? [_|B] -> (filter T? B) ) (define q-sort {(list number) --> (list number)} [] -> [] [A | B] -> (append (q-sort (filter (> A) [A|B])) [A] (q-sort (filter (< A) [A|B]))))
Shell[edit]
While many of the other scripting languages (e.g. Perl, Python, Ruby) have a built-in library sort routine, POSIX shells generally do not.
The following was adapted from the Applescript
code above and used in the bash debugger [1]. It has been tested on bash, zsh, and the Korn shell
(ksh).
# Sort global array, $list, starting from $1 to up to $2. 0 is # returned if everything went okay, and nonzero if there was an error. # We use the recursive quicksort of Tony Hoare with inline array # swapping to partition the array. The partition item is the middle # array item. String comparison is used. The sort is not stable. # It is necessary to use "function" keyword in order not to inherit # variables being defined via typset, which solves the instability # problem here.This is specified in the manual page of ksh. function sort_list() { (($# != 2)) && return 1 typeset -i left=$1 ((left < 0)) || (( 0 == ${#list[@]})) && return 2 typeset -i right=$2 ((right >= ${#list[@]})) && return 3 typeset -i i=$left; typeset -i j=$right typeset -i mid; ((mid= (left+right) / 2)) typeset partition_item; partition_item="${list[$mid]}" typeset temp while ((j > i)) ; do while [[ "${list[$i]}" < "$partition_item" ]] ; do ((i++)) done while [[ "${list[$j]}" > "$partition_item" ]] ; do ((j--)) done if ((i <= j)) ; then temp="${list[$i]}"; list[$i]="${list[$j]}"; list[$j]="$temp" ((i++)) ((j--)) fi done ((left < j)) && sort_list $left $j ((right > i)) && sort_list $i $right return $? } if [[ $0 == *sort.sh ]] ; then [[ -n $ZSH_VERSION ]] && setopt ksharrays typeset -a list list=() sort_list -1 0 typeset -p list list=('one') typeset -p list sort_list 0 0 typeset -p list list=('one' 'two' 'three') sort_list 0 2 typeset -p list list=(4 3 2 1) sort_list 0 3 typeset -p list fi
Standard ML[edit]
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);
Visual Basic[edit]
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.
<p:declare-step xmlns:p="http://www.w3.org/ns/xproc" xmlns:c="http://www.w3.org/ns/xproc-step" xmlns:ix="http://www.innovimax.fr/ns" version="1.0"> <p:input port="source"> <p:inline exclude-inline-prefixes="#all"> <root> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> <doc>03</doc> <doc>04</doc> <doc>07</doc> <doc>06</doc> <doc>02</doc> <doc>01</doc> <doc>08</doc> <doc>10</doc> <doc>09</doc> <doc>05</doc> </root> </p:inline> </p:input> <p:output port="result"/> <p:declare-step type="ix:sort" name="sort"> <p:documentation> <p>XProc QuickSort implementation</p> <p>Copyright (C) 2010 Mohamed ZERGAOUI Innovimax</p> <p>This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.</p> <p>This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.</p> <p>You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.</p> </p:documentation> <p:input port="source" sequence="true"/> <p:output port="result" sequence="true"/> <p:option name="key" required="true"/> <p:count limit="2"/> <p:choose> <p:when test="number(.) le 1"> <p:identity> <p:input port="source"> <p:pipe port="source" step="sort"/> </p:input> </p:identity> </p:when> <p:otherwise> <p:split-sequence test="position() = 1" name="split"> <p:input port="source"> <p:pipe port="source" step="sort"/> </p:input> </p:split-sequence> <p:filter name="filter"> <p:with-option name="select" select="$key"> <p:empty/> </p:with-option> </p:filter> <p:group> <p:variable name="pivot-key" select="."> <p:pipe port="result" step="filter"/> </p:variable> <p:split-sequence name="split-pivot"> <p:input port="source"> <p:pipe port="not-matched" step="split"/> </p:input> <p:with-option name="test" select="concat($key, ' <= ', $pivot-key)"/> </p:split-sequence> <ix:sort name="less"> <p:with-option name="key" select="$key"> <p:empty/> </p:with-option> <p:input port="source"> <p:pipe port="matched" step="split-pivot"/> </p:input> </ix:sort> <ix:sort name="greater"> <p:with-option name="key" select="$key"> <p:empty/> </p:with-option> <p:input port="source"> <p:pipe port="not-matched" step="split-pivot"/> </p:input> </ix:sort> <p:identity> <p:input port="source"> <p:pipe port="result" step="less"/> <p:pipe port="matched" step="split"/> <p:pipe port="result" step="greater"/> </p:input> </p:identity> </p:group> </p:otherwise> </p:choose> </p:declare-step> <p:for-each> <p:iteration-source select="/root/doc"/> <p:identity/> </p:for-each> <ix:sort key="/doc"/> <p:wrap-sequence wrapper="root"/> </p:declare-step>
Zilog Z80000 Assembly[edit]
This implementation is in z80 assembly code. The processor is really ancient, and so it's 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 does not 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
TorqueScript[edit]
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;
}
FORTRAN 90/95[edit]
This implementation of quicksort in FORTRAN 90/95 is non-recursive, and choose as pivot element the median of three (the first, last and middle element of the list). It also uses insertion sort to sort lists with less than 10 elements.
This implementation of Quicksort closely follows the one that can be found in the FORTRAN 90/95 GPL library AFNL.
! *********************************** ! * Subroutine Qsort(X, Ipt) ! * ! *********************************** ! * Sort Array X(:) in ascendent order ! * If present Ipt, a pointer with the ! * changes is returned in Ipt. ! *********************************** Type Limits Integer :: Ileft, Iright End Type Limits ! For a list with Isw number of elements or ! less use Insrt Integer, Parameter :: Isw = 10 Real (kind=4), Intent (inout) :: X(:) Integer, Intent (out), Optional :: Ipt(:) Integer :: I, Ipvn, Ileft, Iright, ISpos, ISmax Integer, Allocatable :: IIpt(:) Type (Limits), Allocatable :: Stack(:) Allocate(Stack(Size(X))) Stack(:)%Ileft = 0 If (Present(Ipt)) Then Forall (I=1:Size(Ipt)) Ipt(I) = I ! Iniitialize the stack Ispos = 1 Ismax = 1 Stack(ISpos)%Ileft = 1 Stack(ISpos)%Iright = Size(X) Do While (Stack(ISpos)%Ileft /= 0) Ileft = Stack(ISPos)%Ileft Iright = Stack(ISPos)%Iright If (Iright-Ileft <= Isw) Then CALL InsrtLC(X, Ipt, Ileft,Iright) ISpos = ISPos + 1 Else Ipvn = ChoosePiv(X, Ileft, Iright) Ipvn = Partition(X, Ileft, Iright, Ipvn, Ipt) Stack(ISmax+1)%Ileft = Ileft Stack(ISmax+1) %Iright = Ipvn-1 Stack(ISmax+2)%Ileft = Ipvn + 1 Stack(ISmax+2)%Iright = Iright ISpos = ISpos + 1 ISmax = ISmax + 2 End If End Do Else ! Iniitialize the stack Ispos = 1 Ismax = 1 Stack(ISpos)%Ileft = 1 Stack(ISpos)%Iright = Size(X) Allocate(IIpt(10)) Do While (Stack(ISpos)%Ileft /= 0) ! Write(*,*)Ispos, ISmax Ileft = Stack(ISPos)%Ileft Iright = Stack(ISPos)%Iright If (Iright-Ileft <= Isw) Then CALL InsrtLC(X, IIpt, Ileft, Iright) ISpos = ISPos + 1 Else Ipvn = ChoosePiv(X, Ileft, Iright) Ipvn = Partition(X, Ileft, Iright, Ipvn) Stack(ISmax+1)%Ileft = Ileft Stack(ISmax+1) %Iright = Ipvn-1 Stack(ISmax+2)%Ileft = Ipvn + 1 Stack(ISmax+2)%Iright = Iright ISpos = ISpos + 1 ISmax = ISmax + 2 End If End Do Deallocate(IIpt) End If Deallocate(Stack) Return CONTAINS ! *********************************** Integer Function ChoosePiv(XX, IIleft, IIright) Result (IIpv) ! *********************************** ! * Choose a Pivot element from XX(Ileft:Iright) ! * for Qsort. This routine chooses the median ! * of the first, last and mid element of the ! * list. ! *********************************** Real (kind=4), Intent (in) :: XX(:) Integer, Intent (in) :: IIleft, IIright Real (kind=4) :: XXcp(3) Integer :: IIpt(3), IImd IImd = Int((IIleft+IIright)/2) XXcp(1) = XX(IIleft) XXcp(2) = XX(IImd) XXcp(3) = XX(IIright) IIpt = (/1,2,3/) CALL InsrtLC(XXcp, IIpt, 1, 3) Select Case (IIpt(2)) Case (1) IIpv = IIleft Case (2) IIpv = IImd Case (3) IIpv = IIright End Select Return End Function ChoosePiv ! *********************************** Subroutine InsrtLC(XX, IIpt, IIl, IIr) ! *********************************** ! * Perform an insertion sort of the list ! * XX(:) between index values IIl and IIr. ! * IIpt(:) returns the permutations ! * made to sort. ! *********************************** Real (kind=4), Intent (inout) :: XX(:) Integer, Intent (inout) :: IIpt(:) Integer, Intent (in) :: IIl, IIr Real (kind=4) :: RRtmp Integer :: II, JJ, IItmp Do II = IIl+1, IIr RRtmp = XX(II) Do JJ = II-1, 1, -1 If (RRtmp < XX(JJ)) Then XX(JJ+1) = XX(JJ) CALL Swap_IN(IIpt, JJ, JJ+1) Else Exit End If End Do XX(JJ+1) = RRtmp End Do Return End Subroutine InsrtLC End Subroutine Qsort ! *********************************** ! * Integer Function Partition(X, Ileft, Iright, Ipv, Ipt) Result (Ipvfn) ! * ! *********************************** ! * This routine arranges the array X ! * between the index values Ileft and Iright ! * positioning elements smallers than ! * X(Ipv) at the left and the others ! * at the right. ! * Internal routine used by Qsort. ! *********************************** Real (kind=4), Intent (inout) :: X(:) Integer, Intent (in) :: Ileft, Iright, Ipv Integer, Intent (inout), Optional :: Ipt(:) Real (kind=4) :: Rpv Integer :: I Rpv = X(Ipv) CALL Swap(X, Ipv, Iright) If (Present(Ipt)) CALL Swap_IN(Ipt, Ipv, Iright) Ipvfn = Ileft If (Present(Ipt)) Then Do I = Ileft, Iright-1 If (X(I) <= Rpv) Then CALL Swap(X, I, Ipvfn) CALL Swap_IN(Ipt, I, Ipvfn) Ipvfn = Ipvfn + 1 End If End Do Else Do I = Ileft, Iright-1 If (X(I) <= Rpv) Then CALL Swap(X, I, Ipvfn) Ipvfn = Ipvfn + 1 End If End Do End If CALL Swap(X, Ipvfn, Iright) If (Present(Ipt)) CALL Swap_IN(Ipt, Ipvfn, Iright) Return End Function Partition ! *********************************** ! * Subroutine Swap(X, I, J) ! * ! *********************************** ! * Swaps elements I and J of array X(:). ! *********************************** Real (kind=4), Intent (inout) :: X(:) Integer, Intent (in) :: I, J Real (kind=4) :: Itmp Itmp = X(I) X(I) = X(J) X(J) = Itmp Return End Subroutine Swap ! *********************************** ! * Subroutine Swap_IN(X, I, J) ! * ! *********************************** ! * Swaps elements I and J of array X(:). ! *********************************** Integer, Intent (inout) :: X(:) Integer, Intent (in) :: I, J Integer :: Itmp Itmp = X(I) X(I) = X(J) X(J) = Itmp Return End Subroutine Swap_IN
