1.10 AppleScript

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

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

1.11 AutoIt v3

This is a straightforward implementation based off 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

1.12 C

This implementation is limited to arrays of integers:

void sort(int array[], int begin, int end) { if (end > begin) { int pivot = array[begin]; int l = begin + 1; int r = end; while(l < r) { if (array[l] <= pivot) { l++; } else { r--; swap(array[l], array[r]); } } l--; swap(array[begin], array[l]); sort(array, begin, l); sort(array, r, end); } }

The following implementation uses a 'fat pivot':

void sort(int array[], int begin, int end) { int pivot = array[begin]; int i = begin + 1, j = end, k = end; int t; while (i < j) { if (array[i] < pivot) i++; else if (array[i] > pivot) { j--; k--; t = array[i]; array[i] = array[j]; array[j] = array[k]; array[k] = t; } else { j--; swap(array[i], array[j]); } } i--; swap(array[begin], array[i]); if (i - begin > 1) sort(array, begin, i); if (end - k > 1) sort(array, k, end); }

1.13 JavaJava is an object-oriented programming language developed primarily by James Gosling and colleagues at Sun Microsystems. The language, initially called Oak (named after the oak trees outside Gosling's office), was intended to replace C++, although the fea

The following JavaJava is an object-oriented programming language developed primarily by James Gosling and colleagues at Sun Microsystems. The language, initially called Oak (named after the oak trees outside Gosling's office), was intended to replace C++, although the fea implementation uses a randomly selected pivot. Analogously to the Erlang solution above, a user-supplied Comparator determines the partial ordering of array elements:

import java.util.Comparator; import java.util.Random; public class Quicksort { public static final Random RND = new Random(); private void swap(Object[] array, int i, int j) { Object tmp = array[i]; array[i] = array[j]; array[j] = tmp; } private int partition(Object[] array, int begin, int end, Comparator cmp) { int index = begin + RND.nextInt(end - begin + 1); Object pivot = array[index]; swap(array, index, end); for (int i = index = begin; i < end; ++ i) { if (cmp.compare(array[i], pivot) <= 0) { swap(array, index++, i); } } swap(array, index, end); return (index); } private void qsort(Object[] array, int begin, int end, Comparator cmp) { if (end > begin) { int index = partition(array, begin, end, cmp); qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp); } } public void sort(Object[] array, Comparator cmp) { qsort(array, 0, array.length - 1, cmp); } }

1.14 C#C (pronounced see-sharp is an object-oriented programming language developed by Microsoft as part of their. NET initiative. Microsoft based C# on C++ and the Java programming language. C# was designed to balance power (the C++ influence) with rapid develo

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

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

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

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

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

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

1.15 ARMCambridge The Acorn RISC Machine (or ARM is a RISC processor architecture that is widely used in a number of applications. It is a very "pure" RISC implementation, and is considered one of the most elegant modern processors. History The ARM design was sta assembly languageAssembly language or simply assembly is a human-readable notation for the machine language that a specific computer architecture uses. Machine language, a pattern of bits encoding machine operations, is made readable by replacing the raw values with symbo

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.

1.16 Prolog

Lets first define quicksort predicate without using Tail_recursion

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

And now more elegant version, using Tail_recursion

qsort(List, Sorted) :- qsort(List, [], Sorted). qsort([], Acc, Acc). qsort([H | Tail], Acc, Sorted) :- partition(Tail, H, Left, Right), qsort(Right, Acc, SortedRight), qsort(Left, [H | SortedRight], Sorted).

<Hide>