Nemerle Translation of: Haskell A little less clean and concise than Haskell, but essentially the same. using System; using System.Console; using Nemerle.Collections.NList; module Quicksort { Qsort[T] (x : list[T]) : list[T] where T : IComparable { |[] => [] |x::xs => Qsort($[y|y in xs, (y.CompareTo(x) < 0)]) + [x] + Qsort($[y|y in xs, (y.CompareTo(x) > 0)]) } Main() : void { def empty = []; def single = [2]; def several = [2, 6, 1, 7, 3, 9, 4]; WriteLine(Qsort(empty)); WriteLine(Qsort(single)); WriteLine(Qsort(several)); } } NetRexx This sample implements both the simple and in place algorithms as described in the task's description: /* NetRexx */ options replace format comments java crossref savelog symbols binary import java.util.List placesList = [String - "UK London", "US New York", "US Boston", "US Washington" - , "UK Washington", "US Birmingham", "UK Birmingham", "UK Boston" - ] lists = [ - placesList - , quickSortSimple(String[] Arrays.copyOf(placesList, placesList.length)) - , quickSortInplace(String[] Arrays.copyOf(placesList, placesList.length)) - ] loop ln = 0 to lists.length - 1 cl = lists[ln] loop ct = 0 to cl.length - 1 say cl[ct] end ct say end ln return method quickSortSimple(array = String[]) public constant binary returns String[] rl = String[array.length] al = List quickSortSimple(Arrays.asList(array)) al.toArray(rl) return rl method quickSortSimple(array = List) public constant binary returns ArrayList if array.size > 1 then do less = ArrayList() equal = ArrayList() greater = ArrayList() pivot = array.get(Random().nextInt(array.size - 1)) loop x_ = 0 to array.size - 1 if (Comparable array.get(x_)).compareTo(Comparable pivot) < 0 then less.add(array.get(x_)) if (Comparable array.get(x_)).compareTo(Comparable pivot) = 0 then equal.add(array.get(x_)) if (Comparable array.get(x_)).compareTo(Comparable pivot) > 0 then greater.add(array.get(x_)) end x_ less = quickSortSimple(less) greater = quickSortSimple(greater) out = ArrayList(array.size) out.addAll(less) out.addAll(equal) out.addAll(greater) array = out end return ArrayList array method quickSortInplace(array = String[]) public constant binary returns String[] rl = String[array.length] al = List quickSortInplace(Arrays.asList(array)) al.toArray(rl) return rl method quickSortInplace(array = List, ixL = int 0, ixR = int array.size - 1) public constant binary returns ArrayList if ixL < ixR then do ixP = int ixL + (ixR - ixL) % 2 ixP = quickSortInplacePartition(array, ixL, ixR, ixP) quickSortInplace(array, ixL, ixP - 1) quickSortInplace(array, ixP + 1, ixR) end array = ArrayList(array) return ArrayList array method quickSortInplacePartition(array = List, ixL = int, ixR = int, ixP = int) public constant binary returns int pivotValue = array.get(ixP) rValue = array.get(ixR) array.set(ixP, rValue) array.set(ixR, pivotValue) ixStore = ixL loop i_ = ixL to ixR - 1 iValue = array.get(i_) if (Comparable iValue).compareTo(Comparable pivotValue) < 0 then do storeValue = array.get(ixStore) array.set(i_, storeValue) array.set(ixStore, iValue) ixStore = ixStore + 1 end end i_ storeValue = array.get(ixStore) rValue = array.get(ixR) array.set(ixStore, rValue) array.set(ixR, storeValue) return ixStore Output: UK London US New York US Boston US Washington UK Washington US Birmingham UK Birmingham UK Boston UK Birmingham UK Boston UK London UK Washington US Birmingham US Boston US New York US Washington UK Birmingham UK Boston UK London UK Washington US Birmingham US Boston US New York US Washington Nial quicksort is fork [ >= [1 first,tally], pass, link [ quicksort sublist [ < [pass, first], pass ], sublist [ match [pass,first],pass ], quicksort sublist [ > [pass,first], pass ] ] ] Using it. |quicksort [5, 8, 7, 4, 3] =3 4 5 7 8 Nim proc quickSort[T](a: var openarray[T], inl = 0, inr = -1) = var r = if inr >= 0: inr else: a.high var l = inl let n = r - l + 1 if n < 2: return let p = a[l + 3 * n div 4] while l <= r: if a[l] < p: inc l continue if a[r] > p: dec r continue if l <= r: swap a[l], a[r] inc l dec r quickSort(a, inl, r) quickSort(a, l, inr) var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782] quickSort a echo a Output: @[-31, 0, 2, 2, 4, 65, 83, 99, 782] Nix let qs = l: if l == [] then [] else with builtins; let x = head l; xs = tail l; low = filter (a: a < x) xs; high = filter (a: a >= x) xs; in qs low ++ [x] ++ qs high; in qs [4 65 2 (-31) 0 99 83 782] Output: [ -31 0 2 4 65 83 99 782 ] Objeck class QuickSort { function : Main(args : String[]) ~ Nil { array := [1, 3, 5, 7, 9, 8, 6, 4, 2]; Sort(array); each(i : array) { array[i]->PrintLine(); }; } function : Sort(array : Int[]) ~ Nil { size := array->Size(); if(size <= 1) { return; }; Sort(array, 0, size - 1); } function : native : Sort(array : Int[], low : Int, high : Int) ~ Nil { i := low; j := high; pivot := array[low + (high-low)/2]; while(i <= j) { while(array[i] < pivot) { i+=1; }; while(array[j] > pivot) { j-=1; }; if (i <= j) { temp := array[i]; array[i] := array[j]; array[j] := temp; i+=1; j-=1; }; }; if(low < j) { Sort(array, low, j); }; if(i < high) { Sort(array, i, high); }; } } Objective-C The latest XCode compiler is assumed with ARC enabled. void quicksortInPlace(NSMutableArray *array, NSInteger first, NSInteger last, NSComparator comparator) { if (first >= last) return; id pivot = array[(first + last) / 2]; NSInteger left = first; NSInteger right = last; while (left <= right) { while (comparator(array[left], pivot) == NSOrderedAscending) left++; while (comparator(array[right], pivot) == NSOrderedDescending) right--; if (left <= right) [array exchangeObjectAtIndex:left++ withObjectAtIndex:right--]; } quicksortInPlace(array, first, right, comparator); quicksortInPlace(array, left, last, comparator); } NSArray* quicksort(NSArray *unsorted, NSComparator comparator) { NSMutableArray *a = [NSMutableArray arrayWithArray:unsorted]; quicksortInPlace(a, 0, a.count - 1, comparator); return a; } int main(int argc, const char * argv[]) { @autoreleasepool { NSArray *a = @[ @1, @3, @5, @7, @9, @8, @6, @4, @2 ]; NSLog(@"Unsorted: %@", a); NSLog(@"Sorted: %@", quicksort(a, ^(id x, id y) { return [x compare:y]; })); NSArray *b = @[ @"Emil", @"Peg", @"Helen", @"Juergen", @"David", @"Rick", @"Barb", @"Mike", @"Tom" ]; NSLog(@"Unsorted: %@", b); NSLog(@"Sorted: %@", quicksort(b, ^(id x, id y) { return [x compare:y]; })); } return 0; } Output: Unsorted: ( 1, 3, 5, 7, 9, 8, 6, 4, 2 ) Sorted: ( 1, 2, 3, 4, 5, 6, 7, 8, 9 ) Unsorted: ( Emil, Peg, Helen, Juergen, David, Rick, Barb, Mike, Tom ) Sorted: ( Barb, David, Emil, Helen, Juergen, Mike, Peg, Rick, Tom ) OCaml let rec quicksort gt = function | [] -> [] | x::xs -> let ys, zs = List.partition (gt x) xs in (quicksort gt ys) @ (x :: (quicksort gt zs)) let _ = quicksort (>) [4; 65; 2; -31; 0; 99; 83; 782; 1] Octave Translation of: MATLAB (The MATLAB version works as is in Octave, provided that the code is put in a file named quicksort.m, and everything below the return must be typed in the prompt of course) function f=quicksort(v) % v must be a column vector f = v; n=length(v); if(n > 1) vl = min(f); vh = max(f); % min, max p = (vl+vh)*0.5; % pivot ia = find(f < p); ib = find(f == p); ic=find(f > p); f = [quicksort(f(ia)); f(ib); quicksort(f(ic))]; end endfunction N=30; v=rand(N,1); tic,u=quicksort(v); toc u Oforth Oforth built-in sort uses quick sort algorithm (see lang/collect/ListBuffer.of for implementation) : [ 5, 8, 2, 3, 4, 1 ] sort ooRexx Translation of: Python a = .array~Of(4, 65, 2, -31, 0, 99, 83, 782, 1) say 'before:' a~toString( ,', ') a = quickSort(a) say ' after:' a~toString( ,', ') exit ::routine quickSort use arg arr -- the array to be sorted less = .array~new pivotList = .array~new more = .array~new if arr~items <= 1 then return arr else do pivot = arr[1] do i over arr if i < pivot then less~append(i) else if i > pivot then more~append(i) else pivotList~append(i) end less = quickSort(less) more = quickSort(more) return less~~appendAll(pivotList)~~appendAll(more) end Output: before: 4, 65, 2, -31, 0, 99, 83, 782, 1 after: -31, 0, 1, 2, 4, 65, 83, 99, 782 Oz declare fun {QuickSort Xs} case Xs of nil then nil [] Pivot|Xr then fun {IsSmaller X} X < Pivot end Smaller Larger in {List.partition Xr IsSmaller ?Smaller ?Larger} {Append {QuickSort Smaller} Pivot|{QuickSort Larger}} end end in {Show {QuickSort [3 1 4 1 5 9 2 6 5]}} PARI/GP quickSort(v)={ if(#v<2, return(v)); my(less=List(),more=List(),same=List(),pivot); pivot=median([v[random(#v)+1],v[random(#v)+1],v[random(#v)+1]]); \\ Middle-of-three for(i=1,#v, if(v[i]>1] }; Pascal { X is array of LongInt } Procedure QuickSort ( Left, Right : LongInt ); Var i, j : LongInt; tmp, pivot : LongInt; { tmp & pivot are the same type as the elements of array } Begin i:=Left; j:=Right; pivot := X[(Left + Right) shr 1]; // pivot := X[(Left + Rigth) div 2] Repeat While pivot > X[i] Do i:=i+1; While pivot < X[j] Do j:=j-1; If i<=j Then Begin tmp:=X[i]; X[i]:=X[j]; X[j]:=tmp; j:=j-1; i:=i+1; End; Until i>j; If Left= $p, @_); } my @a = (4, 65, 2, -31, 0, 99, 83, 782, 1); @a = quick_sort @a; print "@a\n"; Perl 6 # Empty list sorts to the empty list multi quicksort([]) { () } # Otherwise, extract first item as pivot... multi quicksort([$pivot, *@rest]) { # Partition. my $before := @rest.grep(* before $pivot); my $after := @rest.grep(* !before $pivot); # Sort the partitions. flat quicksort($before), $pivot, quicksort($after) } Note that $before and $after are bound to lazy lists, so the partitions can (at least in theory) be sorted in parallel. Phix function quick_sort(sequence x) -- -- put x into ascending order using recursive quick sort -- integer n, last, mid object xi, midval n = length(x) if n<2 then return x -- already sorted (trivial case) end if mid = floor((n+1)/2) midval = x[mid] x[mid] = x[1] last = 1 for i=2 to n do xi = x[i] if xi $pivot){ $gt[] = $val; } } return array_merge(quicksort($loe),array($pivot_key=>$pivot),quicksort($gt)); } $arr = array(1, 3, 5, 7, 9, 8, 6, 4, 2); $arr = quicksort($arr); echo implode(',',$arr); 1,2,3,4,5,6,7,8,9 function quickSort(array $array) { // base case if (empty($array)) { return $array; } $head = array_shift($array); $tail = $array; $lesser = array_filter($tail, function ($item) use ($head) { return $item <= $head; }); $bigger = array_filter($tail, function ($item) use ($head) { return $item > $head; }); return array_merge(quickSort($lesser), [$head], quickSort($bigger)); } $testCase = [1, 4, 8, 2, 8, 0, 2, 8]; $result = quickSort($testCase); echo sprintf("[%s] ==> [%s]\n", implode(', ', $testCase), implode(', ', $result)); [1, 4, 8, 2, 8, 0, 2, 8] ==> [0, 1, 2, 2, 4, 8, 8, 8] PicoLisp (de quicksort (L) (if (cdr L) (let Pivot (car L) (append (quicksort (filter '((A) (< A Pivot)) (cdr L))) (filter '((A) (= A Pivot)) L ) (quicksort (filter '((A) (> A Pivot)) (cdr L)))) ) L) ) PL/I DCL (T(20)) FIXED BIN(31); /* scratch space of length N */ QUICKSORT: PROCEDURE (A,AMIN,AMAX,N) RECURSIVE ; DECLARE (A(*)) FIXED BIN(31); DECLARE (N,AMIN,AMAX) FIXED BIN(31) NONASGN; DECLARE (I,J,IA,IB,IC,PIV) FIXED BIN(31); DECLARE (P,Q) POINTER; DECLARE (AP(1)) FIXED BIN(31) BASED(P); IF(N <= 1)THEN RETURN; IA=0; IB=0; IC=N+1; PIV=(AMIN+AMAX)/2; DO I=1 TO N; IF(A(I) < PIV)THEN DO; IA+=1; A(IA)=A(I); END; ELSE IF(A(I) > PIV) THEN DO; IC-=1; T(IC)=A(I); END; ELSE DO; IB+=1; T(IB)=A(I); END; END; DO I=1 TO IB; A(I+IA)=T(I); END; DO I=IC TO N; A(I)=T(N+IC-I); END; P=ADDR(A(IC)); IC=N+1-IC; IF(IA > 1) THEN CALL QUICKSORT(A, AMIN, PIV-1,IA); IF(IC > 1) THEN CALL QUICKSORT(AP,PIV+1,AMAX, IC); RETURN; END QUICKSORT; MINMAX: PROC(A,AMIN,AMAX,N); DCL (AMIN,AMAX) FIXED BIN(31), (N,A(*)) FIXED BIN(31) NONASGN ; DCL (I,X,Y) FIXED BIN(31); AMIN=A(N); AMAX=AMIN; DO I=1 TO N-1; X=A(I); Y=A(I+1); IF (X < Y)THEN DO; IF (X < AMIN) THEN AMIN=X; IF (Y > AMAX) THEN AMAX=Y; END; ELSE DO; IF (X > AMAX) THEN AMAX=X; IF (Y < AMIN) THEN AMIN=Y; END; END; RETURN; END MINMAX; CALL MINMAX(A,AMIN,AMAX,N); CALL QUICKSORT(A,AMIN,AMAX,N); PowerShell First solution Function SortThree( [Array] $data ) { if( $data[ 0 ] -gt $data[ 1 ] ) { if( $data[ 0 ] -lt $data[ 2 ] ) { $data = $data[ 1, 0, 2 ] } elseif ( $data[ 1 ] -lt $data[ 2 ] ){ $data = $data[ 1, 2, 0 ] } else { $data = $data[ 2, 1, 0 ] } } else { if( $data[ 0 ] -gt $data[ 2 ] ) { $data = $data[ 2, 0, 1 ] } elseif( $data[ 1 ] -gt $data[ 2 ] ) { $data = $data[ 0, 2, 1 ] } } $data } Function QuickSort( [Array] $data, $rand = ( New-Object Random ) ) { $datal = $data.length if( $datal -gt 3 ) { [void] $datal-- $median = ( SortThree $data[ 0, ( $rand.Next( 1, $datal - 1 ) ), -1 ] )[ 1 ] $lt = @() $eq = @() $gt = @() $data | ForEach-Object { if( $_ -lt $median ) { $lt += $_ } elseif( $_ -eq $median ) { $eq += $_ } else { $gt += $_ } } $lt = ( QuickSort $lt $rand ) $gt = ( QuickSort $gt $rand ) $data = @($lt) + $eq + $gt } elseif( $datal -eq 3 ) { $data = SortThree( $data ) } elseif( $datal -eq 2 ) { if( $data[ 0 ] -gt $data[ 1 ] ) { $data = $data[ 1, 0 ] } } $data } QuickSort 5,3,1,2,4 QuickSort 'e','c','a','b','d' QuickSort 0.5,0.3,0.1,0.2,0.4 $l = 100; QuickSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } ) Another solution function quicksort($array) { $less, $equal, $greater = @(), @(), @() if( $array.Count -gt 1 ) { $pivot = $array[0] foreach( $x in $array) { if($x -lt $pivot) { $less += @($x) } elseif ($x -eq $pivot) { $equal += @($x)} else { $greater += @($x) } } $array = (@(quicksort $less) + @($equal) + @(quicksort $greater)) } $array } $array = @(60, 21, 19, 36, 63, 8, 100, 80, 3, 87, 11) "$(quicksort $array)" The output is: 3 8 11 19 21 36 60 63 80 87 100 Prolog qsort( [], [] ). qsort( [H|U], S ) :- splitBy(H, U, L, R), qsort(L, SL), qsort(R, SR), append(SL, [H|SR], S). % splitBy( H, U, LS, RS ) % True if LS = { L in U | L <= H }; RS = { R in U | R > H } splitBy( _, [], [], []). splitBy( H, [U|T], [U|LS], RS ) :- U =< H, splitBy(H, T, LS, RS). splitBy( H, [U|T], LS, [U|RS] ) :- U > H, splitBy(H, T, LS, RS). PureBasic Procedure qSort(Array a(1), firstIndex, lastIndex) Protected low, high, pivotValue low = firstIndex high = lastIndex pivotValue = a((firstIndex + lastIndex) / 2) Repeat While a(low) < pivotValue low + 1 Wend While a(high) > pivotValue high - 1 Wend If low <= high Swap a(low), a(high) low + 1 high - 1 EndIf Until low > high If firstIndex < high qSort(a(), firstIndex, high) EndIf If low < lastIndex qSort(a(), low, lastIndex) EndIf EndProcedure Procedure quickSort(Array a(1)) qSort(a(),0,ArraySize(a())) EndProcedure Python def quickSort(arr): less = [] pivotList = [] more = [] if len(arr) <= 1: return arr else: pivot = arr[0] for i in arr: if i < pivot: less.append(i) elif i > pivot: more.append(i) else: pivotList.append(i) less = quickSort(less) more = quickSort(more) return less + pivotList + more a = [4, 65, 2, -31, 0, 99, 83, 782, 1] a = quickSort(a) In a Haskell fashion -- def qsort(L): return (qsort([y for y in L[1:] if y < L[0]]) + L[:1] + qsort([y for y in L[1:] if y >= L[0]])) if len(L) > 1 else L More readable, but still using list comprehensions: def qsort(list): if not list: return [] else: pivot = list[0] less = [x for x in list if x < pivot] more = [x for x in list[1:] if x >= pivot] return qsort(less) + [pivot] + qsort(more) More correctly in some tests: from random import * def qSort(a): if len(a) <= 1: return a else: q = choice(a) return qSort([elem for elem in a if elem < q]) + [q] * a.count(q) + qSort([elem for elem in a if elem > q]) def quickSort(a): if len(a) <= 1: return a else: less = [] more = [] pivot = choice(a) for i in a: if i < pivot: less.append(i) if i > pivot: more.append(i) less = quickSort(less) more = quickSort(more) return less + [pivot] * a.count(pivot) + more Returning a new list: def qsort(array): if len(array) < 2: return array head, *tail = array less = qsort([i for i in tail if i < head]) more = qsort([i for i in tail if i >= head]) return less + [head] + more Sorting a list in place: def quicksort(array): _quicksort(array, 0, len(array) - 1) def _quicksort(array, start, stop): if stop - start > 0: pivot, left, right = array[start], start, stop while left <= right: while array[left] < pivot: left += 1 while array[right] > pivot: right -= 1 if left <= right: array[left], array[right] = array[right], array[left] left += 1 right -= 1 _quicksort(array, start, right) _quicksort(array, left, stop) Qi (define keep _ [] -> [] Pred [A|Rest] -> [A | (keep Pred Rest)] where (Pred A) Pred [_|Rest] -> (keep Pred Rest)) (define quicksort [] -> [] [A|R] -> (append (quicksort (keep (>= A) R)) [A] (quicksort (keep (< A) R)))) (quicksort [6 8 5 9 3 2 2 1 4 7]) R Translation of: Octave qsort <- function(v) { if ( length(v) > 1 ) { pivot <- (min(v) + max(v))/2.0 # Could also use pivot <- median(v) c(qsort(v[v < pivot]), v[v == pivot], qsort(v[v > pivot])) } else v } N <- 100 vs <- runif(N) system.time(u <- qsort(vs)) print(u) Racket #lang racket (define (quicksort < l) (match l ['() '()] [(cons x xs) (let-values ([(xs-gte xs-lt) (partition (curry < x) xs)]) (append (quicksort < xs-lt) (list x) (quicksort < xs-gte)))])) Examples (quicksort < '(8 7 3 6 4 5 2)) ;returns '(2 3 4 5 6 7 8) (quicksort string@.L then p=@.L else do; p=@.?; @.?=@.L; end else if @.?<@.L then p=@.L else if @.?>@.H then do; p=@.H; @.H=@.L; end else do; p=@.?; @.?=@.L; end j=L+1; k=h do forever do j=j while j<=k & @.j<=p; end /*a tinie-tiny loop.*/ do k=k by -1 while j =p; end /*another " " */ if j>=k then leave /*segment finished? */ _=@.j; @.j=@.k; @.k=_ /*swap J&K elements.*/ end /*forever*/ $=$+1 k=j-1; @.L=@.k; @.k=p if j<=? then do; a.$=j; b.$=H-j+1; $=$+1; a.$=L; b.$=k-L; end else do; a.$=L; b.$=k-L; $=$+1; a.$=j; b.$=H-j+1; end end /*while $¬==0*/ return /*--------------------------------------------------------------------------------------*/ show@: w=length(#); do j=1 for #; say 'element' right(j,w) arg(1)":" @.j; end say copies(' ', maxL + w + 22) /*display a separator (between outputs)*/ return /*-------------------------------------------------------------------------------------------------------------------------------------------------------*/ gen@: @.=; maxL=0 /*assign a default value for the array.*/ @.1 = " Rivers that form part of a (USA) state's border " /*this value is adjusted later to include a prefix & suffix.*/ @.2 = '=' /*this value is expanded later. */ @.3 = "Perdido River Alabama, Florida" @.4 = "Chattahoochee River Alabama, Georgia" @.5 = "Tennessee River Alabama, Kentucky, Mississippi, Tennessee" @.6 = "Colorado River Arizona, California, Nevada, Baja California (Mexico)" @.7 = "Mississippi River Arkansas, Illinois, Iowa, Kentucky, Minnesota, Mississippi, Missouri, Tennessee, Louisiana, Wisconsin" @.8 = "St. Francis River Arkansas, Missouri" @.9 = "Poteau River Arkansas, Oklahoma" @.10 = "Arkansas River Arkansas, Oklahoma" @.11 = "Red River (Mississippi watershed) Arkansas, Oklahoma, Texas" @.12 = "Byram River Connecticut, New York" @.13 = "Pawcatuck River Connecticut, Rhode Island and Providence Plantations" @.14 = "Delaware River Delaware, New Jersey, New York, Pennsylvania" @.15 = "Potomac River District of Columbia, Maryland, Virginia, West Virginia" @.16 = "St. Marys River Florida, Georgia" @.17 = "Chattooga River Georgia, South Carolina" @.18 = "Tugaloo River Georgia, South Carolina" @.19 = "Savannah River Georgia, South Carolina" @.20 = "Snake River Idaho, Oregon, Washington" @.21 = "Wabash River Illinois, Indiana" @.22 = "Ohio River Illinois, Indiana, Kentucky, Ohio, West Virginia" @.23 = "Great Miami River (mouth only) Indiana, Ohio" @.24 = "Des Moines River Iowa, Missouri" @.25 = "Big Sioux River Iowa, South Dakota" @.26 = "Missouri River Kansas, Iowa, Missouri, Nebraska, South Dakota" @.27 = "Tug Fork River Kentucky, Virginia, West Virginia" @.28 = "Big Sandy River Kentucky, West Virginia" @.29 = "Pearl River Louisiana, Mississippi" @.30 = "Sabine River Louisiana, Texas" @.31 = "Monument Creek Maine, New Brunswick (Canada)" @.32 = "St. Croix River Maine, New Brunswick (Canada)" @.33 = "Piscataqua River Maine, New Hampshire" @.34 = "St. Francis River Maine, Quebec (Canada)" @.35 = "St. John River Maine, Quebec (Canada)" @.36 = "Pocomoke River Maryland, Virginia" @.37 = "Palmer River Massachusetts, Rhode Island and Providence Plantations" @.38 = "Runnins River Massachusetts, Rhode Island and Providence Plantations" @.39 = "Montreal River Michigan (upper peninsula), Wisconsin" @.40 = "Detroit River Michigan, Ontario (Canada)" @.41 = "St. Clair River Michigan, Ontario (Canada)" @.42 = "St. Marys River Michigan, Ontario (Canada)" @.43 = "Brule River Michigan, Wisconsin" @.44 = "Menominee River Michigan, Wisconsin" @.45 = "Red River of the North Minnesota, North Dakota" @.46 = "Bois de Sioux River Minnesota, North Dakota, South Dakota" @.47 = "Pigeon River Minnesota, Ontario (Canada)" @.48 = "Rainy River Minnesota, Ontario (Canada)" @.49 = "St. Croix River Minnesota, Wisconsin" @.50 = "St. Louis River Minnesota, Wisconsin" @.51 = "Halls Stream New Hampshire, Canada" @.52 = "Salmon Falls River New Hampshire, Maine" @.53 = "Connecticut River New Hampshire, Vermont" @.54 = "Arthur Kill New Jersey, New York (tidal strait)" @.55 = "Kill Van Kull New Jersey, New York (tidal strait)" @.56 = "Hudson River (lower part only) New Jersey, New York" @.57 = "Rio Grande New Mexico, Texas, Tamaulipas (Mexico), Nuevo Leon (Mexico), Coahuila de Zaragoza (Mexico), Chihuahua (Mexico)" @.58 = "Niagara River New York, Ontario (Canada)" @.59 = "St. Lawrence River New York, Ontario (Canada)" @.60 = "Poultney River New York, Vermont" @.61 = "Catawba River North Carolina, South Carolina" @.62 = "Blackwater River North Carolina, Virginia" @.63 = "Columbia River Oregon, Washington" do #=1 until @.#=='' /*find how many entries in array, and */ maxL=max(maxL, length(@.#)) /* also find the maximum width entry.*/ end /*#*/ #=#-1 /*adjust the highest element number. */ @.1=center(@.1, maxL, '-') /* " " header information. */ @.2=copies(@.2, maxL) /* " " " separator. */ return output element 1 before sort: ------------------------------------------------ Rivers that form part of a (USA) state's border ------------------------------------------------- element 2 before sort: ================================================================================================================================================== element 3 before sort: Perdido River Alabama, Florida element 4 before sort: Chattahoochee River Alabama, Georgia element 5 before sort: Tennessee River Alabama, Kentucky, Mississippi, Tennessee element 6 before sort: Colorado River Arizona, California, Nevada, Baja California (Mexico) element 7 before sort: Mississippi River Arkansas, Illinois, Iowa, Kentucky, Minnesota, Mississippi, Missouri, Tennessee, Louisiana, Wisconsin element 8 before sort: St. Francis River Arkansas, Missouri element 9 before sort: Poteau River Arkansas, Oklahoma element 10 before sort: Arkansas River Arkansas, Oklahoma element 11 before sort: Red River (Mississippi watershed) Arkansas, Oklahoma, Texas element 12 before sort: Byram River Connecticut, New York element 13 before sort: Pawcatuck River Connecticut, Rhode Island and Providence Plantations element 14 before sort: Delaware River Delaware, New Jersey, New York, Pennsylvania element 15 before sort: Potomac River District of Columbia, Maryland, Virginia, West Virginia element 16 before sort: St. Marys River Florida, Georgia element 17 before sort: Chattooga River Georgia, South Carolina element 18 before sort: Tugaloo River Georgia, South Carolina element 19 before sort: Savannah River Georgia, South Carolina element 20 before sort: Snake River Idaho, Oregon, Washington element 21 before sort: Wabash River Illinois, Indiana element 22 before sort: Ohio River Illinois, Indiana, Kentucky, Ohio, West Virginia element 23 before sort: Great Miami River (mouth only) Indiana, Ohio element 24 before sort: Des Moines River Iowa, Missouri element 25 before sort: Big Sioux River Iowa, South Dakota element 26 before sort: Missouri River Kansas, Iowa, Missouri, Nebraska, South Dakota element 27 before sort: Tug Fork River Kentucky, Virginia, West Virginia element 28 before sort: Big Sandy River Kentucky, West Virginia element 29 before sort: Pearl River Louisiana, Mississippi element 30 before sort: Sabine River Louisiana, Texas element 31 before sort: Monument Creek Maine, New Brunswick (Canada) element 32 before sort: St. Croix River Maine, New Brunswick (Canada) element 33 before sort: Piscataqua River Maine, New Hampshire element 34 before sort: St. Francis River Maine, Quebec (Canada) element 35 before sort: St. John River Maine, Quebec (Canada) element 36 before sort: Pocomoke River Maryland, Virginia element 37 before sort: Palmer River Massachusetts, Rhode Island and Providence Plantations element 38 before sort: Runnins River Massachusetts, Rhode Island and Providence Plantations element 39 before sort: Montreal River Michigan (upper peninsula), Wisconsin element 40 before sort: Detroit River Michigan, Ontario (Canada) element 41 before sort: St. Clair River Michigan, Ontario (Canada) element 42 before sort: St. Marys River Michigan, Ontario (Canada) element 43 before sort: Brule River Michigan, Wisconsin element 44 before sort: Menominee River Michigan, Wisconsin element 45 before sort: Red River of the North Minnesota, North Dakota element 46 before sort: Bois de Sioux River Minnesota, North Dakota, South Dakota element 47 before sort: Pigeon River Minnesota, Ontario (Canada) element 48 before sort: Rainy River Minnesota, Ontario (Canada) element 49 before sort: St. Croix River Minnesota, Wisconsin element 50 before sort: St. Louis River Minnesota, Wisconsin element 51 before sort: Halls Stream New Hampshire, Canada element 52 before sort: Salmon Falls River New Hampshire, Maine element 53 before sort: Connecticut River New Hampshire, Vermont element 54 before sort: Arthur Kill New Jersey, New York (tidal strait) element 55 before sort: Kill Van Kull New Jersey, New York (tidal strait) element 56 before sort: Hudson River (lower part only) New Jersey, New York element 57 before sort: Rio Grande New Mexico, Texas, Tamaulipas (Mexico), Nuevo Leon (Mexico), Coahuila De Zaragoza (Mexico), Chihuahua (Mexico) element 58 before sort: Niagara River New York, Ontario (Canada) element 59 before sort: St. Lawrence River New York, Ontario (Canada) element 60 before sort: Poultney River New York, Vermont element 61 before sort: Catawba River North Carolina, South Carolina element 62 before sort: Blackwater River North Carolina, Virginia element 63 before sort: Columbia River Oregon, Washington element 1 after sort: ------------------------------------------------ Rivers that form part of a (USA) state's border ------------------------------------------------- element 2 after sort: ================================================================================================================================================== element 3 after sort: Arkansas River Arkansas, Oklahoma element 4 after sort: Arthur Kill New Jersey, New York (tidal strait) element 5 after sort: Big Sandy River Kentucky, West Virginia element 6 after sort: Big Sioux River Iowa, South Dakota element 7 after sort: Blackwater River North Carolina, Virginia element 8 after sort: Bois de Sioux River Minnesota, North Dakota, South Dakota element 9 after sort: Brule River Michigan, Wisconsin element 10 after sort: Byram River Connecticut, New York element 11 after sort: Catawba River North Carolina, South Carolina element 12 after sort: Chattahoochee River Alabama, Georgia element 13 after sort: Chattooga River Georgia, South Carolina element 14 after sort: Colorado River Arizona, California, Nevada, Baja California (Mexico) element 15 after sort: Columbia River Oregon, Washington element 16 after sort: Connecticut River New Hampshire, Vermont element 17 after sort: Delaware River Delaware, New Jersey, New York, Pennsylvania element 18 after sort: Des Moines River Iowa, Missouri element 19 after sort: Detroit River Michigan, Ontario (Canada) element 20 after sort: Great Miami River (mouth only) Indiana, Ohio element 21 after sort: Halls Stream New Hampshire, Canada element 22 after sort: Hudson River (lower part only) New Jersey, New York element 23 after sort: Kill Van Kull New Jersey, New York (tidal strait) element 24 after sort: Menominee River Michigan, Wisconsin element 25 after sort: Mississippi River Arkansas, Illinois, Iowa, Kentucky, Minnesota, Mississippi, Missouri, Tennessee, Louisiana, Wisconsin element 26 after sort: Missouri River Kansas, Iowa, Missouri, Nebraska, South Dakota element 27 after sort: Montreal River Michigan (upper peninsula), Wisconsin element 28 after sort: Monument Creek Maine, New Brunswick (Canada) element 29 after sort: Niagara River New York, Ontario (Canada) element 30 after sort: Ohio River Illinois, Indiana, Kentucky, Ohio, West Virginia element 31 after sort: Palmer River Massachusetts, Rhode Island and Providence Plantations element 32 after sort: Pawcatuck River Connecticut, Rhode Island and Providence Plantations element 33 after sort: Pearl River Louisiana, Mississippi element 34 after sort: Perdido River Alabama, Florida element 35 after sort: Pigeon River Minnesota, Ontario (Canada) element 36 after sort: Piscataqua River Maine, New Hampshire element 37 after sort: Pocomoke River Maryland, Virginia element 38 after sort: Poteau River Arkansas, Oklahoma element 39 after sort: Potomac River District of Columbia, Maryland, Virginia, West Virginia element 40 after sort: Poultney River New York, Vermont element 41 after sort: Rainy River Minnesota, Ontario (Canada) element 42 after sort: Red River (Mississippi watershed) Arkansas, Oklahoma, Texas element 43 after sort: Red River of the North Minnesota, North Dakota element 44 after sort: Rio Grande New Mexico, Texas, Tamaulipas (Mexico), Nuevo Leon (Mexico), Coahuila De Zaragoza (Mexico), Chihuahua (Mexico) element 45 after sort: Runnins River Massachusetts, Rhode Island and Providence Plantations element 46 after sort: Sabine River Louisiana, Texas element 47 after sort: Salmon Falls River New Hampshire, Maine element 48 after sort: Savannah River Georgia, South Carolina element 49 after sort: Snake River Idaho, Oregon, Washington element 50 after sort: St. Clair River Michigan, Ontario (Canada) element 51 after sort: St. Croix River Maine, New Brunswick (Canada) element 52 after sort: St. Croix River Minnesota, Wisconsin element 53 after sort: St. Francis River Arkansas, Missouri element 54 after sort: St. Francis River Maine, Quebec (Canada) element 55 after sort: St. John River Maine, Quebec (Canada) element 56 after sort: St. Lawrence River New York, Ontario (Canada) element 57 after sort: St. Louis River Minnesota, Wisconsin element 58 after sort: St. Marys River Florida, Georgia element 59 after sort: St. Marys River Michigan, Ontario (Canada) element 60 after sort: Tennessee River Alabama, Kentucky, Mississippi, Tennessee element 61 after sort: Tug Fork River Kentucky, Virginia, West Virginia element 62 after sort: Tugaloo River Georgia, South Carolina element 63 after sort: Wabash River Illinois, Indiana version 2 Translation of: Python The Python code translates very well to ooRexx but here is a way to implement it in classic REXX as well. a = '4 65 2 -31 0 99 83 782 1' do i = 1 to words(a) queue word(a, i) end call quickSort parse pull item do queued() call charout ,item', ' parse pull item end say item exit quickSort: procedure /* In classic Rexx, arguments are passed by value, not by reference so stems cannot be passed as arguments nor used as return values. Putting their contents on the external data queue is a way to bypass this issue. */ /* construct the input stem */ arr.0 = queued() do i = 1 to arr.0 parse pull arr.i end less.0 = 0 pivotList.0 = 0 more.0 = 0 if arr.0 <= 1 then do if arr.0 = 1 then queue arr.1 return end else do pivot = arr.1 do i = 1 to arr.0 item = arr.i select when item < pivot then do j = less.0 + 1 less.j = item less.0 = j end when item > pivot then do j = more.0 + 1 more.j = item more.0 = j end otherwise j = pivotList.0 + 1 pivotList.j = item pivotList.0 = j end end end /* recursive call to sort the less. stem */ do i = 1 to less.0 queue less.i end if queued() > 0 then do call quickSort less.0 = queued() do i = 1 to less.0 parse pull less.i end end /* recursive call to sort the more. stem */ do i = 1 to more.0 queue more.i end if queued() > 0 then do call quickSort more.0 = queued() do i = 1 to more.0 parse pull more.i end end /* put the contents of all 3 stems on the queue in order */ do i = 1 to less.0 queue less.i end do i = 1 to pivotList.0 queue pivotList.i end do i = 1 to more.0 queue more.i end return Ruby class Array def quick_sort return self if length <= 1 pivot = self[0] less, greatereq = self[1..-1].partition { |x| x < pivot } less.quick_sort + [pivot] + greatereq.quick_sort end end or class Array def quick_sort return self if length <= 1 pivot = sample group = group_by{ |x| x <=> pivot } group.default = [] group[-1].quick_sort + group[0] + group[1].quick_sort end end or functionally class Array def quick_sort h, *t = self h ? t.partition { |e| e < h }.inject { |l, r| l.quick_sort + [h] + r.quick_sort } : [] end end Run BASIC ' ------------------------------- ' quick sort ' ------------------------------- size = 50 dim s(size) ' array to sort for i = 1 to size ' fill it with some random numbers s(i) = rnd(0) * 100 next i lft = 1 rht = size [qSort] lftHold = lft rhtHold = rht pivot = s(lft) while lft < rht while (s(rht) >= pivot) and (lft < rht) : rht = rht - 1 :wend if lft <> rht then s(lft) = s(rht) lft = lft + 1 end if while (s(lft) <= pivot) and (lft < rht) : lft = lft + 1 :wend if lft <> rht then s(rht) = s(lft) rht = rht - 1 end if wend s(lft) = pivot pivot = lft lft = lftHold rht = rhtHold if lft < pivot then rht = pivot - 1 goto [qSort] end if if rht > pivot then lft = pivot + 1 goto [qSort] end if for i = 1 to size print i;"-->";s(i) next i Rust fn main() { println!("Sort numbers in descending order"); let mut numbers = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]; println!("Before: {:?}", numbers); quick_sort(&mut numbers, &|x,y| x > y); println!("After: {:?}\n", numbers); println!("Sort strings alphabetically"); let mut strings = ["beach", "hotel", "airplane", "car", "house", "art"]; println!("Before: {:?}", strings); quick_sort(&mut strings, &|x,y| x < y); println!("After: {:?}\n", strings); println!("Sort strings by length"); println!("Before: {:?}", strings); quick_sort(&mut strings, &|x,y| x.len() < y.len()); println!("After: {:?}", strings); } fn quick_sort(v: &mut [T], f: &F) where F: Fn(&T,&T) -> bool { let len = v.len(); if len >= 2 { let pivot_index = partition(v, f); quick_sort(&mut v[0..pivot_index], f); quick_sort(&mut v[pivot_index + 1..len], f); } } fn partition(v: &mut [T], f: &F) -> usize where F: Fn(&T,&T) -> bool { let len = v.len(); let pivot_index = len / 2; v.swap(pivot_index, len - 1); let mut store_index = 0; for i in 0..len - 1 { if f(&v[i], &v[len - 1]) { v.swap(i, store_index); store_index += 1; } } v.swap(store_index, len - 1); store_index } Output: Sort numbers in descending order Before: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1] After: [782, 99, 83, 65, 4, 2, 2, 1, 0, -31] Sort strings alphabetically Before: ["beach", "hotel", "airplane", "car", "house", "art"] After: ["airplane", "art", "beach", "car", "hotel", "house"] Sort strings by length Before: ["airplane", "art", "beach", "car", "hotel", "house"] After: ["car", "art", "house", "hotel", "beach", "airplane"] Sather class SORT{T < $IS_LT{T}} is private afilter(a:ARRAY{T}, cmp:ROUT{T,T}:BOOL, p:T):ARRAY{T} is filtered ::= #ARRAY{T}; loop v ::= a.elt!; if cmp.call(v, p) then filtered := filtered.append(|v|); end; end; return filtered; end; private mlt(a, b:T):BOOL is return a < b; end; private mgt(a, b:T):BOOL is return a > b; end; quick_sort(inout a:ARRAY{T}) is if a.size < 2 then return; end; pivot ::= a.median; left:ARRAY{T} := afilter(a, bind(mlt(_,_)), pivot); right:ARRAY{T} := afilter(a, bind(mgt(_,_)), pivot); quick_sort(inout left); quick_sort(inout right); res ::= #ARRAY{T}; res := res.append(left, |pivot|, right); a := res; end; end; class MAIN is main is a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4, 656, -11|; b ::= a.copy; SORT{INT}::quick_sort(inout a); #OUT + a + "\n" + b.sort + "\n"; end; end; The ARRAY class has a builtin sorting method, which is quicksort (but under certain condition an insertion sort is used instead), exactly quicksort_range; this implementation is original. Scala What follows is a progression on genericity here. First, a quick sort of a list of integers: def sort(xs: List[Int]): List[Int] = { xs match { case Nil => Nil case x :: xx => { // Arbitrarily partition list in two val (lo, hi) = xx.partition(_ < x) // Sort each half sort(lo) ++ (x :: sort(hi)) } } } Next, a quick sort of a list of some type T, given a lessThan function: def sort[T](xs: List[T], lessThan: (T, T) => Boolean): List[T] = { xs match { case Nil => Nil case x :: xx => { val (lo, hi) = xx.partition(lessThan(_, x)) sort(lo, lessThan) ++ (x :: sort(hi, lessThan)) } } } To take advantage of known orderings, a quick sort of a list of some type T, for which exists an implicit (or explicit) Ordering[T]: def sort[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = { xs match { case Nil => Nil case x :: xx => { val (lo, hi) = xx.partition(ord.lt(_, x)) sort[T](lo) ++ (x :: sort[T](hi)) } } } That last one could have worked with Ordering, but Ordering is Java, and doesn't have the less than operator. Ordered is Scala-specific, and provides it. def sort[T <: Ordered[T]](xs: List[T]): List[T] = { xs match { case Nil => Nil case x :: xx => { val (lo, hi) = xx.partition(_ < x) sort(lo) ++ (x :: sort(hi)) } } } What hasn't changed in all these examples is ordering a list. It is possible to write a generic quicksort in Scala, which will order any kind of collection. To do so, however, requires that the type of the collection, itself, be made a parameter to the function. Let's see it below, and then remark upon it: def sort[T, C[T] <: scala.collection.TraversableLike[T, C[T]]] (xs: C[T]) (implicit ord: scala.math.Ordering[T], cbf: scala.collection.generic.CanBuildFrom[C[T], T, C[T]]): C[T] = { // Some collection types can't pattern match if (xs.isEmpty) { xs } else { val (lo, hi) = xs.tail.partition(ord.lt(_, xs.head)) val b = cbf() b.sizeHint(xs.size) b ++= sort(lo) b += xs.head b ++= sort(hi) b.result() } } The type of our collection is "C[T]", and, by providing C[T] as a type parameter to TraversableLike, we ensure C[T] is capable of returning instances of type C[T]. Traversable is the base type of all collections, and TraversableLike is a trait which contains the implementation of most Traversable methods. We need another parameter, though, which is a factory capable of building a C[T] collection. That is being passed implicitly, so callers to this method do not need to provide them, as the collection they are using should already provide one as such implicitly. Because we need that implicitly, then we need to ask for the "T => Ordering[T]" as well, as the "T <: Ordered[T]" which provides it cannot be used in conjunction with implicit parameters. The body of the function is from the list variant, since many of the Traversable collection types don't support pattern matching, "+:" or "::". Scheme (define (split-by l p k) (let loop ((low '()) (high '()) (l l)) (cond ((null? l) (k low high)) ((p (car l)) (loop low (cons (car l) high) (cdr l))) (else (loop (cons (car l) low) high (cdr l)))))) (define (quicksort l gt?) (if (null? l) '() (split-by (cdr l) (lambda (x) (gt? x (car l))) (lambda (low high) (append (quicksort low gt?) (list (car l)) (quicksort high gt?)))))) (quicksort '(1 3 5 7 9 8 6 4 2) >) With srfi-1: (define (quicksort l gt?) (if (null? l) '() (append (quicksort (filter (lambda (x) (gt? (car l) x)) (cdr l)) gt?) (list (car l)) (quicksort (filter (lambda (x) (not (gt? (car l) x))) (cdr l)) gt?)))) (quicksort '(1 3 5 7 9 8 6 4 2) >) Seed7 const proc: quickSort (inout array elemType: arr, in integer: left, in integer: right) is func local var elemType: compare_elem is elemType.value; var integer: less_idx is 0; var integer: greater_idx is 0; var elemType: help is elemType.value; begin if right > left then compare_elem := arr[right]; less_idx := pred(left); greater_idx := right; repeat repeat incr(less_idx); until arr[less_idx] >= compare_elem; repeat decr(greater_idx); until arr[greater_idx] <= compare_elem or greater_idx = left; if less_idx < greater_idx then help := arr[less_idx]; arr[less_idx] := arr[greater_idx]; arr[greater_idx] := help; end if; until less_idx >= greater_idx; arr[right] := arr[less_idx]; arr[less_idx] := compare_elem; quickSort(arr, left, pred(less_idx)); quickSort(arr, succ(less_idx), right); end if; end func; const proc: quickSort (inout array elemType: arr) is func begin quickSort(arr, 1, length(arr)); end func; Original source: [2] SETL In-place sort (looks much the same as the C version) a := [2,5,8,7,0,9,1,3,6,4]; qsort(a); print(a); proc qsort(rw a); if #a > 1 then pivot := a(#a div 2 + 1); l := 1; r := #a; (while l < r) (while a(l) < pivot) l +:= 1; end; (while a(r) > pivot) r -:= 1; end; swap(a(l), a(r)); end; qsort(a(1..l-1)); qsort(a(r+1..#a)); end if; end proc; proc swap(rw x, rw y); [y,x] := [x,y]; end proc; Copying sort using comprehensions: a := [2,5,8,7,0,9,1,3,6,4]; print(qsort(a)); proc qsort(a); if #a > 1 then pivot := a(#a div 2 + 1); a := qsort([x in a | x < pivot]) + [x in a | x = pivot] + qsort([x in a | x > pivot]); end if; return a; end proc; Sidef func quicksort (a) { a.len < 2 && return(a); var p = a.pop_rand; # to avoid the worst cases __FUNC__(a.grep{ .< p}) + [p] + __FUNC__(a.grep{ .>= p}); } Standard ML fun quicksort [] = [] | quicksort (x::xs) = let val (left, right) = List.partition (fn y => y(inout elements: [T], range: Range) { if (range.endIndex - range.startIndex > 1) { let pivotIndex = partition(&elements, range) quicksort(&elements, range.startIndex ..< pivotIndex) quicksort(&elements, pivotIndex+1 ..< range.endIndex) } } func quicksort(inout elements: [T]) { quicksort(&elements, indices(elements)) } Tcl package require Tcl 8.5 proc quicksort {m} { if {[llength $m] <= 1} { return $m } set pivot [lindex $m 0] set less [set equal [set greater [list]]] foreach x $m { lappend [expr {$x < $pivot ? "less" : $x > $pivot ? "greater" : "equal"}] $x } return [concat [quicksort $less] $equal [quicksort $greater]] } puts [quicksort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9 uBasic/4tH PRINT "Quick sort:" n = FUNC (_InitArray) PROC _ShowArray (n) PROC _Quicksort (n) PROC _ShowArray (n) PRINT END _InnerQuick PARAM(2) LOCAL(4) IF b@ < 2 THEN RETURN f@ = a@ + b@ - 1 c@ = a@ e@ = f@ d@ = @((c@ + e@) / 2) DO DO WHILE @(c@) < d@ c@ = c@ + 1 LOOP DO WHILE @(e@) > d@ e@ = e@ - 1 LOOP IF c@ - 1 < e@ THEN PROC _Swap (c@, e@) c@ = c@ + 1 e@ = e@ - 1 ENDIF UNTIL c@ > e@ LOOP IF a@ < e@ THEN PROC _InnerQuick (a@, e@ - a@ + 1) IF c@ < f@ THEN PROC _InnerQuick (c@, f@ - c@ + 1) RETURN _Quicksort PARAM(1) ' Quick sort PROC _InnerQuick (0, a@) RETURN _Swap PARAM(2) ' Swap two array elements PUSH @(a@) @(a@) = @(b@) @(b@) = POP() RETURN _InitArray ' Init example array PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 FOR i = 0 TO 9 @(i) = POP() NEXT RETURN (i) _ShowArray PARAM (1) ' Show array subroutine FOR i = 0 TO a@-1 PRINT @(i), NEXT PRINT RETURN UnixPipes Works with: Zsh split() { (while read n ; do test $1 -gt $n && echo $n > $2 || echo $n > $3 done) } qsort() { (read p; test -n "$p" && ( lc="1.$1" ; gc="2.$1" split $p >(qsort $lc >$lc) >(qsort $gc >$gc); cat $lc <(echo $p) $gc rm -f $lc $gc; )) } cat to.sort | qsort Ursala The distributing bipartition operator, *|, is useful for this algorithm. The pivot is chosen as the greater of the first two items, this being the least sophisticated method sufficient to ensure termination. The quicksort function is a higher order function parameterized by the relational predicate p, which can be chosen appropriately for the type of items in the list being sorted. This example demonstrates sorting a list of natural numbers. #import nat quicksort "p" = ~&itB^?a\~&a ^|WrlT/~& "p"*|^\~& "p"?hthPX/~&th ~&h #cast %nL example = quicksort(nleq) <694,1377,367,506,3712,381,1704,1580,475,1872> Output: <367,381,475,506,694,1377,1580,1704,1872,3712> V [qsort [joinparts [p [*l1] [*l2] : [*l1 p *l2]] view]. [split_on_first uncons [>] split]. [small?] [] [split_on_first [l1 l2 : [l1 qsort l2 qsort joinparts]] view i] ifte]. The way of joy (using binrec) [qsort [small?] [] [uncons [>] split] [[p [*l] [*g] : [*l p *g]] view] binrec]. VBA This is the "simple" quicksort, using temporary arrays. Public Sub Quick(a() As Variant, last As Integer) ' quicksort a Variant array (1-based, numbers or strings) Dim aLess() As Variant Dim aEq() As Variant Dim aGreater() As Variant Dim pivot As Variant Dim naLess As Integer Dim naEq As Integer Dim naGreater As Integer If last > 1 Then 'choose pivot in the middle of the array pivot = a(Int((last + 1) / 2)) 'construct arrays naLess = 0 naEq = 0 naGreater = 0 For Each el In a() If el > pivot Then naGreater = naGreater + 1 ReDim Preserve aGreater(1 To naGreater) aGreater(naGreater) = el ElseIf el < pivot Then naLess = naLess + 1 ReDim Preserve aLess(1 To naLess) aLess(naLess) = el Else naEq = naEq + 1 ReDim Preserve aEq(1 To naEq) aEq(naEq) = el End If Next 'sort arrays "less" and "greater" Quick aLess(), naLess Quick aGreater(), naGreater 'concatenate P = 1 For i = 1 To naLess a(P) = aLess(i): P = P + 1 Next For i = 1 To naEq a(P) = aEq(i): P = P + 1 Next For i = 1 To naGreater a(P) = aGreater(i): P = P + 1 Next End If End Sub Public Sub QuicksortTest() Dim a(1 To 26) As Variant 'populate a with numbers in descending order, then sort For i = 1 To 26: a(i) = 26 - i: Next Quick a(), 26 For i = 1 To 26: Debug.Print a(i);: Next Debug.Print 'now populate a with strings in descending order, then sort For i = 1 To 26: a(i) = Chr$(Asc("z") + 1 - i) & "-stuff": Next Quick a(), 26 For i = 1 To 26: Debug.Print a(i); " ";: Next Debug.Print End Sub Output: quicksorttest 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 a-stuff b-stuff c-stuff d-stuff e-stuff f-stuff g-stuff h-stuff i-stuff j-stuff k-stuff l-stuff m-stuff n-stuff o-stuff p-stuff q-stuff r-stuff s-stuff t-stuff u-stuff v-stuff w-stuff x-stuff y-stuff z-stuff Note: the "quicksort in place" VBScript Translation of: BBC BASIC Function quicksort(arr,s,n) l = s r = s + n - 1 p = arr(Int((l + r)/2)) Do Until l > r Do While arr(l) < p l = l + 1 Loop Do While arr(r) > p r = r -1 Loop If l <= r Then tmp = arr(l) arr(l) = arr(r) arr(r) = tmp l = l + 1 r = r - 1 End If Loop If s < r Then Call quicksort(arr,s,r-s+1) End If If l < t Then Call quicksort(arr,l,t-l+1) End If quicksort = arr End Function myarray=Array(9,8,7,6,5,5,4,3,2,1,0,-1) m = quicksort(myarray,0,12) WScript.Echo Join(m,",") Output: -1,0,1,2,3,4,5,5,6,7,8,9 Wart def (qsort (pivot ... ns)) (+ (qsort+keep (fn(_) (_ < pivot)) ns) list.pivot (qsort+keep (fn(_) (_ > pivot)) ns)) def (qsort x) :case x=nil nil XPL0 include c:\cxpl\codes; \intrinsic 'code' declarations string 0; \use zero-terminated strings proc QSort(Array, Num); \Quicksort Array into ascending order char Array; \address of array to sort int Num; \number of elements in the array int I, J, Mid, Temp; [I:= 0; J:= Num-1; Mid:= Array(J>>1); while I <= J do [while Array(I) < Mid do I:= I+1; while Array(J) > Mid do J:= J-1; if I <= J then [Temp:= Array(I); Array(I):= Array(J); Array(J):= Temp; I:= I+1; J:= J-1; ]; ]; if I < Num-1 then QSort(@Array(I), Num-I); if J > 0 then QSort(Array, J+1); ]; \QSort func StrLen(Str); \Return number of characters in an ASCIIZ string char Str; int I; for I:= 0 to -1>>1-1 do if Str(I) = 0 then return I; char Str; [Str:= "Pack my box with five dozen liquor jugs."; QSort(Str, StrLen(Str), 1); Text(0, Str); CrLf(0); ] Output: .Pabcdeefghiiijklmnoooqrstuuvwxyz zkl These are the Wikipedia algorithms. Quick sort immutable sequence using crappy pivot choice: fcn qtSort(list,cmp=Op("<")){ // sort immutable lists fcn(list,cmp,N){ // spendy to keep recreating cmp reg pivot=list[0], rest=list[1,*]; left,right:=rest.filter22(cmp,pivot); N+=1; T.extend(self.fcn(left,cmp,N),T(pivot),self.fcn(right,cmp,N)); }(list,cmp,0); } In place quick sort: fcn qiSort(list,cmp='<){ // in place quick sort fcn(list,left,right,cmp){ if (left