|
Quicksort implementations
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 also to demonstrate the strengths and weaknesses of each particular language in this particular application.
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);;
fun quicksort lt lst =
let val rec sort =
fn [] => []
| (x::xs) =>
let
val (left,right) = List.partition (fn y => lt (y, x)) xs
in sort left @ x :: sort right
end
in sort lst
end
The following example—though less general than the above snippet 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);
(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 swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }
void sort(int arr[], int beg, int end) {
if (end > beg + 1) {
int piv = arr[beg], l = beg + 1, r = end;
while (l < r) {
if (arr[l] <= piv)
l++;
else
swap(&arr[l], &arr[--r]);
}
swap(&arr[--l], &arr[beg]);
sort(arr, beg, l);
sort(arr, r, end);
}
}
This 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:
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);
}
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);
}
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
#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);
} }
With the advent of Java 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<E extends Comparable<E>> {
public static final Random RND = new Random();
private void swap(E[] array, int i, int j) {
E tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private 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 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 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<Integer> qs = new QuickSort<Integer>();
qs.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<String> qs2 = new QuickSort<String>();
qs2.sort(l2);
System.out.println("l2 sorted:" + Arrays.toString(l2));
}
}
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);
}
}
}
Option Explicit
' a position, wich 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
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.
Let's 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 a 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).
|
|
