|
This is a list of sample implementations of the quicksort sorting algorithm in various programming languages, sorted by number of non-comment lines of code. Samples are written in a non-contrived style, characteristic of the respective languages. These serve to demonstrate the algorithm, but even more to demonstrate the strengths and weaknesses of each particular language.
sort =: ]`(($:@: ((}.<:{.)#}.))
,{.,
($:@: ((}.> {.)#}.))) @. (*@#)
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
sort [] = []
sort (pivot:rest) = sort [ y | y <- rest; y <= pivot ]
++ [pivot] ++
sort [ y | y <- rest; y > pivot ]
sort () == id
sort pivot,,rest == ( self : rest[rest <= pivot] )
, pivot ,
( self : rest[rest > pivot] )
The following Haskell code 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.
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (pivot:rest) = sort [y | y <- rest, y < pivot]
++ [pivot] ++
sort [y | y <- rest, y >=pivot]
The following implementation does not have the aforementioned inefficiency, as it uses a partition function that ensures that we only traverse `xs' once:
partition:: (Ord a) => [a] -> a -> ([a],[a]) -> ([a],[a])
partition [] _ part = part -- base case
partition (x:xs) pivot (lesseq,greater) =
if x<= pivot then partition xs pivot (x:lesseq,greater)
else partition xs pivot (lesseq,x:greater)
sort:: (Ord a) => [a] -> [a]
sort [] = []
sort (x:xs) = sort lesseq ++ [x] ++ greater where
(lesseq,greater) = partition xs x ([],[])
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]).
''val sort : 'a list -> 'a list = <fun>''
# let rec sort array = match array with
[] -> []
| pivot::rest -> let left,right = List.partition (function x -> x < pivot) rest
in (sort left) @ pivot::(sort right);;
(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)))))))
Uses srfi-1, srfi-8 and srfi-26. Traverses the list half as many times as the CL version above.
(define (qsort list)
(if (pair? list)
(let ((p (car list)))
(receive (smaller larger)
(partition (cut < <> p) (cdr list))
(append (qsort smaller) (cons p (qsort larger)))))
'()))
def sort(array)
return [] if array.empty?
pivot = array[0]
left, right = array[1..-1].partition { |y| y <= pivot }.map { |a| sort(a) }
left + [ pivot ] + right
end
The following Python implementation uses a more efficient partitioning strategy:
def partition(array, begin, end, cmp):
while begin < end:
while begin < end:
if cmp(array[begin], array[end]):
(array[begin], array[end]) = (array[end], array[begin])
break
end -= 1
while begin < end:
if cmp(array[begin], array[end]):
(array[begin], array[end]) = (array[end], array[begin])
break
begin += 1
return begin
def sort(array, cmp=lambda x, y: x > y, begin=None, end=None):
if begin is None: begin = 0
if end is None: end = len(array)
if begin < end:
i = partition(array, begin, end-1, cmp)
sort(array, cmp, begin, i)
sort(array, cmp, i+1, end)
A more elegant implementation:
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]])
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
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
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);
}
#include <algorithm>
#include <iterator>
#include <functional>
template <typename T>
void sort(T begin, T end) {
if (begin != end) {
T middle = partition (begin, end, bind2nd(
less<iterator_traits<T>::value_type>(), *begin));
sort (begin, middle);
sort (max(begin + 1, middle), end);
}
}
The following Java 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);
} }
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);
}
}
}
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.
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).
|
