Algorithm Implementation/Sorting/Quicksort
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;
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))
)This is a basic implementation using C.A.R. Hoare's algorithm with pivot in middle (sometimes referred to as binary or dichotomic sort). The use of a script object to store the list makes this version about 10 times faster than previously proposed one (for a list of a 1000 strings). Also "left" and "right" are keywords, and may not always run as expected. Improvement can also be done depending on data to be sorted by choosing pivot randomly or by increasing their umbers.
on QuickSort(aList, Le, Ri)
--> Sorts list of of simple types such as reals, integers, strings or even booleans
script Sal --> script object aList
property Array : aList
end script
set [i, j] to [Le, Ri]
set v to Sal's Array's item ((Le + Ri) div 2) --> pivot in middle (as C.A.R. Hoare's algorithm)
repeat while j > i
repeat while Sal's Array's item i < v
set i to i + 1
end repeat
repeat while Sal's Array's item j > v
set j to j - 1
end repeat
if not i > j then
tell (a reference to Sal's Array) to set [item i, item j] to [item j, item i] --> let's swap
set [i, j] to [i + 1, j - 1]
end if
end repeat
if Le < j then QuickSort(Sal's Array, Le, j)
if Ri > i then QuickSort(Sal's Array, i, Ri)
end QuickSort
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
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.
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
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 if ( cmp(array+r, pivot) > 0 ) {
r -= size;
} else if ( l < r ) {
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*)) {
if (nitems > 0) {
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={1, 2, 3, 4, 5};
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
editQuicksort 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.
This is a generic, STL-based version of quicksort.
Note that this implementation uses last iterator content, and is not suitable for a std::[whatever]sort replacement as is.
#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);
}
}
The followings C# implementations uses the functional aspect of c#
public IEnumerable<T> Quicksort<T>(List<T> v, IComparer<T> comparer)
{
if (v.Count < 2)
return v;
T pivot = v[v.Count / 2];
return Quicksort(v.Where(x => comparer.Compare(x, pivot) < 0), comparer)
.Concat(new T[] { pivot })
.Concat(Quicksort(v.Where(x => comparer.Compare(x, pivot) > 0), comparer));
}
Faster cause uses partition
public IEnumerable<T> Quicksort(IEnumerable<T> v, Comparer<T> compare)
{
if (!v.Any())
return Enumerable.Empty<T>();
T pivot = v.First();
// partition
Stack<T> lowers = new Stack<T>(), greaters = new Stack<T>();
foreach (T item in v.Skip(1)) // skip the pivot
(compare(item, pivot) < 0 ? lowers : greaters).Push(item);
return Quicksort(lowers, compare)
.Concat(new T[] { pivot })
.Concat(Quicksort(greaters, compare));
}
The following example uses linq to filter the list
private void Quicksort<T>(T[] v, int left, int right, IComparer<T> comparer)
{
if (right - left > 1)
{
var mid = (left + right) / 2;
T pivot = v[mid];
T[] aux = new T[right - left + 1];
Array.Copy(v, left, aux, 0, aux.Length);
var vv = aux.Where(x => comparer.Compare(x, pivot) < 0)
.Concat( new T[] {pivot} )
.Concat(aux.Where(x => comparer.Compare(x, pivot) > 0)).ToArray();
Array.Copy(vv, 0, v, left, vv.Length);
Quicksort(v, left, mid, comparer);
Quicksort(v, mid + 1, right, comparer);
}
}
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);
}
}
(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)))))))
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);
}
}
//D2 version,working with almost any kind of iterator(called range in the D community)not only array
void quickSort(T)(T iter)
if(hasLength!T && isRandomAccessRange!T && hasSlicing!T){
if(iter.length<=1)return;//there is nothing to sort
auto pivot = iter[iter.length/2];
size_t r = iter.length, l = 0;
do {
while (iter[l] < pivot) l++;
while (iter[r] > pivot) r--;
if (l <= r) swap(iter[l++], iter[r--]);
} while (l <= r);
quickSort(iter[0 .. r]);
quickSort(iter[l .. $]);
}
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;
The following Elixir code sorts collections that implement the Enumerbale protocol of items of any type that can be compared using the < operator.
defmodule QSort do
def sort([]), do: []
def sort([pivot | rest]) do
{smaller, bigger} = Enum.partition(rest, &(&1 < pivot))
sort(smaller) ++ [pivot] ++ sort(bigger)
end
end
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]).
let rec qsort = function
hd :: tl ->
let less, greater = List.partition ((>=) hd) tl
List.concat [qsort less; [hd]; qsort greater]
| _ -> []
func QSort(data []int) {
if len(data) < 2 {
return
}
pivot := data[0]
l, r := 1, len(data) - 1
for l <= r {
for l <= r && data[l] <= pivot {
l ++
}
for r >= l && data[r] >= pivot {
r --
}
if l < r {
data[l], data[r] = data[r], data[l]
}
}
if r > 0 {
data[0], data[r] = data[r], data[0]
qsort(data[0:r])
}
qsort(data[l:])
}
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)
}
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)
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.
)
The following example uses the functional characteristics of Java 8
import java.util.*;
import java.util.function.*;
import java.util.stream.Stream;
import static com.google.common.collect.Iterables.concat;
import static java.lang.System.out;
import static java.util.Arrays.asList;
import static java.util.stream.Collectors.partitioningBy;
import static org.assertj.core.util.Lists.newArrayList;
public <T> List<T> qs(List<T> l, BiPredicate<T, T> isLower) {
if (l.size() < 2) {
return l;
} else {
T x = l.get(0);
Stream<T> xs = l.stream().skip(1);
Map<Boolean, List<T>> part = xs.collect(partitioningBy(item -> isLower.test(item, x)));
List<T> lowers = part.get(true);
List<T> highers = part.get(false);
return newArrayList(concat(qs(lowers, isLower), asList(x), qs(highers, isLower)));
}
}
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;
}
}
function qsort(a) {
if (a.length <= 1) return a; //< the array is already sorted at this point (e.g. [1] or [])
var left = []
var right = []
var pivot = a.shift(); //a separate `var` declaration must be used for each variable to avoid polluting global scope
while (a.length) a[0] < pivot ? left.push(a.shift()) : right.push(a.shift());
return qsort(left).concat(pivot).concat(qsort(right));
}
Here is another JavaScript implementation using declarative programming that does not mutate the input.
let quicksort=xs=>{
if (xs.length <= 1) return xs
var l = []
var r = []
var pivot = xs[xs.length-1] //< note that quicksort can commonly be made more performant by choosing a better pivot
xs.slice(0,-1).forEach(x => x < pivot ? l.push(x) : r.push(x)) //iterates over all the elements except the pivot, then pushes onto the appropriate list
return quicksort(l).concat([pivot], quicksort(r))
}
'''DEFINE''' sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .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}]]]
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))];
sort [] = []
sort (pivot:rest) = sort [ y | y <- rest; y <= pivot ]
++ [pivot] ++
sort [ y | y <- rest; y > pivot ]
(* 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 *)
let rec sort = function
[] -> []
| pivot :: rest ->
let left, right = List.partition (( > ) pivot) rest in
sort left @ pivot :: sort right
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, @_))
}
Or:
sub qsort {
return if not @_;
my ($head, @tail) = @_;
return (qsort(grep { $_ < $head } @tail), $head,
qsort(grep { $_ >= $head} @tail))
}
multi quicksort () { () }
multi quicksort (*$x, *@xs) {
my @pre = @xs.grep:{ $_ < $x };
my @post = @xs.grep:{ $_ >= $x };
(@pre.quicksort, $x, @post.quicksort);
}
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<midval then
last += 1
x[i] = x[last]
x[last] = xi
end if
end for
return quick_sort(x[2..last]) & {midval} & quick_sort(x[last+1..n])
end function
?quick_sort({5,"oranges","and",3,"apples"})
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;}))
);
}
Here is an in-place algorythm that performs better than the implementations above. Of course in real life use sort PHP native function.
// Quick sort between $start and $last indexes of array $a (inplace implementation)
function quickSort(&$a, $start = 0, $last = null) {
// Init
$wall = $start;
$last = is_null($last) ? count($a) - 1 : $last;
// Nothing to sort
if($last - $start < 1) {
return;
}
// Moving median value to the back to avoid bad performance when sorting an already sorted array
switchValues($a, (int) (($start + $last) / 2), $last);
// Splitting the array according to comparisons with the last value
for ($i = $start; $i < $last; $i++) {
if ($a[$i] < $a[$last]) {
switchValues($a, $i, $wall);
$wall++;
}
}
// Placing last value between the two split arrays
switchValues($a, $wall, $last);
// Sorting left of the wall
quickSort($a, $start, $wall - 1);
// Sorting right of the wall
quickSort($a, $wall + 1, $last);
}
// Switch two values identified by keys $i1 and $i2 of $a
function switchValues(&$a, $i1, $i2) {
if ($i1 !== $i2) {
$temp = $a[$i1];
$a[$i1] = $a[$i2];
$a[$i2] = $temp;
}
}
function printArray($a) {
echo '[' . implode(', ', $a). ']' . PHP_EOL;
}
// Generate array with random values
$arr = [];
$size = 1000000;
for ($i = 0; $i < $size; $i++) {
$arr[] = (int) (rand() / (1000000000 / $size));
}
// Measuring function's performance
$t1 = microtime(true);
quickSort($arr);
$t2 = microtime(true);
// Printing stats
// printArray($arr);
$t = round(($t2 - $t1) * 1000 * 1000) / 1000;
echo PHP_EOL . "Sorted $size elements in {$t}ms" . PHP_EOL;
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).
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 partitioning 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)
The above takes longer than the in place sort below, which only swaps values above the pivot value to the left, with values below the pivot to the right, instead of the previous , which re-swaps already swapped under pivot values, which doubles the number of swaps.
However , both in-place sorts are slower than the memory consuming list comprehension version, which itself is 10 times slower than the in-built sorted() function.
The version below doesn't avoid the bad sorted input problem, by choosing a random pivot element or median-of-three pivot element.
def qsinplace(a, l, r):
if l >= r:
return
pivot_idx = l
old_r = r
pivot = a[l]
l += 1
while True:
# manual check, does it work when l=pivot_idx, r=l+1 for a[l] <= a[r], and for a[l] > a[r] ?
while a[r] > pivot:
r -= 1
if l >= r:
break
while l < r and a[l] <= pivot:
l += 1
#pre-conditions to swap: l == r, or a[l] > pivot from 2nd loop, and a[r] <= pivot from 1st loop
a[l], a[r] = a[r], a[l]
a[pivot_idx], a[r] = a[r], a[pivot_idx]
qsinplace(a, pivot_idx, r)
qsinplace(a, r + 1, old_r)
#driver test
l=[i for i in xrange(0,100000) ]
import random
import time
t1 = time.time()
random.shuffle(l)
t2 = time.time()
print "took ", t2 - t1, " time to shuffle ", len(l)
print l
ll = len(l)
t1 = time.time()
# quick sort
qsinplace(l,0, ll-1)
t2 = time.time()
print "took ", t2 - t1, " time to qsinplace", len(l)
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
Using Closures but with a random pivot:
def quicksort(list)
return list if list.length <= 1
pivot = list.shuffle.shift
left, right = list.partition { |el| el < pivot }
quicksort(left).concat(quicksort(right))
end
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)
}
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))))))))
(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]))))
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
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);
func qsort(var array: [Int]) -> [Int] {
if array.isEmpty { return [] }
let pivot = array.removeAtIndex(0)
var left = array.filter { $0 < pivot }
var right = array.filter { $0 >= pivot }
return qsort(left) + [pivot] + qsort(right)
}
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>
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
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;
}
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
Pascal
editconst maxA = 1000;
type TElem = integer;
TArray = array[1..maxA]of TElem;
(* This version of quick sort can be found in Turbo Pascal examples *)
procedure quicksort(var A:TArray;l,r:integer);
var i,j:integer;
x,w:TElem;
begin
i := l;
j := r;
x := A[(l + r) div 2];
repeat
while A[i] < x do i := i + 1;
while x < A[j] do j := j - 1;
if i <= j then
begin
w := A[i];
A[i] := A[j];
A[j] := w;
i := i + 1;
j := j - 1;
end;
until i > j;
if l < j then quicksort(A,l,j);
if i < r then quicksort(A,i,r);
end;
Another procedure with extracted partition function
const maxA = 1000;
maxS = 2000;
type TElem = integer;
TArray = array[1..maxA]of TElem;
TStackArray = array[1..maxS]of integer;
function HoarePartition(var A:TArray;p,r:integer):integer;
var i,j:integer;
x,t:TElem;
begin
x := A[p];
i := p - 1;
j := r + 1;
repeat
repeat
j := j - 1;
until A[j] <= x;
repeat
i := i + 1;
until A[i] >= x;
if i < j then
begin
t := A[i];
A[i] := A[j];
A[j] := t;
end;
until i >= j;
HoarePartition := j;
end;
function LomutoPartition(var A:TArray;p,r:integer):integer;
var i,j:integer;
x,t:TElem;
begin
x := A[r];
i := p - 1;
for j := p to r do
if A[j] <= x then
begin
i := i + 1;
t := A[i];
A[i] := A[j];
A[j] := t;
end;
if i < r then
LomutoPartition := i
else
LomutoPartition := i - 1;
end;
(*Recursive version of quick sort*)
procedure quickSort(var A:TArray;p,r:integer);
var q:integer;
begin
if p < r then
begin
q := HoarePartition(A,p,r);
quickSort(A,p,q);
quickSort(A,q + 1,r);
end;
end;
(*Iterative version of quick sort*)
procedure quickSort(var A:TArray;n:integer);
var p,q,r:integer;
s:TStackArray;
top:integer;
begin
top := 0;
if n > 1 then
begin
top := top + 2;
s[top] := n;
s[top - 1] := 1;
while top <> 0 do
begin
r := s[top];
p := s[top - 1];
top := top - 2;
while(p < r)do
begin
q := HoarePartition(A,p,r);
if q - p + 1 < r - q then
begin
top := top + 2;
s[top] := r;
s[top - 1] := q + 1;
r := q;
end
else
begin
top := top + 2;
s[top] := q;
s[top - 1] := p;
p = q + 1;
end;
end;
end;
end;
end;