Sorting algorithms/Quicksort
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
Heapsort | Mergesort | Quicksort
O(n log2n) Sorts
Shell Sort
O(n2) Sorts
Bubble sort | Cocktail sort | Comb sort | Gnome sort | Insertion sort | Selection sort | Strand sort
Other Sorts
Bead sort | Bogosort | Counting sort | Pancake sort | Permutation sort | Radix sort | Sleep sort | Stooge sort
| This page uses content from Wikipedia. The original article was at Quicksort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
The task is to sort an array (or list) elements using the quicksort algorithm. The elements must have a strict weak order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers.
Quicksort, also known as partition-exchange sort, uses these steps.
- Choose any element of the array to be the pivot.
- Divide all other elements (except the pivot) into two partitions.
- All elements less than the pivot must be in the first partition.
- All elements greater than the pivot must be in the second partition.
- Use recursion to sort both partitions.
- Join the first sorted partition, the pivot, and the second sorted partition.
The best pivot creates partitions of equal length (or lengths differing by 1). The worst pivot creates an empty partition (for example, if the pivot is the first or last element of a sorted array). The runtime of Quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the array.
This is a simple quicksort algorithm, adapted from Wikipedia.
function quicksort(array)
less, equal, greater := three empty arrays
if length(array) > 1
pivot := select any element of array
for each x in array
if x < pivot then add x to less
if x = pivot then add x to equal
if x > pivot then add x to greater
quicksort(less)
quicksort(greater)
array := concatenate(less, equal, greater)
A better quicksort algorithm works in place, by swapping elements within the array, to avoid the memory allocation of more arrays.
function quicksort(array)
if length(array) > 1
pivot := select any element of array
left := first index of array
right := last index of array
while left ≤ right
while array[left] < pivot
left := left + 1
while array[right] > pivot
right := right - 1
if left ≤ right
swap array[left] with array[right]
left := left + 1
right := right - 1
quicksort(array from first index to right)
quicksort(array from left to last index)
Quicksort has a reputation as the fastest sort. Optimized variants of quicksort are common features of many languages and libraries. One often contrasts quicksort with merge sort, because both sorts have an average time of O(n log n).
- "On average, mergesort does fewer comparisons than quicksort, so it may be better when complicated comparison routines are used. Mergesort also takes advantage of pre-existing order, so it would be favored for using sort() to merge several sorted arrays. On the other hand, quicksort is often faster for small arrays, and on arrays of a few distinct values, repeated many times." — http://perldoc.perl.org/sort.html
Quicksort is at one end of the spectrum of divide-and-conquer algorithms, with merge sort at the opposite end.
- Quicksort is a conquer-then-divide algorithm, which does most of the work during the partitioning and the recursive calls. The subsequent reassembly of the sorted partitions involves trivial effort.
- Merge sort is a divide-then-conquer algorithm. The partioning happens in a trivial way, by splitting the input array in half. Most of the work happens during the recursive calls and the merge phase.
With quicksort, every element in the first partition is less than or equal to every element in the second partition. Therefore, the merge phase of quicksort is so trivial that it needs no mention!
This task has not specified whether to allocate new arrays, or sort in place. This task also has not specified how to choose the pivot element. (Common ways to are to choose the first element, the middle element, or the median of three elements.) Thus there is a variety among the following implementations.
[edit] ACL2
(defun partition (p xs)
(if (endp xs)
(mv nil nil)
(mv-let (less more)
(partition p (rest xs))
(if (< (first xs) p)
(mv (cons (first xs) less) more)
(mv less (cons (first xs) more))))))
(defun qsort (xs)
(if (endp xs)
nil
(mv-let (less more)
(partition (first xs) (rest xs))
(append (qsort less)
(list (first xs))
(qsort more)))))
Usage:
> (qsort '(8 6 7 5 3 0 9))
(0 3 5 6 7 8 9)
[edit] ActionScript
The functional programming way
function quickSort (array:Array):Array
{
if (array.length <= 1)
return array;
var pivot:Number = array[Math.round(array.length / 2)];
return quickSort(array.filter(function (x:Number, index:int, array:Array):Boolean { return x < pivot; })).concat(
array.filter(function (x:Number, index:int, array:Array):Boolean { return x == pivot; })).concat(
quickSort(array.filter(function (x:Number, index:int, array:Array):Boolean { return x > pivot; })));
}
The faster way
function quickSort (array:Array):Array
{
if (array.length <= 1)
return array;
var pivot:Number = array[Math.round(array.length / 2)];
var less:Array = [];
var equal:Array = [];
var greater:Array = [];
for each (var x:Number in array) {
if (x < pivot)
less.push(x);
if (x == pivot)
equal.push(x);
if (x > pivot)
greater.push(x);
}
return quickSort(less).concat(
equal).concat(
quickSort(greater));
}
[edit] Ada
This example is implemented as a generic procedure. The procedure specification is:
-----------------------------------------------------------------------
-- Generic Quicksort procedure
-----------------------------------------------------------------------
generic
type Element_Type is private;
type Index_Type is (<>);
type Element_Array is array(Index_Type range <>) of Element_Type;
with function "<" (Left, Right : Element_Type) return Boolean is <>;
with function ">" (Left, Right : Element_Type) return Boolean is <>;
procedure Sort(Item : in out Element_Array);
The procedure body deals with any discrete index type, either an integer type or an enumerated type.
-----------------------------------------------------------------------
-- Generic Quicksort procedure
-----------------------------------------------------------------------
procedure Sort (Item : in out Element_Array) is
procedure Swap(Left, Right : in out Element_Type) is
Temp : Element_Type := Left;
begin
Left := Right;
Right := Temp;
end Swap;
Pivot_Index : Index_Type;
Pivot_Value : Element_Type;
Right : Index_Type := Item'Last;
Left : Index_Type := Item'First;
begin
if Item'Length > 1 then
Pivot_Index := Index_Type'Val((Index_Type'Pos(Item'Last) + 1 +
Index_Type'Pos(Item'First)) / 2);
Pivot_Value := Item(Pivot_Index);
Left := Item'First;
Right := Item'Last;
loop
while Left < Item'Last and then Item(Left) < Pivot_Value loop
Left := Index_Type'Succ(Left);
end loop;
while Right > Item'First and then Item(Right) > Pivot_Value loop
Right := Index_Type'Pred(Right);
end loop;
exit when Left >= Right;
Swap(Item(Left), Item(Right));
if Left < Item'Last and Right > Item'First then
Left := Index_Type'Succ(Left);
Right := Index_Type'Pred(Right);
end if;
end loop;
if Right > Item'First then
Sort(Item(Item'First..Index_Type'Pred(Right)));
end if;
if Left < Item'Last then
Sort(Item(Left..Item'Last));
end if;
end if;
end Sort;
An example of how this procedure may be used is:
with Sort;
with Ada.Text_Io;
with Ada.Float_Text_IO; use Ada.Float_Text_IO;
procedure Sort_Test is
type Days is (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
type Sales is array(Days range <>) of Float;
procedure Sort_Days is new Sort(Float, Days, Sales);
procedure Print(Item : Sales) is
begin
for I in Item'range loop
Put(Item => Item(I), Fore => 5, Aft => 2, Exp => 0);
end loop;
end Print;
Weekly_Sales : Sales := (Mon => 300.0,
Tue => 700.0,
Wed => 800.0,
Thu => 500.0,
Fri => 200.0,
Sat => 100.0,
Sun => 900.0);
begin
Print(Weekly_Sales);
Ada.Text_Io.New_Line(2);
Sort_Days(Weekly_Sales);
Print(Weekly_Sales);
end Sort_Test;
[edit] ALGOL 68
From: http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Quicksort#ALGOL_68
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
);
MODE DATA = INT;
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))
)
[edit] APL
qsort ← {1≥⍴⍵:⍵⋄e←⍵[?⍴⍵]⋄ (∇(⍵<e)/⍵) , ((⍵=e)/⍵) , ∇(⍵>e)/⍵}
qsort 1 3 5 7 9 8 6 4 2
1 2 3 4 5 6 7 8 9
Of course, in real APL applications, one would use ⍋ to sort (which will pick a sorting algorithm suited to the argument).
[edit] AWK
# the following qsort implementation extracted from:
#
# ftp://ftp.armory.com/pub/lib/awk/qsort
#
# Copyleft GPLv2 John DuBois
#
# @(#) qsort 1.2.1 2005-10-21
# 1990 john h. dubois iii (john@armory.com)
#
# qsortArbIndByValue(): Sort an array according to the values of its elements.
#
# Input variables:
#
# Arr[] is an array of values with arbitrary (associative) indices.
#
# Output variables:
#
# k[] is returned with numeric indices 1..n. The values assigned to these
# indices are the indices of Arr[], ordered so that if Arr[] is stepped
# through in the order Arr[k[1]] .. Arr[k[n]], it will be stepped through in
# order of the values of its elements.
#
# Return value: The number of elements in the arrays (n).
#
# NOTES:
#
# Full example for accessing results:
#
# foolist["second"] = 2;
# foolist["zero"] = 0;
# foolist["third"] = 3;
# foolist["first"] = 1;
#
# outlist[1] = 0;
# n = qsortArbIndByValue(foolist, outlist)
#
# for (i = 1; i <= n; i++) {
# printf("item at %s has value %d\n", outlist[i], foolist[outlist[i]]);
# }
# delete outlist;
#
function qsortArbIndByValue(Arr, k,
ArrInd, ElNum)
{
ElNum = 0;
for (ArrInd in Arr) {
k[++ElNum] = ArrInd;
}
qsortSegment(Arr, k, 1, ElNum);
return ElNum;
}
#
# qsortSegment(): Sort a segment of an array.
#
# Input variables:
#
# Arr[] contains data with arbitrary indices.
#
# k[] has indices 1..nelem, with the indices of Arr[] as values.
#
# Output variables:
#
# k[] is modified by this function. The elements of Arr[] that are pointed to
# by k[start..end] are sorted, with the values of elements of k[] swapped
# so that when this function returns, Arr[k[start..end]] will be in order.
#
# Return value: None.
#
function qsortSegment(Arr, k, start, end,
left, right, sepval, tmp, tmpe, tmps)
{
if ((end - start) < 1) { # 0 or 1 elements
return;
}
# handle two-element case explicitly for a tiny speedup
if ((end - start) == 1) {
if (Arr[tmps = k[start]] > Arr[tmpe = k[end]]) {
k[start] = tmpe;
k[end] = tmps;
}
return;
}
# Make sure comparisons act on these as numbers
left = start + 0;
right = end + 0;
sepval = Arr[k[int((left + right) / 2)]];
# Make every element <= sepval be to the left of every element > sepval
while (left < right) {
while (Arr[k[left]] < sepval) {
left++;
}
while (Arr[k[right]] > sepval) {
right--;
}
if (left < right) {
tmp = k[left];
k[left++] = k[right];
k[right--] = tmp;
}
}
if (left == right)
if (Arr[k[left]] < sepval) {
left++;
} else {
right--;
}
if (start < right) {
qsortSegment(Arr, k, start, right);
}
if (left < end) {
qsortSegment(Arr, k, left, end);
}
}
[edit] AutoHotkey
translated from python example
MsgBox % quicksort("8,4,9,2,1")
quicksort(list)
{
StringSplit, list, list, `,
If (list0 <= 1)
Return list
pivot := list1
Loop, Parse, list, `,
{
If (A_LoopField < pivot)
less = %less%,%A_LoopField%
Else If (A_LoopField > pivot)
more = %more%,%A_LoopField%
Else
pivotlist = %pivotlist%,%A_LoopField%
}
StringTrimLeft, less, less, 1
StringTrimLeft, more, more, 1
StringTrimLeft, pivotList, pivotList, 1
less := quicksort(less)
more := quicksort(more)
Return less . pivotList . more
}
[edit] BASIC
This is specifically for INTEGERs, but can be modified for any data type by changing arr()'s type.
DECLARE SUB quicksort (arr() AS INTEGER, leftN AS INTEGER, rightN AS INTEGER)
DIM q(99) AS INTEGER
DIM n AS INTEGER
RANDOMIZE TIMER
FOR n = 0 TO 99
q(n) = INT(RND * 9999)
NEXT
OPEN "output.txt" FOR OUTPUT AS 1
FOR n = 0 TO 99
PRINT #1, q(n),
NEXT
PRINT #1,
quicksort q(), 0, 99
FOR n = 0 TO 99
PRINT #1, q(n),
NEXT
CLOSE
SUB quicksort (arr() AS INTEGER, leftN AS INTEGER, rightN AS INTEGER)
DIM pivot AS INTEGER, leftNIdx AS INTEGER, rightNIdx AS INTEGER
leftNIdx = leftN
rightNIdx = rightN
IF (rightN - leftN) > 0 THEN
pivot = (leftN + rightN) / 2
WHILE (leftNIdx <= pivot) AND (rightNIdx >= pivot)
WHILE (arr(leftNIdx) < arr(pivot)) AND (leftNIdx <= pivot)
leftNIdx = leftNIdx + 1
WEND
WHILE (arr(rightNIdx) > arr(pivot)) AND (rightNIdx >= pivot)
rightNIdx = rightNIdx - 1
WEND
SWAP arr(leftNIdx), arr(rightNIdx)
leftNIdx = leftNIdx + 1
rightNIdx = rightNIdx - 1
IF (leftNIdx - 1) = pivot THEN
rightNIdx = rightNIdx + 1
pivot = rightNIdx
ELSEIF (rightNIdx + 1) = pivot THEN
leftNIdx = leftNIdx - 1
pivot = leftNIdx
END IF
WEND
quicksort arr(), leftN, pivot - 1
quicksort arr(), pivot + 1, rightN
END IF
END SUB
[edit] BCPL
// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.
GET "libhdr.h"
LET quicksort(v, n) BE qsort(v+1, v+n)
AND qsort(l, r) BE
{ WHILE l+8<r DO
{ LET midpt = (l+r)/2
// Select a good(ish) median value.
LET val = middle(!l, !midpt, !r)
LET i = partition(val, l, r)
// Only use recursion on the smaller partition.
TEST i>midpt THEN { qsort(i, r); r := i-1 }
ELSE { qsort(l, i-1); l := i }
}
FOR p = l+1 TO r DO // Now perform insertion sort.
FOR q = p-1 TO l BY -1 TEST q!0<=q!1 THEN BREAK
ELSE { LET t = q!0
q!0 := q!1
q!1 := t
}
}
AND middle(a, b, c) = a<b -> b<c -> b,
a<c -> c,
a,
b<c -> a<c -> a,
c,
b
AND partition(median, p, q) = VALOF
{ LET t = ?
WHILE !p < median DO p := p+1
WHILE !q > median DO q := q-1
IF p>=q RESULTIS p
t := !p
!p := !q
!q := t
p, q := p+1, q-1
} REPEAT
LET start() = VALOF {
LET v = VEC 1000
FOR i = 1 TO 1000 DO v!i := randno(1_000_000)
quicksort(v, 1000)
FOR i = 1 TO 1000 DO
{ IF i MOD 10 = 0 DO newline()
writef(" %i6", v!i)
}
newline()
}
[edit] C
void quick_sort (int *a, int n) {
if (n < 2)
return;
int p = a[n / 2];
int *l = a;
int *r = a + n - 1;
while (l <= r) {
while (*l < p)
l++;
while (*r > p)
r--;
if (l <= r) {
int t = *l;
*l++ = *r;
*r-- = t;
}
}
quick_sort(a, r - a + 1);
quick_sort(l, a + n - l);
}
int main () {
int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
int n = sizeof a / sizeof a[0];
quick_sort(a, n);
return 0;
}
[edit] C++
The following implements quicksort with a median-of-three pivot. As idiomatic in C++, the argument last is a one-past-end iterator. Note that this code takes advantage of std::partition, which is O(n). Also note that it needs a random-access iterator for efficient calculation of the median-of-three pivot (more exactly, for O(1) calculation of the iterator mid).
#include <iterator>
#include <algorithm> // for std::partition
#include <functional> // for std::less
// helper function for median of three
template<typename T>
T median(T t1, T t2, T t3)
{
if (t1 < t2)
{
if (t2 < t3)
return t2;
else if (t1 < t3)
return t3;
else
return t1;
}
else
{
if (t1 < t3)
return t1;
else if (t2 < t3)
return t3;
else
return t2;
}
}
// helper object to get <= from <
template<typename Order> struct non_strict_op:
public std::binary_function<typename Order::second_argument_type,
typename Order::first_argument_type,
bool>
{
non_strict_op(Order o): order(o) {}
bool operator()(typename Order::second_argument_type arg1,
typename Order::first_argument_type arg2) const
{
return !order(arg2, arg1);
}
private:
Order order;
};
template<typename Order> non_strict_op<Order> non_strict(Order o)
{
return non_strict_op<Order>(o);
}
template<typename RandomAccessIterator,
typename Order>
void quicksort(RandomAccessIterator first, RandomAccessIterator last, Order order)
{
if (first != last && first+1 != last)
{
typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
RandomAccessIterator mid = first + (last - first)/2;
value_type pivot = median(*first, *mid, *(last-1));
RandomAccessIterator split1 = std::partition(first, last, std::bind2nd(order, pivot));
RandomAccessIterator split2 = std::partition(split1, last, std::bind2nd(non_strict(order), pivot));
quicksort(first, split1, order);
quicksort(split2, last, order);
}
}
template<typename RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last)
{
quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}
A simpler version of the above that just uses the first element as the pivot and only does one "partition".
#include <iterator>
#include <algorithm> // for std::partition
#include <functional> // for std::less
template<typename RandomAccessIterator,
typename Order>
void quicksort(RandomAccessIterator first, RandomAccessIterator last, Order order)
{
if (last - first > 1)
{
RandomAccessIterator split = std::partition(first+1, last, std::bind2nd(order, *first));
std::iter_swap(first, split-1);
quicksort(first, split-1, order);
quicksort(split, last, order);
}
}
template<typename RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last)
{
quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}
[edit] C#
Note that actually Array.Sort and ArrayList.Sort both use an unstable implementation of the quicksort algorithm.
using System;
using System.Collections.Generic;
namespace QuickSort
{
class Program
{
static void Main(string[] args)
{
List<int> unsorted = new List<int> { 1, 3, 5, 7, 9, 8, 6, 4, 2 };
List<int> sorted = quicksort(unsorted);
Console.WriteLine(string.Join(",", sorted));
Console.ReadKey();
}
private static List<int> quicksort(List<int> arr)
{
List<int> loe = new List<int>(), gt = new List<int>();
if (arr.Count < 2)
return arr;
int pivot = arr.Count / 2;
int pivot_val = arr[pivot];
arr.RemoveAt(pivot);
foreach (int i in arr)
{
if (i <= pivot_val)
loe.Add(i);
else if (i > pivot_val)
gt.Add(i);
}
List<int> resultSet = new List<int>();
resultSet.AddRange(quicksort(loe));
gt.Add(pivot_val);
resultSet.AddRange(quicksort(gt));
return resultSet;
}
}
}
[edit] Clojure
A very Haskell-like solution using list comprehensions and lazy evaluation.
(defn qsort [L]
(if (empty? L)
'()
(let [[pivot & L2] L]
(lazy-cat (qsort (for [y L2 :when (< y pivot)] y))
(list pivot)
(qsort (for [y L2 :when (>= y pivot)] y))))))
Another short version (using quasiquote):
(defn qsort [[pvt & rs]]
(if pvt
`(~@(qsort (filter #(< % pvt) rs))
~pvt
~@(qsort (filter #(>= % pvt) rs)))))
Another, more readable version (no macros):
(defn qsort [[pivot & xs]]
(when pivot
(let [smaller #(< % pivot)]
(lazy-cat (qsort (filter smaller xs))
[pivot]
(qsort (remove smaller xs))))))
A 3-group quicksort (fast when many values are equal):
(defn qsort3 [[pvt :as coll]]
(when pvt
(let [{left -1 mid 0 right 1} (group-by #(compare % pvt) coll)]
(lazy-cat (qsort3 left) mid (qsort3 right)))))
[edit] CoffeeScript
# This shows quicksort-in-place.
quicksort = (a) ->
swap = (i, j) ->
return if i == j
[a[i], a[j]] = [a[j], a[i]]
divide = (v, start, end) ->
first_big = start
j = start
while j <= end
if a[j] < v
swap first_big, j
first_big += 1
j += 1
first_big
partition = (start, end) ->
v = a[end]
first_big = divide v, start, end-1
swap first_big, end
first_big
qs = (start, end) ->
return if start >= end
m = partition start, end
qs start, m-1
qs m+1, end
qs 0, a.length - 1
# test
do ->
a = [1, 3, 5, 7, 9, 8, 6, 4, 2, 0, 3.5]
quicksort(a)
console.log a # [ 0, 1, 2, 3, 3.5, 4, 5, 6, 7, 8, 9 ]
[edit] Common Lisp
The functional programming way
(defun quicksort (list)
(if (<= (length list) 1)
list
(let ((pivot (first list)))
(append (quicksort (remove-if-not #'(lambda (x) (< x pivot)) list))
(remove-if-not #'(lambda (x) (= x pivot)) list)
(quicksort (remove-if-not #'(lambda (x) (> x pivot)) list))))))
With macrolet
(defun qs (list)
(if (< (length list) 2)
list
(macrolet ((pivot (test) `(remove (first list) list :test-not #',test)))
(append (qs (pivot >)) (pivot =) (qs (pivot <))))))
In-place non-functional
(defun quicksort (sequence)
(labels ((swap (a b) (rotatef (elt sequence a) (elt sequence b)))
(sub-sort (left right)
(when (< left right)
(let ((pivot (elt sequence right))
(index left))
(loop for i from left below right
when (<= (elt sequence i) pivot)
do (swap i (prog1 index (incf index))))
(swap right index)
(sub-sort left (1- index))
(sub-sort (1+ index) right)))))
(sub-sort 0 (1- (length sequence)))
sequence))
[edit] Curry
Copied from Curry: Example Programs.
-- quicksort using higher-order functions:
qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:l) = qsort (filter (<x) l) ++ x : qsort (filter (>=x) l)
goal = qsort [2,3,1,0]
[edit] D
A high-level version:
import std.stdio;
T[] quickSort(T)(T[] items) {
if (items.length <= 1)
return items;
T[] less, more;
foreach (x; items[1 .. $])
(x < items[0] ? less : more) ~= x;
return quickSort(less) ~ items[0] ~ quickSort(more);
}
void main() {
writeln(quickSort([4, 65, 2, -31, 0, 99, 2, 83, 782, 1]));
}
Output:
[-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]
[edit] Dart
quickSort(List a) {
if (a.length <= 1) {
return a;
}
var pivot = a[0];
var less = [];
var more = [];
var pivotList = [];
// Partition
a.forEach((var i){
if (i.compareTo(pivot) < 0) {
less.add(i);
} else if (i.compareTo(pivot) > 0) {
more.add(i);
} else {
pivotList.add(i);
}
});
// Recursively sort sublists
less = quickSort(less);
more = quickSort(more);
// Concatenate results
less.addAll(pivotList);
less.addAll(more);
return less;
}
void main() {
var arr=[1,5,2,7,3,9,4,6,8];
print("Before sort");
arr.forEach((var i)=>print("$i"));
arr = quickSort(arr);
print("After sort");
arr.forEach((var i)=>print("$i"));
}
[edit] E
def quicksort := {
def swap(container, ixA, ixB) {
def temp := container[ixA]
container[ixA] := container[ixB]
container[ixB] := temp
}
def partition(array, var first :int, var last :int) {
if (last <= first) { return }
# Choose a pivot
def pivot := array[def pivotIndex := (first + last) // 2]
# Move pivot to end temporarily
swap(array, pivotIndex, last)
var swapWith := first
# Scan array except for pivot, and...
for i in first..!last {
if (array[i] <= pivot) { # items ≤ the pivot
swap(array, i, swapWith) # are moved to consecutive positions on the left
swapWith += 1
}
}
# Swap pivot into between-partition position.
# Because of the swapping we know that everything before swapWith is less
# than or equal to the pivot, and the item at swapWith (since it was not
# swapped) is greater than the pivot, so inserting the pivot at swapWith
# will preserve the partition.
swap(array, swapWith, last)
return swapWith
}
def quicksortR(array, first :int, last :int) {
if (last <= first) { return }
def pivot := partition(array, first, last)
quicksortR(array, first, pivot - 1)
quicksortR(array, pivot + 1, last)
}
def quicksort(array) { # returned from block
quicksortR(array, 0, array.size() - 1)
}
}
[edit] Erlang
like haskell
qsort([]) -> [];
qsort([X|Xs]) ->
qsort([ Y || Y <- Xs, Y < X]) ++ [X] ++ qsort([ Y || Y <- Xs, Y >= X]).
[edit] F#
let rec qsort = function
[] -> []
| x::xs ->
qsort [for a in xs do if a < x then yield a]@x::
qsort [for a in xs do if a >= x then yield a]
[edit] Factor
: qsort ( seq -- seq )
dup empty? [
unclip [ [ < ] curry partition [ qsort ] bi@ ] keep
prefix append
] unless ;
[edit] Fexl
# (sort keep compare xs) sorts the list xs using the three-way comparison
# function. It keeps duplicates if the keep flag is true, otherwise it
# discards them and returns only the unique entries.
\sort ==
(\keep\compare\xs
xs end \x\xs
\lo = (filter (\y compare y x T F F) xs)
\hi = (filter (\y compare y x F keep T) xs)
append (sort keep compare lo);
item x;
sort keep compare hi
)
[edit] Forth
defer lessthan ( a@ b@ -- ? ) ' < is lessthan
: mid ( l r -- mid ) over - 2/ -cell and + ;
: exch ( addr1 addr2 -- ) dup @ >r over @ swap ! r> swap ! ;
: partition ( l r -- l r r2 l2 )
2dup mid @ >r ( r: pivot )
2dup begin
swap begin dup @ r@ lessthan while cell+ repeat
swap begin r@ over @ lessthan while cell- repeat
2dup <= if 2dup exch >r cell+ r> cell- then
2dup > until r> drop ;
: qsort ( l r -- )
partition swap rot
\ 2over 2over - + < if 2swap then
2dup < if recurse else 2drop then
2dup < if recurse else 2drop then ;
: sort ( array len -- )
dup 2 < if 2drop exit then
1- cells over + qsort ;
[edit] Fortran
MODULE Qsort_Module
IMPLICIT NONE
CONTAINS
RECURSIVE SUBROUTINE Qsort(a)
INTEGER, INTENT(IN OUT) :: a(:)
INTEGER :: split
IF(size(a) > 1) THEN
CALL Partition(a, split)
CALL Qsort(a(:split-1))
CALL Qsort(a(split:))
END IF
END SUBROUTINE Qsort
SUBROUTINE Partition(a, marker)
INTEGER, INTENT(IN OUT) :: a(:)
INTEGER, INTENT(OUT) :: marker
INTEGER :: left, right, pivot, temp
pivot = (a(1) + a(size(a))) / 2 ! Average of first and last elements to prevent quadratic
left = 0 ! behavior with sorted or reverse sorted data
right = size(a) + 1
DO WHILE (left < right)
right = right - 1
DO WHILE (a(right) > pivot)
right = right-1
END DO
left = left + 1
DO WHILE (a(left) < pivot)
left = left + 1
END DO
IF (left < right) THEN
temp = a(left)
a(left) = a(right)
a(right) = temp
END IF
END DO
IF (left == right) THEN
marker = left + 1
ELSE
marker = left
END IF
END SUBROUTINE Partition
END MODULE Qsort_Module
PROGRAM Quicksort
USE Qsort_Module
IMPLICIT NONE
INTEGER, PARAMETER :: n = 100
INTEGER :: array(n)
INTEGER :: i
REAL :: x
CALL RANDOM_SEED
DO i = 1, n
CALL RANDOM_NUMBER(x)
array(i) = INT(x * 10000)
END DO
WRITE (*, "(A)") "array is :-"
WRITE (*, "(10I5)") array
CALL Qsort(array)
WRITE (*,*)
WRITE (*, "(A)") "sorted array is :-"
WRITE (*,"(10I5)") array
END PROGRAM Quicksort
[edit] Go
Old school, following Hoare's 1962 paper.
As a nod to the task request to work for all types with weak strict ordering, code below uses the < operator when comparing key values. The three points are noted in the code below.
Actually supporting arbitrary types would then require at a minimum a user supplied less-than function, and values referenced from an array of interface{} types. More efficient and flexible though is the sort interface of the Go sort package. Replicating that here seemed beyond the scope of the task so code was left written to sort an array of ints.
Go has no language support for indexing with discrete types other than integer types, so this was not coded.
Finally, the choice of a recursive closure over passing slices to a recursive function is really just a very small optimization. Slices are cheap because they do not copy the underlying array, but there's still a tiny bit of overhead in constructing the slice object. Passing just the two numbers is in the interest of avoiding that overhead.
package main
import "fmt"
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
fmt.Println("unsorted:", list)
quicksort(list)
fmt.Println("sorted! ", list)
}
func quicksort(a []int) {
var pex func(int, int)
pex = func(lower, upper int) {
for {
switch upper - lower {
case -1, 0: // 0 or 1 item in segment. nothing to do here!
return
case 1: // 2 items in segment
// < operator respects strict weak order
if a[upper] < a[lower] {
// a quick exchange and we're done.
a[upper], a[lower] = a[lower], a[upper]
}
return
// Hoare suggests optimized sort-3 or sort-4 algorithms here,
// but does not provide an algorithm.
}
// Hoare stresses picking a bound in a way to avoid worst case
// behavior, but offers no suggestions other than picking a
// random element. A function call to get a random number is
// relatively expensive, so the method used here is to simply
// choose the middle element. This at least avoids worst case
// behavior for the obvious common case of an already sorted list.
bx := (upper + lower) / 2
b := a[bx] // b = Hoare's "bound" (aka "pivot")
lp := lower // lp = Hoare's "lower pointer"
up := upper // up = Hoare's "upper pointer"
outer:
for {
// use < operator to respect strict weak order
for lp < upper && !(b < a[lp]) {
lp++
}
for {
if lp > up {
// "pointers crossed!"
break outer
}
// < operator for strict weak order
if a[up] < b {
break // inner
}
up--
}
// exchange
a[lp], a[up] = a[up], a[lp]
lp++
up--
}
// segment boundary is between up and lp, but lp-up might be
// 1 or 2, so just call segment boundary between lp-1 and lp.
if bx < lp {
// bound was in lower segment
if bx < lp-1 {
// exchange bx with lp-1
a[bx], a[lp-1] = a[lp-1], b
}
up = lp - 2
} else {
// bound was in upper segment
if bx > lp {
// exchange
a[bx], a[lp] = a[lp], b
}
up = lp - 1
lp++
}
// "postpone the larger of the two segments" = recurse on
// the smaller segment, then iterate on the remaining one.
if up-lower < upper-lp {
pex(lower, up)
lower = lp
} else {
pex(lp, upper)
upper = up
}
}
}
pex(0, len(a)-1)
}
Output:
unsorted: [31 41 59 26 53 58 97 93 23 84] sorted! [23 26 31 41 53 58 59 84 93 97]
[edit] Haskell
The famous two-liner, reflecting the underlying algorithm directly:
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]
A more efficient version, doing only one comparison per element:
import Data.List
qsort [] = []
qsort (x:xs) = qsort ys ++ x : qsort zs where (ys, zs) = partition (< x) xs
[edit] IDL
IDL has a powerful optimized sort() built-in. The following is thus merely for demonstration.
function qs, arr
if (count = n_elements(arr)) lt 2 then return,arr
pivot = total(arr) / count ; use the average for want of a better choice
return,[qs(arr[where(arr le pivot)]),qs(arr[where(arr gt pivot)])]
end
Example:
IDL> print,qs([3,17,-5,12,99])
-5 3 12 17 99
[edit] Icon and Unicon
procedure main() #: demonstrate various ways to sort a list and string
demosort(quicksort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
procedure quicksort(X,op,lower,upper) #: return sorted list
local pivot,x
if /lower := 1 then { # top level call setup
upper := *X
op := sortop(op,X) # select how and what we sort
}
if upper - lower > 0 then {
every x := quickpartition(X,op,lower,upper) do # find a pivot and sort ...
/pivot | X := x # ... how to return 2 values w/o a structure
X := quicksort(X,op,lower,pivot-1) # ... left
X := quicksort(X,op,pivot,upper) # ... right
}
return X
end
procedure quickpartition(X,op,lower,upper) #: quicksort partitioner helper
local pivot
static pivotL
initial pivotL := list(3)
pivotL[1] := X[lower] # endpoints
pivotL[2] := X[upper] # ... and
pivotL[3] := X[lower+?(upper-lower)] # ... random midpoint
if op(pivotL[2],pivotL[1]) then pivotL[2] :=: pivotL[1] # mini-
if op(pivotL[3],pivotL[2]) then pivotL[3] :=: pivotL[2] # ... sort
pivot := pivotL[2] # median is pivot
lower -:= 1
upper +:= 1
while lower < upper do { # find values on wrong side of pivot ...
while op(pivot,X[upper -:= 1]) # ... rightmost
while op(X[lower +:=1],pivot) # ... leftmost
if lower < upper then # not crossed yet
X[lower] :=: X[upper] # ... swap
}
suspend lower # 1st return pivot point
suspend X # 2nd return modified X (in case immutable)
end
Implementation notes:
- Since this transparently sorts both string and list arguments the result must 'return' to bypass call by value (strings)
- The partition procedure must "return" two values - 'suspend' is used to accomplish this
Algorithm notes:
- The use of a type specific sorting operator meant that a general pivot choice need to be made. The median of the ends and random middle seemed reasonable. It turns out to have been suggested by Sedgewick.
- Sedgewick's suggestions for tail calling to recurse into the larger side and using insertion sort below a certain size were not implemented. (Q: does Icon/Unicon has tail calling optimizations?)
Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.
Sorting Demo using procedure quicksort
on list : [ 3 14 1 5 9 2 6 3 ]
with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms)
...
on string : "qwerty"
with op = &null: "eqrtwy" (0 ms)
[edit] Io
List do(
quickSort := method(
if(size > 1) then(
pivot := at(size / 2 floor)
return select(x, x < pivot) quickSort appendSeq(
select(x, x == pivot) appendSeq(select(x, x > pivot) quickSort)
)
) else(return self)
)
quickSortInPlace := method(
copy(quickSort)
)
)
lst := list(5, -1, -4, 2, 9)
lst quickSort println # ==> list(-4, -1, 2, 5, 9)
lst quickSortInPlace println # ==> list(-4, -1, 2, 5, 9)
Another more low-level Quicksort implementation can be found in Io's [github ] repository.
[edit] J
sel=: 1 : 'x # ['
quicksort=: 3 : 0
if.
1 >: #y
do.
y
else.
e=. y{~?#y
(quicksort y <sel e),(y =sel e),quicksort y >sel e
end.
)
See the Quicksort essay in the J Wiki for additional explanations and examples.
[edit] Java
public static <E extends Comparable<? super E>> List<E> quickSort(List<E> arr) {
if (arr.size() <= 1)
return arr;
E pivot = arr.getFirst(); //This pivot can change to get faster results
List<E> less = new LinkedList<E>();
List<E> pivotList = new LinkedList<E>();
List<E> more = new LinkedList<E>();
// Partition
for (E i: arr) {
if (i.compareTo(pivot) < 0)
less.add(i);
else if (i.compareTo(pivot) > 0)
more.add(i);
else
pivotList.add(i);
}
// Recursively sort sublists
less = quickSort(less);
more = quickSort(more);
// Concatenate results
less.addAll(pivotList);
less.addAll(more);
return less;
}
[edit] JavaScript
function sort(array, less) {
function swap(i, j) { var t=array[i]; array[i]=array[j]; array[j]=t }
function quicksort(left, right) {
if (left < right) {
var pivot = array[(left + right) >> 1];
var left_new = left, right_new = right;
do {
while (less(array[left_new], pivot)
left_new++;
while (less(pivot, array[right_new])
right_new--;
if (left_new <= right_new)
swap(left_new++, right_new--);
} while (left_new <= right_new);
quicksort(left, right_new);
quicksort(left_new, right);
}
}
quicksort(0, array.length-1);
return array;
}
The functional programming way
Array.prototype.quick_sort = function ()
{
if (this.length <= 1)
return this;
var pivot = this[Math.round(this.length / 2)];
return this.filter(function (x) { return x < pivot }).quick_sort().concat(
this.filter(function (x) { return x == pivot })).concat(
this.filter(function (x) { return x > pivot }).quick_sort());
}
[edit] Joy
DEFINE qsort ==
[small] # termination condition: 0 or 1 element
[] # do nothing
[uncons [>] split] # pivot and two lists
[enconcat] # insert the pivot after the recursion
binrec. # recursion on the two lists
[edit] K
quicksort:{f:*x@1?#x;:[0=#x;x;,/(_f x@&x<f;x@&x=f;_f x@&x>f)]}
Example:
quicksort 1 3 5 7 9 8 6 4 2
Output:
1 2 3 4 5 6 7 8 9
Explanation:
_f()
is the current function called recursively.
:[....]
generally means :[condition1;then1;condition2;then2;....;else]. Though here it is used as :[if;then;else].
This construct
f:*x@1?#x
assigns a random element in x (the argument) to f, as the pivot value.
And here is the full if/then/else clause:
:[
0=#x; / if length of x is zero
x; / then return x
/ else
,/( / join the results of:
_f x@&x<f / sort (recursively) elements less than f (pivot)
x@&x=f / element equal to f
_f x@&x>f) / sort (recursively) elements greater than f
]
Though - as with APL and J - for larger arrays it's much faster to sort using "<" (grade up) which gives the indices of the list sorted ascending, i.e.
t@<t:1 3 5 7 9 8 6 4 2
[edit] Logo
; quicksort (lists, functional)
to small? :list
output or [empty? :list] [empty? butfirst :list]
end
to quicksort :list
if small? :list [output :list]
localmake "pivot first :list
output (sentence
quicksort filter [? < :pivot] butfirst :list
filter [? = :pivot] :list
quicksort filter [? > :pivot] butfirst :list
)
end
show quicksort [1 3 5 7 9 8 6 4 2]
; quicksort (arrays, in-place)
to incr :name
make :name (thing :name) + 1
end
to decr :name
make :name (thing :name) - 1
end
to swap :i :j :a
localmake "t item :i :a
setitem :i :a item :j :a
setitem :j :a :t
end
to quick :a :low :high
if :high <= :low [stop]
localmake "l :low
localmake "h :high
localmake "pivot item ashift (:l + :h) -1 :a
do.while [
while [(item :l :a) < :pivot] [incr "l]
while [(item :h :a) > :pivot] [decr "h]
if :l <= :h [swap :l :h :a incr "l decr "h]
] [:l <= :h]
quick :a :low :h
quick :a :l :high
end
to sort :a
quick :a first :a count :a
end
make "test {1 3 5 7 9 8 6 4 2}
sort :test
show :test
[edit] Logtalk
quicksort(List, Sorted) :-
quicksort(List, [], Sorted).
quicksort([], Sorted, Sorted).
quicksort([Pivot| Rest], Acc, Sorted) :-
partition(Rest, Pivot, Smaller0, Bigger0),
quicksort(Smaller0, [Pivot| Bigger], Sorted),
quicksort(Bigger0, Acc, Bigger).
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)
).
[edit] Lua
--in-place quicksort
function quicksort(t, start, endi)
start, endi = start or 1, endi or #t
--partition w.r.t. first element
if(endi - start < 2) then return t end
local pivot = start
for i = start + 1, endi do
if t[i] <= t[pivot] then
local temp = t[pivot + 1]
t[pivot + 1] = t[pivot]
if(i == pivot + 1) then
t[pivot] = temp
else
t[pivot] = t[i]
t[i] = temp
end
pivot = pivot + 1
end
end
t = quicksort(t, start, pivot - 1)
return quicksort(t, pivot + 1, endi)
end
--example
print(unpack(quicksort{5, 2, 7, 3, 4, 7, 1}))
[edit] Lucid
qsort(a) = if eof(first a) then a else follow(qsort(b0),qsort(b1)) fi
where
p = first a < a;
b0 = a whenever p;
b1 = a whenever not p;
follow(x,y) = if xdone then y upon xdone else x fi
where
xdone = iseod x fby xdone or iseod x;
end;
end
[edit] M4
dnl return the first element of a list when called in the funny way seen below
define(`arg1', `$1')dnl
dnl
dnl append lists 1 and 2
define(`append',
`ifelse(`$1',`()',
`$2',
`ifelse(`$2',`()',
`$1',
`substr($1,0,decr(len($1))),substr($2,1)')')')dnl
dnl
dnl separate list 2 based on pivot 1, appending to left 3 and right 4,
dnl until 2 is empty, and then combine the sort of left with pivot with
dnl sort of right
define(`sep',
`ifelse(`$2', `()',
`append(append(quicksort($3),($1)),quicksort($4))',
`ifelse(eval(arg1$2<=$1),1,
`sep($1,(shift$2),append($3,(arg1$2)),$4)',
`sep($1,(shift$2),$3,append($4,(arg1$2)))')')')dnl
dnl
dnl pick first element of list 1 as pivot and separate based on that
define(`quicksort',
`ifelse(`$1', `()',
`()',
`sep(arg1$1,(shift$1),`()',`()')')')dnl
dnl
quicksort((3,1,4,1,5,9))
Output:
(1,1,3,4,5,9)
[edit] Mathematica
QuickSort[x_List] := Module[{pivot},
If[Length@x <= 1, Return[x]];
pivot = RandomChoice@x;
Flatten@{QuickSort[Cases[x, j_ /; j < pivot]], Cases[x, j_ /; j == pivot], QuickSort[Cases[x, j_ /; j > pivot]]}
]
[edit] MATLAB
This implements the pseudo-code in the specification. The input can be either a row or column vector, but the returned vector will always be a row vector. This can be modified to operate on any built-in primitive or user defined class by replacing the "<=" and ">" comparisons with "le" and "gt" functions respectively. This is because operators can not be overloaded, but the functions that are equivalent to the operators can be overloaded in class definitions.
This should be placed in a file named quickSort.m.
function sortedArray = quickSort(array)
if numel(array) <= 1 %If the array has 1 element then it can't be sorted
sortedArray = array;
return
end
pivot = array(end);
array(end) = [];
%Create two new arrays which contain the elements that are less than or
%equal to the pivot called "less" and greater than the pivot called
%"greater"
less = array( array <= pivot );
greater = array( array > pivot );
%The sorted array is the concatenation of the sorted "less" array, the
%pivot and the sorted "greater" array in that order
sortedArray = [quickSort(less) pivot quickSort(greater)];
end
A slightly more vectorized version of the above code that removes the need for the less and greater arrays:
function sortedArray = quickSort(array)
if numel(array) <= 1 %If the array has 1 element then it can't be sorted
sortedArray = array;
return
end
pivot = array(end);
array(end) = [];
sortedArray = [quickSort( array(array <= pivot) ) pivot quickSort( array(array > pivot) )];
end
Sample usage:
quickSort([4,3,7,-2,9,1])
ans =
-2 1 3 4 7 9
[edit] MAXScript
fn quickSort arr =
(
less = #()
pivotList = #()
more = #()
if arr.count <= 1 then
(
arr
)
else
(
pivot = arr[arr.count/2]
for i in arr do
(
case of
(
(i < pivot): (append less i)
(i == pivot): (append pivotList i)
(i > pivot): (append more i)
)
)
less = quickSort less
more = quickSort more
less + pivotList + more
)
)
a = #(4, 89, -3, 42, 5, 0, 2, 889)
a = quickSort a
[edit] Modula-2
The definition module exposes the interface. This one uses the procedure variable feature to pass a caller defined compare callback function so that it can sort various simple and structured record types.
This Quicksort assumes that you are working with an an array of pointers to an arbitrary type and are not moving the record data itself but only the pointers. The M2 type "ADDRESS" is considered compatible with any pointer type.
The use of type ADDRESS here to achieve genericity is something of a chink the the normal strongly typed flavor of Modula-2. Unlike the other language types, "system" types such as ADDRESS or WORD must be imported explicity from the SYSTEM MODULE. The ISO standard for the "Generic Modula-2" language extension provides genericity without the chink, but most compilers have not implemented this extension.
(*#####################*)
DEFINITION MODULE QSORT;
(*#####################*)
FROM SYSTEM IMPORT ADDRESS;
TYPE CmpFuncPtrs = PROCEDURE(ADDRESS, ADDRESS):INTEGER;
PROCEDURE QuickSortPtrs(VAR Array:ARRAY OF ADDRESS; N:CARDINAL;
Compare:CmpFuncPtrs);
END QSORT.
The implementation module is not visible to clients, so it may be changed without worry so long as it still implements the definition.
Sedgewick suggests that faster sorting will be achieved if you drop back to an insertion sort once the partitions get small.
(*##########################*)
IMPLEMENTATION MODULE QSORT;
(*##########################*)
FROM SYSTEM IMPORT ADDRESS;
CONST SmallPartition = 9;
(*
NOTE
1.Reference on QuickSort: "Implementing Quicksort Programs", Robert
Sedgewick, Communications of the ACM, Oct 78, v21 #10.
*)
(*==============================================================*)
PROCEDURE QuickSortPtrs(VAR Array:ARRAY OF ADDRESS; N:CARDINAL;
Compare:CmpFuncPtrs);
(*==============================================================*)
(*-----------------------------*)
PROCEDURE Swap(VAR A,B:ADDRESS);
(*-----------------------------*)
VAR temp :ADDRESS;
BEGIN
temp := A; A := B; B := temp;
END Swap;
(*-------------------------------*)
PROCEDURE TstSwap(VAR A,B:ADDRESS);
(*-------------------------------*)
VAR temp :ADDRESS;
BEGIN
IF Compare(A,B) > 0 THEN
temp := A; A := B; B := temp;
END;
END TstSwap;
(*--------------*)
PROCEDURE Isort;
(*--------------*)
(*
Insertion sort.
*)
VAR i,j :CARDINAL;
temp :ADDRESS;
BEGIN
IF N < 2 THEN RETURN END;
FOR i := N-2 TO 0 BY -1 DO
IF Compare(Array[i],Array[i+1]) > 0 THEN
temp := Array[i];
j := i+1;
REPEAT
Array[j-1] := Array[j];
INC(j);
UNTIL (j = N) OR (Compare(Array[j],temp) >= 0);
Array[j-1] := temp;
END;
END;
END Isort;
(*----------------------------------*)
PROCEDURE Quick(left,right:CARDINAL);
(*----------------------------------*)
VAR
i,j,
second :CARDINAL;
Partition :ADDRESS;
BEGIN
IF right > left THEN
i := left; j := right;
Swap(Array[left],Array[(left+right) DIV 2]);
second := left+1; (* insure 2nd element is in *)
TstSwap(Array[second], Array[right]); (* the lower part, last elem *)
TstSwap(Array[left], Array[right]); (* in the upper part *)
TstSwap(Array[second], Array[left]); (* THUS, only one test is *)
(* needed in repeat loops *)
Partition := Array[left];
LOOP
REPEAT INC(i) UNTIL Compare(Array[i],Partition) >= 0;
REPEAT DEC(j) UNTIL Compare(Array[j],Partition) <= 0;
IF j < i THEN
EXIT
END;
Swap(Array[i],Array[j]);
END; (*loop*)
Swap(Array[left],Array[j]);
IF (j > 0) AND (j-1-left >= SmallPartition) THEN
Quick(left,j-1);
END;
IF right-i >= SmallPartition THEN
Quick(i,right);
END;
END;
END Quick;
BEGIN (* QuickSortPtrs --------------------------------------------------*)
IF N > SmallPartition THEN (* won't work for 2 elements *)
Quick(0,N-1);
END;
Isort;
END QuickSortPtrs;
END QSORT.
[edit] Modula-3
This code is taken from libm3, which is basically Modula-3's "standard library". Note that this code uses Insertion sort when the array is less than 9 elements long.
GENERIC INTERFACE ArraySort(Elem);
PROCEDURE Sort(VAR a: ARRAY OF Elem.T; cmp := Elem.Compare);
END ArraySort.
GENERIC MODULE ArraySort (Elem);
PROCEDURE Sort (VAR a: ARRAY OF Elem.T; cmp := Elem.Compare) =
BEGIN
QuickSort (a, 0, NUMBER (a), cmp);
InsertionSort (a, 0, NUMBER (a), cmp);
END Sort;
PROCEDURE QuickSort (VAR a: ARRAY OF Elem.T; lo, hi: INTEGER;
cmp := Elem.Compare) =
CONST CutOff = 9;
VAR i, j: INTEGER; key, tmp: Elem.T;
BEGIN
WHILE (hi - lo > CutOff) DO (* sort a[lo..hi) *)
(* use median-of-3 to select a key *)
i := (hi + lo) DIV 2;
IF cmp (a[lo], a[i]) < 0 THEN
IF cmp (a[i], a[hi-1]) < 0 THEN
key := a[i];
ELSIF cmp (a[lo], a[hi-1]) < 0 THEN
key := a[hi-1]; a[hi-1] := a[i]; a[i] := key;
ELSE
key := a[lo]; a[lo] := a[hi-1]; a[hi-1] := a[i]; a[i] := key;
END;
ELSE (* a[lo] >= a[i] *)
IF cmp (a[hi-1], a[i]) < 0 THEN
key := a[i]; tmp := a[hi-1]; a[hi-1] := a[lo]; a[lo] := tmp;
ELSIF cmp (a[lo], a[hi-1]) < 0 THEN
key := a[lo]; a[lo] := a[i]; a[i] := key;
ELSE
key := a[hi-1]; a[hi-1] := a[lo]; a[lo] := a[i]; a[i] := key;
END;
END;
(* partition the array *)
i := lo+1; j := hi-2;
(* find the first hole *)
WHILE cmp (a[j], key) > 0 DO DEC (j) END;
tmp := a[j];
DEC (j);
LOOP
IF (i > j) THEN EXIT END;
WHILE i < hi AND cmp (a[i], key) < 0 DO INC (i) END;
IF (i > j) THEN EXIT END;
a[j+1] := a[i];
INC (i);
WHILE j > lo AND cmp (a[j], key) > 0 DO DEC (j) END;
IF (i > j) THEN IF (j = i-1) THEN DEC (j) END; EXIT END;
a[i-1] := a[j];
DEC (j);
END;
(* fill in the last hole *)
a[j+1] := tmp;
i := j+2;
(* then, recursively sort the smaller subfile *)
IF (i - lo < hi - i)
THEN QuickSort (a, lo, i-1, cmp); lo := i;
ELSE QuickSort (a, i, hi, cmp); hi := i-1;
END;
END; (* WHILE (hi-lo > CutOff) *)
END QuickSort;
PROCEDURE InsertionSort (VAR a: ARRAY OF Elem.T; lo, hi: INTEGER;
cmp := Elem.Compare) =
VAR j: INTEGER; key: Elem.T;
BEGIN
FOR i := lo+1 TO hi-1 DO
key := a[i];
j := i-1;
WHILE (j >= lo) AND cmp (key, a[j]) < 0 DO
a[j+1] := a[j];
DEC (j);
END;
a[j+1] := key;
END;
END InsertionSort;
BEGIN
END ArraySort.
To use this generic code to sort an array of text, we create two files called TextSort.i3 and TextSort.m3, respectively.
INTERFACE TextSort = ArraySort(Text) END TextSort.
MODULE TextSort = ArraySort(Text) END TextSort.
Then, as an example:
MODULE Main;
IMPORT IO, TextSort;
VAR arr := ARRAY [1..10] OF TEXT {"Foo", "bar", "!ooF", "Modula-3", "hickup",
"baz", "quuz", "Zeepf", "woo", "Rosetta Code"};
BEGIN
TextSort.Sort(arr);
FOR i := FIRST(arr) TO LAST(arr) DO
IO.Put(arr[i] & "\n");
END;
END Main.
[edit] Nemerle
A little less clean and concise than Haskell, but essentially the same.
using System;
using System.Console;
using Nemerle.Collections.NList;
module Quicksort
{
Qsort[T] (x : list[T]) : list[T]
where T : IComparable
{
|[] => []
|x::xs => Qsort($[y|y in xs, (y.CompareTo(x) < 0)]) + [x] + Qsort($[y|y in xs, (y.CompareTo(x) > 0)])
}
Main() : void
{
def empty = [];
def single = [2];
def several = [2, 6, 1, 7, 3, 9, 4];
WriteLine(Qsort(empty));
WriteLine(Qsort(single));
WriteLine(Qsort(several));
}
}
[edit] NetRexx
This sample implements both the simple and in place algorithms as described in the task's description:
/* NetRexx */
options replace format comments java crossref savelog symbols binary
import java.util.List
placesList = [String -
"UK London", "US New York", "US Boston", "US Washington" -
, "UK Washington", "US Birmingham", "UK Birmingham", "UK Boston" -
]
lists = [ -
placesList -
, quickSortSimple(String[] Arrays.copyOf(placesList, placesList.length)) -
, quickSortInplace(String[] Arrays.copyOf(placesList, placesList.length)) -
]
loop ln = 0 to lists.length - 1
cl = lists[ln]
loop ct = 0 to cl.length - 1
say cl[ct]
end ct
say
end ln
return
method quickSortSimple(array = String[]) public constant binary returns String[]
rl = String[array.length]
al = List quickSortSimple(Arrays.asList(array))
al.toArray(rl)
return rl
method quickSortSimple(array = List) public constant binary returns ArrayList
if array.size > 1 then do
less = ArrayList()
equal = ArrayList()
greater = ArrayList()
pivot = array.get(Random().nextInt(array.size - 1))
loop x_ = 0 to array.size - 1
if (Comparable array.get(x_)).compareTo(Comparable pivot) < 0 then less.add(array.get(x_))
if (Comparable array.get(x_)).compareTo(Comparable pivot) = 0 then equal.add(array.get(x_))
if (Comparable array.get(x_)).compareTo(Comparable pivot) > 0 then greater.add(array.get(x_))
end x_
less = quickSortSimple(less)
greater = quickSortSimple(greater)
out = ArrayList(array.size)
out.addAll(less)
out.addAll(equal)
out.addAll(greater)
array = out
end
return ArrayList array
method quickSortInplace(array = String[]) public constant binary returns String[]
rl = String[array.length]
al = List quickSortInplace(Arrays.asList(array))
al.toArray(rl)
return rl
method quickSortInplace(array = List, ixL = int 0, ixR = int array.size - 1) public constant binary returns ArrayList
if ixL < ixR then do
ixP = int ixL + (ixR - ixL) % 2
ixP = quickSortInplacePartition(array, ixL, ixR, ixP)
quickSortInplace(array, ixL, ixP - 1)
quickSortInplace(array, ixP + 1, ixR)
end
array = ArrayList(array)
return ArrayList array
method quickSortInplacePartition(array = List, ixL = int, ixR = int, ixP = int) public constant binary returns int
pivotValue = array.get(ixP)
rValue = array.get(ixR)
array.set(ixP, rValue)
array.set(ixR, pivotValue)
ixStore = ixL
loop i_ = ixL to ixR - 1
iValue = array.get(i_)
if (Comparable iValue).compareTo(Comparable pivotValue) < 0 then do
storeValue = array.get(ixStore)
array.set(i_, storeValue)
array.set(ixStore, iValue)
ixStore = ixStore + 1
end
end i_
storeValue = array.get(ixStore)
rValue = array.get(ixR)
array.set(ixStore, rValue)
array.set(ixR, storeValue)
return ixStore
- Output
UK London US New York US Boston US Washington UK Washington US Birmingham UK Birmingham UK Boston UK Birmingham UK Boston UK London UK Washington US Birmingham US Boston US New York US Washington UK Birmingham UK Boston UK London UK Washington US Birmingham US Boston US New York US Washington
[edit] Nial
quicksort is fork [ >= [1 first,tally],
pass,
link [
quicksort sublist [ < [pass, first], pass ],
sublist [ match [pass,first],pass ],
quicksort sublist [ > [pass,first], pass ]
]
]
Using it.
|quicksort [5, 8, 7, 4, 3]
=3 4 5 7 8
[edit] Nimrod
proc QuickSort(list: seq[int]): seq[int] =
if len(list) == 0:
return @[]
var pivot = list[0]
var left: seq[int] = @[]
var right: seq[int] = @[]
for i in low(list)+1..high(list):
if list[i] <= pivot:
left.add(list[i])
elif list[i] > pivot:
right.add(list[i])
result = QuickSort(left)
result.add(pivot)
result.add(QuickSort(right))
Usage:
var sorted: seq[int] = QuickSort(@[5,2,1,6,2,3,1,2,123,21,54,6,1])
for i in items(sorted):
echo(i)
[edit] OCaml
let rec quicksort gt = function
| [] -> []
| x::xs ->
let ys, zs = List.partition (gt x) xs in
(quicksort gt ys) @ (x :: (quicksort gt zs))
let _ =
quicksort (>) [4; 65; 2; -31; 0; 99; 83; 782; 1]
[edit] Octave
(The MATLAB version works as is in Octave, provided that the code is put in a file named quicksort.m, and everything below the return must be typed in the prompt of course)function f=quicksort(v) % v must be a column vector
f = v; n=length(v);
if(n > 1)
vl = min(f); vh = max(f); % min, max
p = (vl+vh)*0.5; % pivot
ia = find(f < p); ib = find(f == p); ic=find(f > p);
f = [quicksort(f(ia)); f(ib); quicksort(f(ic))];
end
endfunction
N=30; v=rand(N,1); tic,u=quicksort(v); toc
u
[edit] Oz
declare
fun {QuickSort Xs}
case Xs of nil then nil
[] Pivot|Xr then
fun {IsSmaller X} X < Pivot end
Smaller Larger
in
{List.partition Xr IsSmaller ?Smaller ?Larger}
{Append {QuickSort Smaller} Pivot|{QuickSort Larger}}
end
end
in
{Show {QuickSort [3 1 4 1 5 9 2 6 5]}}
[edit] PARI/GP
quickSort(v)={
if(#v<2, return(v));
my(less=List(),more=List(),same=List(),pivot);
pivot=median([v[random(#v)+1],v[random(#v)+1],v[random(#v)+1]]); \\ Middle-of-three
for(i=1,#v,
if(v[i]<pivot,
listput(less, v[i]),
if(v[i]==pivot, listput(same, v[i]), listput(more, v[i]))
)
);
concat(quickSort(Vec(less)), concat(Vec(same), quickSort(Vec(more))))
};
median(v)={
vecsort(v)[#v>>1]
};
[edit] Pascal
{ X is array of LongInt }
Procedure QuickSort ( Left, Right : LongInt );
Var
i, j : LongInt;
tmp, pivot : LongInt; { tmp & pivot are the same type as the elements of array }
Begin
i:=Left;
j:=Right;
pivot := X[(Left + Right) shr 1]; // pivot := X[(Left + Rigth) div 2]
Repeat
While pivot > X[i] Do i:=i+1;
While pivot < X[j] Do j:=j-1;
If i<j Then Begin
tmp:=X[i];
X[i]:=X[j];
X[j]:=tmp;
j:=j-1;
i:=i+1;
End;
Until i>j;
If Left<j Then QuickSort(Left,j);
If i<Right Then QuickSort(i,Right);
End;
[edit] Perl
sub quick_sort {
my @a = @_;
return @a if @a < 2;
my $p = pop @a;
quick_sort(grep $_ < $p, @a), $p, quick_sort(grep $_ >= $p, @a);
}
my @a = (4, 65, 2, -31, 0, 99, 83, 782, 1);
@a = quick_sort @a;
print "@a\n";
[edit] Perl 6
# Empty list sorts to the empty list
multi quicksort([]) { () }
# Otherwise, extract first item as pivot...
multi quicksort([$pivot, *@rest]) {
# Partition.
my @before := @rest.grep(* before $pivot);
my @after := @rest.grep(* !before $pivot);
# Sort the partitions.
(quicksort(@before), $pivot, quicksort(@after))
}
Note that @before and @after are bound to lazy lists, so the partitions can (at least in theory) be sorted in parallel.
[edit] PHP
function quicksort($arr){
$loe = $gt = array();
if(count($arr) < 2){
return $arr;
}
$pivot_key = key($arr);
$pivot = array_shift($arr);
foreach($arr as $val){
if($val <= $pivot){
$loe[] = $val;
}elseif ($val > $pivot){
$gt[] = $val;
}
}
return array_merge(quicksort($loe),array($pivot_key=>$pivot),quicksort($gt));
}
$arr = array(1, 3, 5, 7, 9, 8, 6, 4, 2);
$arr = quicksort($arr);
echo implode(',',$arr);
1,2,3,4,5,6,7,8,9
[edit] PicoLisp
(de quicksort (L)
(if (cdr L)
(let Pivot (car L)
(append (quicksort (filter '((A) (< A Pivot)) (cdr L)))
(filter '((A) (= A Pivot)) L )
(quicksort (filter '((A) (> A Pivot)) (cdr L)))) )
L) )
[edit] PL/I
DCL (T(20)) FIXED BIN(31); /* scratch space of length N */
QUICKSORT: PROCEDURE (A,AMIN,AMAX,N) RECURSIVE ;
DECLARE (A(*)) FIXED BIN(31);
DECLARE (N,AMIN,AMAX) FIXED BIN(31) NONASGN;
DECLARE (I,J,IA,IB,IC,PIV) FIXED BIN(31);
DECLARE (P,Q) POINTER;
DECLARE (AP(1)) FIXED BIN(31) BASED(P);
IF(N <= 1)THEN RETURN;
IA=0; IB=0; IC=N+1;
PIV=(AMIN+AMAX)/2;
DO I=1 TO N;
IF(A(I) < PIV)THEN DO;
IA+=1; A(IA)=A(I);
END; ELSE IF(A(I) > PIV) THEN DO;
IC-=1; T(IC)=A(I);
END; ELSE DO;
IB+=1; T(IB)=A(I);
END;
END;
DO I=1 TO IB; A(I+IA)=T(I); END;
DO I=IC TO N; A(I)=T(N+IC-I); END;
P=ADDR(A(IC));
IC=N+1-IC;
IF(IA > 1) THEN CALL QUICKSORT(A, AMIN, PIV-1,IA);
IF(IC > 1) THEN CALL QUICKSORT(AP,PIV+1,AMAX, IC);
RETURN;
END QUICKSORT;
MINMAX: PROC(A,AMIN,AMAX,N);
DCL (AMIN,AMAX) FIXED BIN(31),
(N,A(*)) FIXED BIN(31) NONASGN ;
DCL (I,X,Y) FIXED BIN(31);
AMIN=A(N); AMAX=AMIN;
DO I=1 TO N-1;
X=A(I); Y=A(I+1);
IF (X < Y)THEN DO;
IF (X < AMIN) THEN AMIN=X;
IF (Y > AMAX) THEN AMAX=Y;
END; ELSE DO;
IF (X > AMAX) THEN AMAX=X;
IF (Y < AMIN) THEN AMIN=Y;
END;
END;
RETURN;
END MINMAX;
CALL MINMAX(A,AMIN,AMAX,N);
CALL QUICKSORT(A,AMIN,AMAX,N);
[edit] PowerShell
Function SortThree( [Array] $data )
{
if( $data[ 0 ] -gt $data[ 1 ] )
{
if( $data[ 0 ] -lt $data[ 2 ] )
{
$data = $data[ 1, 0, 2 ]
} elseif ( $data[ 1 ] -lt $data[ 2 ] ){
$data = $data[ 1, 2, 0 ]
} else {
$data = $data[ 2, 1, 0 ]
}
} else {
if( $data[ 0 ] -gt $data[ 2 ] )
{
$data = $data[ 2, 0, 1 ]
} elseif( $data[ 1 ] -gt $data[ 2 ] ) {
$data = $data[ 0, 2, 1 ]
}
}
$data
}
Function QuickSort( [Array] $data, $rand = ( New-Object Random ) )
{
$datal = $data.length
if( $datal -gt 3 )
{
[void] $datal--
$median = ( SortThree $data[ 0, ( $rand.Next( 1, $datal - 1 ) ), -1 ] )[ 1 ]
$lt = @()
$eq = @()
$gt = @()
$data | ForEach-Object { if( $_ -lt $median ) { $lt += $_ } elseif( $_ -eq $median ) { $eq += $_ } else { $gt += $_ } }
$lt = ( QuickSort $lt $rand )
$gt = ( QuickSort $gt $rand )
$data = @($lt) + $eq + $gt
} elseif( $datal -eq 3 ) {
$data = SortThree( $data )
} elseif( $datal -eq 2 ) {
if( $data[ 0 ] -gt $data[ 1 ] )
{
$data = $data[ 1, 0 ]
}
}
$data
}
QuickSort 5,3,1,2,4
QuickSort 'e','c','a','b','d'
QuickSort 0.5,0.3,0.1,0.2,0.4
$l = 100; QuickSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )
[edit] Prolog
qsort( [], [] ).
qsort( [H|U], S ) :- splitBy(H, U, L, R), qsort(L, SL), qsort(R, SR), append(SL, [H|SR], S).
% splitBy( H, U, LS, RS )
% True if LS = { L in U | L <= H }; RS = { R in U | R > H }
splitBy( _, [], [], []).
splitBy( H, [U|T], [U|LS], RS ) :- U =< H, splitBy(H, T, LS, RS).
splitBy( H, [U|T], LS, [U|RS] ) :- U > H, splitBy(H, T, LS, RS).
[edit] PureBasic
Procedure qSort(Array a(1), firstIndex, lastIndex)
Protected low, high, pivotValue
low = firstIndex
high = lastIndex
pivotValue = a((firstIndex + lastIndex) / 2)
Repeat
While a(low) < pivotValue
low + 1
Wend
While a(high) > pivotValue
high - 1
Wend
If low <= high
Swap a(low), a(high)
low + 1
high - 1
EndIf
Until low > high
If firstIndex < high
qSort(a(), firstIndex, high)
EndIf
If low < lastIndex
qSort(a(), low, lastIndex)
EndIf
EndProcedure
Procedure quickSort(Array a(1))
qSort(a(),0,ArraySize(a()))
EndProcedure
[edit] Python
def quickSort(arr):
less = []
pivotList = []
more = []
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
for i in arr:
if i < pivot:
less.append(i)
elif i > pivot:
more.append(i)
else:
pivotList.append(i)
less = quickSort(less)
more = quickSort(more)
return less + pivotList + more
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a = quickSort(a)
In a Haskell fashion --
def qsort(L):
return (qsort([y for y in L[1:] if y < L[0]]) +
L[:1] +
qsort([y for y in L[1:] if y >= L[0]])) if len(L) > 1 else L
More readable, but still using list comprehensions:
def qsort(list):
if not list:
return []
else:
pivot = list[0]
less = [x for x in list if x < pivot]
more = [x for x in list[1:] if x >= pivot]
return qsort(less) + [pivot] + qsort(more)
[edit] Qi
(define keep
_ [] -> []
Pred [A|Rest] -> [A | (keep Pred Rest)] where (Pred A)
Pred [_|Rest] -> (keep Pred Rest))
(define quicksort
[] -> []
[A|R] -> (append (quicksort (keep (>= A) R))
[A]
(quicksort (keep (< A) R))))
(quicksort [6 8 5 9 3 2 2 1 4 7])
[edit] R
qsort <- function(v) {
if ( length(v) > 1 )
{
pivot <- (min(v) + max(v))/2.0 # Could also use pivot <- median(v)
c(qsort(v[v < pivot]), v[v == pivot], qsort(v[v > pivot]))
} else v
}
N <- 100
vs <- runif(N)
system.time(u <- qsort(vs))
print(u)
[edit] REXX
/*REXX program sorts an array using the quicksort method. */
call gen@ /*generate array elements. */
call show@ 'before sort' /*show before array elements*/
call quickSort highItem /*invoke the quick sort. */
call show@ ' after sort' /*show after array elements*/
exit
/*─────────────────────────────────────QUICKSORT subroutine───────-*/
quickSort: procedure expose @.
a.1=1
b.1=arg(1)
$=1
do while $\==0
l=a.$
t=b.$
$=$-1
if t<2 then iterate
h=l+t-1
?=l+t%2
if @.h<@.l then if @.?<@.h then do;p=@.h;@.h=@.l;end
else if @.?>@.l then p=@.l
else do;p=@.?;@.?=@.l;end
else if @.?<@.l then p=@.l
else if @.?>@.h then do;p=@.h;@.h=@.l;end
else do;p=@.?;@.?=@.l;end
j=l+1
k=h
do forever
do j=j while j<=k & @.j<=p; end
do k=k by -1 while j <k & @.k>=p; end
if j>=k then leave
_=@.j; @.j=@.k; @.k=_
end
k=j-1; @.l=@.k; @.k=p
$=$+1
if j<=? then do; a.$=j; b.$=h-j+1; $=$+1; a.$=l; b.$=k-l; end
else do; a.$=l; b.$=k-l; $=$+1; a.$=j; b.$=h-j+1; end
end
return
/*─────────────────────────────────────GEN@ subroutine────────────-/
gen@: @.='' /*assign default value. */
@.1 ="------------------- Rivers that form part of a state's (USA) border -----------------------------"
@.2 ="========================================================================================================================================"
@.3 ="Chattahoochee River: Alabama, Georgia"
@.4 ="Colorado River: Arizona, Nevada, California, Baja California (Mexico)"
@.5 ="St. Francis River: Arkansas, Missouri"
@.6 ="Poteau River: Arkansas, Oklahoma"
@.7 ="Byram River: Connecticut, New York"
@.8 ="Pawcatuck River: Connecticut, Rhode Island"
@.9 ="Perdido River: Florida, Alabama"
@.10="St. Marys River: Florida, Georgia"
@.11="Chattooga River: Georgia, South Carolina"
@.12="Tugaloo River: Georgia, South Carolina"
@.13="Snake River: Idaho, Washington, Oregon"
@.14="Wabash River: Illinois, Indiana"
@.15="Ohio River: Illinois, Indiana, Ohio, Kentucky, West Virginia"
@.16="Des Moines River: Iowa, Missouri"
@.17="Tennessee River: Kentucky, Tennessee, Mississippi, Alabama"
@.18="Big Sandy River: Kentucky, West Virginia"
@.19="Tug Fork River: Kentucky, West Virginia, Virginia"
@.20="Monument Creek: Maine, New Brunswick (Canda)"
@.21="St. Croix River: Maine, New Brunswick (Canda)"
@.22="Piscataqua River: Maine, New Hampshire"
@.23="St. Francis River: Maine, Quebec (Canada)"
@.24="St. John River: Maine, Quebec (Canada)"
@.25="Pocomoke River: Maryland, Virginia"
@.26="Potomac River: Maryland, Virginia, city of Washington (District of Columbia), West Virginia"
@.27="Montreal River: Michigan (upper peninsula ), Wisconsin"
@.28="Detroit River: Michigan, Ontario (Canada)"
@.29="St. Clair River: Michigan, Ontario (Canada)"
@.30="St. Marys River: Michigan, Ontario (Canada)"
@.31="Brule River: Michigan, Wisconsin"
@.32="Menominee River: Michigan, Wisconsin"
@.33="Pigeon River: Minnesota, Ontario (Canada)"
@.34="Rainy River: Minnesota, Ontario (Canada)"
@.35="St. Croix River: Minnesota, Wisconsin"
@.36="St. Louis River: Minnesota, Wisconsin"
@.37="Mississippi River: Minnesota, Wisconsin, Iowa, Illinois, Missouri, Kentucky, Tennesse, Arkansas, Mississippi, Louisiana"
@.38="Pearl River: Mississippi, Louisiana"
@.39="Halls Stream: New Hampshire, Canada"
@.40="Salmon Falls River: New Hampshire, Maine"
@.41="Connecticut River: New Hampshire, Vermont"
@.42="Hudson River (lower part only): New Jersey, New York"
@.43="Arthur Kill: New Jersey, New York (tidal strait)"
@.44="Kill Van Kull: New Jersey, New York (tidal strait)"
@.45="Rio Grande: New Mexico, Texas, Tamaulipas (Mexico), Nuevo Leon (Mexico), Coahuila De Zaragoza (Mexico), Chihuahua (Mexico)"
@.46="Niagara River: New York, Ontario (Canada)"
@.47="St. Lawrence River: New York, Ontario (Canada)"
@.48="Delaware River: New York, Pennsylvania, New Jersey, Delaware"
@.49="Catawba River: North Carolina, South Carolina"
@.50="Red River of the North: North Dakota, Minnesota"
@.51="Great Miami River (mouth only): Ohio, Indiana"
@.52="Arkansas River: Oklahoma, Arkansas"
@.53="Palmer River: Rhode Island, Massachusetts"
@.54="Runnins River: Rhode Island, Massachusetts"
@.55="Savannah River: South Carolina, Georgia"
@.56="Big Sioux River: South Dakota, Iowa"
@.57="Bois de Sioux River: South Dakota, Minnesota, North Dakota"
@.58="Missouri River: South Dakota, Nebraska, Iowa, Missouri, Kansas"
@.59="Sabine River: Texas, Louisiana"
@.60="Red River (Mississippi watershed): Texas, Oklahoma, Arkansas"
@.61="Poultney River: Vermont, New York"
@.62="Blackwater River: Virginia, North Carolina"
@.63="Columbia River: Washington, Oregon"
do highItem=1 while @.highItem\=='' /*find how many entries. */
end
highItem=highItem-1 /*adjust highItem slightly. */
return
/*─────────────────────────────────────SHOW@ subroutine───────────-*/
show@: widthH=length(highItem) /*maximum width of any line.*/
do j=1 for highItem
say 'element' right(j,widthH) arg(1)':' @.j
end
say copies('─',80) /*show a seperator line. */
return
Output:
element 1 before sort: ------------------- Rivers that form part of a state's (USA) border ----------------------------- element 2 before sort: ======================================================================================================================================== element 3 before sort: Chattahoochee River: Alabama, Georgia element 4 before sort: Colorado River: Arizona, Nevada, California, Baja California (Mexico) element 5 before sort: St. Francis River: Arkansas, Missouri element 6 before sort: Poteau River: Arkansas, Oklahoma element 7 before sort: Byram River: Connecticut, New York element 8 before sort: Pawcatuck River: Connecticut, Rhode Island element 9 before sort: Perdido River: Florida, Alabama element 10 before sort: St. Marys River: Florida, Georgia element 11 before sort: Chattooga River: Georgia, South Carolina element 12 before sort: Tugaloo River: Georgia, South Carolina element 13 before sort: Snake River: Idaho, Washington, Oregon element 14 before sort: Wabash River: Illinois, Indiana element 15 before sort: Ohio River: Illinois, Indiana, Ohio, Kentucky, West Virginia element 16 before sort: Des Moines River: Iowa, Missouri element 17 before sort: Tennessee River: Kentucky, Tennessee, Mississippi, Alabama element 18 before sort: Big Sandy River: Kentucky, West Virginia element 19 before sort: Tug Fork River: Kentucky, West Virginia, Virginia element 20 before sort: Monument Creek: Maine, New Brunswick (Canda) element 21 before sort: St. Croix River: Maine, New Brunswick (Canda) element 22 before sort: Piscataqua River: Maine, New Hampshire element 23 before sort: St. Francis River: Maine, Quebec (Canada) element 24 before sort: St. John River: Maine, Quebec (Canada) element 25 before sort: Pocomoke River: Maryland, Virginia element 26 before sort: Potomac River: Maryland, Virginia, city of Washington (District of Columbia), West Virginia element 27 before sort: Montreal River: Michigan (upper peninsula ), Wisconsin element 28 before sort: Detroit River: Michigan, Ontario (Canada) element 29 before sort: St. Clair River: Michigan, Ontario (Canada) element 30 before sort: St. Marys River: Michigan, Ontario (Canada) element 31 before sort: Brule River: Michigan, Wisconsin element 32 before sort: Menominee River: Michigan, Wisconsin element 33 before sort: Pigeon River: Minnesota, Ontario (Canada) element 34 before sort: Rainy River: Minnesota, Ontario (Canada) element 35 before sort: St. Croix River: Minnesota, Wisconsin element 36 before sort: St. Louis River: Minnesota, Wisconsin element 37 before sort: Mississippi River: Minnesota, Wisconsin, Iowa, Illinois, Missouri, Kentucky, Tennesse, Arkansas, Mississippi, Louisiana element 38 before sort: Pearl River: Mississippi, Louisiana element 39 before sort: Halls Stream: New Hampshire, Canada element 40 before sort: Salmon Falls River: New Hampshire, Maine element 41 before sort: Connecticut River: New Hampshire, Vermont element 42 before sort: Hudson River (lower part only): New Jersey, New York element 43 before sort: Arthur Kill: New Jersey, New York (tidal strait) element 44 before sort: Kill Van Kull: New Jersey, New York (tidal strait) element 45 before sort: Rio Grande: New Mexico, Texas, Tamaulipas (Mexico), Nuevo Leon (Mexico), Coahuila De Zaragoza (Mexico), Chihuahua (Mexico) element 46 before sort: Niagara River: New York, Ontario (Canada) element 47 before sort: St. Lawrence River: New York, Ontario (Canada) element 48 before sort: Delaware River: New York, Pennsylvania, New Jersey, Delaware element 49 before sort: Catawba River: North Carolina, South Carolina element 50 before sort: Red River of the North: North Dakota, Minnesota element 51 before sort: Great Miami River (mouth only): Ohio, Indiana element 52 before sort: Arkansas River: Oklahoma, Arkansas element 53 before sort: Palmer River: Rhode Island, Massachusetts element 54 before sort: Runnins River: Rhode Island, Massachusetts element 55 before sort: Savannah River: South Carolina, Georgia element 56 before sort: Big Sioux River: South Dakota, Iowa element 57 before sort: Bois de Sioux River: South Dakota, Minnesota, North Dakota element 58 before sort: Missouri River: South Dakota, Nebraska, Iowa, Missouri, Kansas element 59 before sort: Sabine River: Texas, Louisiana element 60 before sort: Red River (Mississippi watershed): Texas, Oklahoma, Arkansas element 61 before sort: Poultney River: Vermont, New York element 62 before sort: Blackwater River: Virginia, North Carolina element 63 before sort: Columbia River: Washington, Oregon ──────────────────────────────────────────────────────────────────────────────── element 1 after sort: ------------------- Rivers that form part of a state's (USA) border ----------------------------- element 2 after sort: ======================================================================================================================================== element 3 after sort: Arkansas River: Oklahoma, Arkansas element 4 after sort: Arthur Kill: New Jersey, New York (tidal strait) element 5 after sort: Big Sandy River: Kentucky, West Virginia element 6 after sort: Big Sioux River: South Dakota, Iowa element 7 after sort: Blackwater River: Virginia, North Carolina element 8 after sort: Bois de Sioux River: South Dakota, Minnesota, North Dakota element 9 after sort: Brule River: Michigan, Wisconsin element 10 after sort: Byram River: Connecticut, New York element 11 after sort: Catawba River: North Carolina, South Carolina element 12 after sort: Chattahoochee River: Alabama, Georgia element 13 after sort: Chattooga River: Georgia, South Carolina element 14 after sort: Colorado River: Arizona, Nevada, California, Baja California (Mexico) element 15 after sort: Columbia River: Washington, Oregon element 16 after sort: Connecticut River: New Hampshire, Vermont element 17 after sort: Delaware River: New York, Pennsylvania, New Jersey, Delaware element 18 after sort: Des Moines River: Iowa, Missouri element 19 after sort: Detroit River: Michigan, Ontario (Canada) element 20 after sort: Great Miami River (mouth only): Ohio, Indiana element 21 after sort: Halls Stream: New Hampshire, Canada element 22 after sort: Hudson River (lower part only): New Jersey, New York element 23 after sort: Kill Van Kull: New Jersey, New York (tidal strait) element 24 after sort: Menominee River: Michigan, Wisconsin element 25 after sort: Mississippi River: Minnesota, Wisconsin, Iowa, Illinois, Missouri, Kentucky, Tennesse, Arkansas, Mississippi, Louisiana element 26 after sort: Missouri River: South Dakota, Nebraska, Iowa, Missouri, Kansas element 27 after sort: Montreal River: Michigan (upper peninsula ), Wisconsin element 28 after sort: Monument Creek: Maine, New Brunswick (Canda) element 29 after sort: Niagara River: New York, Ontario (Canada) element 30 after sort: Ohio River: Illinois, Indiana, Ohio, Kentucky, West Virginia element 31 after sort: Palmer River: Rhode Island, Massachusetts element 32 after sort: Pawcatuck River: Connecticut, Rhode Island element 33 after sort: Pearl River: Mississippi, Louisiana element 34 after sort: Perdido River: Florida, Alabama element 35 after sort: Pigeon River: Minnesota, Ontario (Canada) element 36 after sort: Piscataqua River: Maine, New Hampshire element 37 after sort: Pocomoke River: Maryland, Virginia element 38 after sort: Poteau River: Arkansas, Oklahoma element 39 after sort: Potomac River: Maryland, Virginia, city of Washington (District of Columbia), West Virginia element 40 after sort: Poultney River: Vermont, New York element 41 after sort: Rainy River: Minnesota, Ontario (Canada) element 42 after sort: Red River (Mississippi watershed): Texas, Oklahoma, Arkansas element 43 after sort: Red River of the North: North Dakota, Minnesota element 44 after sort: Rio Grande: New Mexico, Texas, Tamaulipas (Mexico), Nuevo Leon (Mexico), Coahuila De Zaragoza (Mexico), Chihuahua (Mexico) element 45 after sort: Runnins River: Rhode Island, Massachusetts element 46 after sort: Sabine River: Texas, Louisiana element 47 after sort: Salmon Falls River: New Hampshire, Maine element 48 after sort: Savannah River: South Carolina, Georgia element 49 after sort: Snake River: Idaho, Washington, Oregon element 50 after sort: St. Clair River: Michigan, Ontario (Canada) element 51 after sort: St. Croix River: Maine, New Brunswick (Canda) element 52 after sort: St. Croix River: Minnesota, Wisconsin element 53 after sort: St. Francis River: Arkansas, Missouri element 54 after sort: St. Francis River: Maine, Quebec (Canada) element 55 after sort: St. John River: Maine, Quebec (Canada) element 56 after sort: St. Lawrence River: New York, Ontario (Canada) element 57 after sort: St. Louis River: Minnesota, Wisconsin element 58 after sort: St. Marys River: Florida, Georgia element 59 after sort: St. Marys River: Michigan, Ontario (Canada) element 60 after sort: Tennessee River: Kentucky, Tennessee, Mississippi, Alabama element 61 after sort: Tug Fork River: Kentucky, West Virginia, Virginia element 62 after sort: Tugaloo River: Georgia, South Carolina element 63 after sort: Wabash River: Illinois, Indiana ────────────────────────────────────────────────────────────────────────────────
[edit] Ruby
class Array
def quick_sort
return self if length <= 1
pivot = self[length / 2]
find_all { |i| i < pivot }.quick_sort +
find_all { |i| i == pivot } +
find_all { |i| i > pivot }.quick_sort
end
end
or
class Array
def quick_sort
return self if length <= 1
pivot = self[0]
less, greatereq = self[1..-1].partition { |x| x < pivot }
less.quick_sort +
[pivot] +
greatereq.quick_sort
end
end
[edit] Sather
class SORT{T < $IS_LT{T}} is
private afilter(a:ARRAY{T}, cmp:ROUT{T,T}:BOOL, p:T):ARRAY{T} is
filtered ::= #ARRAY{T};
loop v ::= a.elt!;
if cmp.call(v, p) then
filtered := filtered.append(|v|);
end;
end;
return filtered;
end;
private mlt(a, b:T):BOOL is return a < b; end;
private mgt(a, b:T):BOOL is return a > b; end;
quick_sort(inout a:ARRAY{T}) is
if a.size < 2 then return; end;
pivot ::= a.median;
left:ARRAY{T} := afilter(a, bind(mlt(_,_)), pivot);
right:ARRAY{T} := afilter(a, bind(mgt(_,_)), pivot);
quick_sort(inout left);
quick_sort(inout right);
res ::= #ARRAY{T};
res := res.append(left, |pivot|, right);
a := res;
end;
end;
class MAIN is
main is
a:ARRAY{INT} := |10, 9, 8, 7, 6, -10, 5, 4, 656, -11|;
b ::= a.copy;
SORT{INT}::quick_sort(inout a);
#OUT + a + "\n" + b.sort + "\n";
end;
end;
The ARRAY class has a builtin sorting method, which is quicksort (but under certain condition an insertion sort is used instead), exactly quicksort_range; this implementation is original.
[edit] Scala
I'll show a progression on genericity here.
First, a quick sort of a list of integers:
def quicksortInt(coll: List[Int]): List[Int] =
if (coll.isEmpty) {
coll
} else {
val (smaller, bigger) = coll.tail partition (_ < coll.head)
quicksortInt(smaller) ::: coll.head :: quicksortInt(bigger)
}
Next, a quick sort of a list of some type T, given a lessThan function:
def quicksortFunc[T](coll: List[T], lessThan: (T, T) => Boolean): List[T] =
if (coll.isEmpty) {
coll
} else {
val (smaller, bigger) = coll.tail partition (lessThan(_, coll.head))
quicksortFunc(smaller, lessThan) ::: coll.head :: quicksortFunc(bigger, lessThan)
}
To take advantage of known orderings, a quick sort of a list of some type T, for which exists an implicit (or explicit) Ordered[T]:
def quicksortOrd[T <% Ordered[T]](coll: List[T]): List[T] =
if (coll.isEmpty) {
coll
} else {
val (smaller, bigger) = coll.tail partition (_ < coll.head)
quicksortOrd(smaller) ::: coll.head :: quicksortOrd(bigger)
}
That last one could have worked with Ordering, but Ordering is Java, and doesn't have the less than operator. Ordered is Scala-specific, and provides it.
What hasn't changed in all these examples is that I'm ordering a list. It is possible to write a generic quicksort in Scala, which will order any kind of collection. To do so, however, requires that the type of the collection, itself, be made a parameter to the function. Let's see it below, and then remark upon it:
def quicksort
[T, CC[X] <: Seq[X] with SeqLike[X, CC[X]]] // My type parameters
(coll: CC[T]) // My explicit parameter
(implicit o: T => Ordered[T], cbf: CanBuildFrom[CC[T], T, CC[T]]) // My implicit parameters
: CC[T] = // My return type
if (coll.isEmpty) {
coll
} else {
val (smaller, bigger) = coll.tail partition (_ < coll.head)
quicksort(smaller) ++ (coll.head +: quicksort(bigger))
}
That will only work starting with Scala 2.8. The type of our collection is "CC", and, by providing CC[X] as a type parameter to TraversableLike, we ensure CC is capable of returing instances of type CC. Traversable is the base type of all collections, and TraversableLike is a trait which contains the implementation of most Traversable methods.
We need another parameter, though, which is a factory capable of building a CC collection. That is being passed implicitly, so callers to this method do not need to provide them, as the collection they are using should already provide such implicit. Because we need that implicit, then we need to ask for the "T => Ordered[T]" as well, as the "T <% Ordered[T]" which provides it cannot be used in conjunction with implicit parameters.
The body of the function is pretty much the same of the body for the list variant, but using "++" instead of list-specific methods "::" and ":::", and using "coll.companion" to build a collection out of one element.
We can also use pattern matching here - the first version of quicksortInt would look like that:
def quicksortInt(list: List[Int]): List[Int] = list match {
case head :: tail =>
val (smaller, bigger) = tail partition (_ < head)
quicksortInt(smaller) ::: head :: quicksortInt(bigger)
case list => list
}
[edit] Scheme
(define (split-by l p k)
(let loop ((low '())
(high '())
(l l))
(cond ((null? l)
(k low high))
((p (car l))
(loop low (cons (car l) high) (cdr l)))
(else
(loop (cons (car l) low) high (cdr l))))))
(define (quicksort l gt?)
(if (null? l)
'()
(split-by (cdr l)
(lambda (x) (gt? x (car l)))
(lambda (low high)
(append (quicksort low gt?)
(list (car l))
(quicksort high gt?))))))
(quicksort '(1 3 5 7 9 8 6 4 2) >)
With srfi-1:
(define (quicksort l gt?)
(if (null? l)
'()
(append (quicksort (filter (lambda (x) (gt? (car l) x)) (cdr l)) gt?)
(list (car l))
(quicksort (filter (lambda (x) (not (gt? (car l) x))) (cdr l)) gt?))))
(quicksort '(1 3 5 7 9 8 6 4 2) >)
[edit] Seed7
const proc: quickSort (inout array elemType: arr, in integer: left, in integer: right) is func
local
var elemType: compare_elem is elemType.value;
var integer: less_idx is 0;
var integer: greater_idx is 0;
var elemType: help is elemType.value;
begin
if right > left then
compare_elem := arr[right];
less_idx := pred(left);
greater_idx := right;
repeat
repeat
incr(less_idx);
until arr[less_idx] >= compare_elem;
repeat
decr(greater_idx);
until arr[greater_idx] <= compare_elem or greater_idx = left;
if less_idx < greater_idx then
help := arr[less_idx];
arr[less_idx] := arr[greater_idx];
arr[greater_idx] := help;
end if;
until less_idx >= greater_idx;
arr[right] := arr[less_idx];
arr[less_idx] := compare_elem;
quickSort(arr, left, pred(less_idx));
quickSort(arr, succ(less_idx), right);
end if;
end func;
const proc: quickSort (inout array elemType: arr) is func
begin
quickSort(arr, 1, length(arr));
end func;
Original source: [2]
[edit] SETL
In-place sort (looks much the same as the C version)
a := [2,5,8,7,0,9,1,3,6,4];
qsort(a);
print(a);
proc qsort(rw a);
if #a > 1 then
pivot := a(#a div 2 + 1);
l := 1;
r := #a;
(while l < r)
(while a(l) < pivot) l +:= 1; end;
(while a(r) > pivot) r -:= 1; end;
swap(a(l), a(r));
end;
qsort(a(1..l-1));
qsort(a(r+1..#a));
end if;
end proc;
proc swap(rw x, rw y);
[y,x] := [x,y];
end proc;
Copying sort using comprehensions:
a := [2,5,8,7,0,9,1,3,6,4];
print(qsort(a));
proc qsort(a);
if #a > 1 then
pivot := a(#a div 2 + 1);
a := qsort([x in a | x < pivot]) +
[x in a | x = pivot] +
qsort([x in a | x > pivot]);
end if;
return a;
end proc;
[edit] Standard ML
fun quicksort [] = []
| quicksort (x::xs) =
let
val (left, right) = List.partition (fn y => y<x) xs
in
quicksort left @ [x] @ quicksort right
end
[edit] Tcl
package require Tcl 8.5
proc quicksort {m} {
if {[llength $m] <= 1} {
return $m
}
set pivot [lindex $m 0]
set less [set equal [set greater [list]]]
foreach x $m {
lappend [expr {$x < $pivot ? "less" : $x > $pivot ? "greater" : "equal"}] $x
}
return [concat [quicksort $less] $equal [quicksort $greater]]
}
puts [quicksort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9
[edit] UnixPipes
split() {
(while read n ; do
test $1 -gt $n && echo $n > $2 || echo $n > $3
done)
}
qsort() {
(read p; test -n "$p" && (
lc="1.$1" ; gc="2.$1"
split $p >(qsort $lc >$lc) >(qsort $gc >$gc);
cat $lc <(echo $p) $gc
rm -f $lc $gc;
))
}
cat to.sort | qsort
[edit] Ursala
The distributing bipartition operator, *|, is useful for this algorithm. The pivot is chosen as the greater of the first two items, this being the least sophisticated method sufficient to ensure termination. The quicksort function is a higher order function parameterized by the relational predicate p, which can be chosen appropriately for the type of items in the list being sorted. This example demonstrates sorting a list of natural numbers.
#import nat
quicksort "p" = ~&itB^?a\~&a ^|WrlT/~& "p"*|^\~& "p"?hthPX/~&th ~&h
#cast %nL
example = quicksort(nleq) <694,1377,367,506,3712,381,1704,1580,475,1872>
output:
<367,381,475,506,694,1377,1580,1704,1872,3712>
[edit] V
[qsort
[joinparts [p [*l1] [*l2] : [*l1 p *l2]] view].
[split_on_first uncons [>] split].
[small?]
[]
[split_on_first [l1 l2 : [l1 qsort l2 qsort joinparts]] view i]
ifte].
The way of joy (using binrec)
[qsort
[small?] []
[uncons [>] split]
[[p [*l] [*g] : [*l p *g]] view]
binrec].
[edit] VBA
This is the "simple" quicksort, using temporary arrays.
Public Sub Quick(a() As Variant, last As Integer)
' quicksort a Variant array (1-based, numbers or strings)
Dim aLess() As Variant
Dim aEq() As Variant
Dim aGreater() As Variant
Dim pivot As Variant
Dim naLess As Integer
Dim naEq As Integer
Dim naGreater As Integer
If last > 1 Then
'choose pivot in the middle of the array
pivot = a(Int((last + 1) / 2))
'construct arrays
naLess = 0
naEq = 0
naGreater = 0
For Each el In a()
If el > pivot Then
naGreater = naGreater + 1
ReDim Preserve aGreater(1 To naGreater)
aGreater(naGreater) = el
ElseIf el < pivot Then
naLess = naLess + 1
ReDim Preserve aLess(1 To naLess)
aLess(naLess) = el
Else
naEq = naEq + 1
ReDim Preserve aEq(1 To naEq)
aEq(naEq) = el
End If
Next
'sort arrays "less" and "greater"
Quick aLess(), naLess
Quick aGreater(), naGreater
'concatenate
P = 1
For i = 1 To naLess
a(P) = aLess(i): P = P + 1
Next
For i = 1 To naEq
a(P) = aEq(i): P = P + 1
Next
For i = 1 To naGreater
a(P) = aGreater(i): P = P + 1
Next
End If
End Sub
Public Sub QuicksortTest()
Dim a(1 To 26) As Variant
'populate a with numbers in descending order, then sort
For i = 1 To 26: a(i) = 26 - i: Next
Quick a(), 26
For i = 1 To 26: Debug.Print a(i);: Next
Debug.Print
'now populate a with strings in descending order, then sort
For i = 1 To 26: a(i) = Chr$(Asc("z") + 1 - i) & "-stuff": Next
Quick a(), 26
For i = 1 To 26: Debug.Print a(i); " ";: Next
Debug.Print
End Sub
Output:
quicksorttest 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 a-stuff b-stuff c-stuff d-stuff e-stuff f-stuff g-stuff h-stuff i-stuff j-stuff k-stuff l-stuff m-stuff n-stuff o-stuff p-stuff q-stuff r-stuff s-stuff t-stuff u-stuff v-stuff w-stuff x-stuff y-stuff z-stuff
Note: the "quicksort in place"
[edit] XPL0
include c:\cxpl\codes; \intrinsic 'code' declarations
string 0; \use zero-terminated strings instead of MSb-terminated
proc QSort(Array, Num, Size); \Quicksort Array into ascending order
char Array; \address of array to sort
int Num, \number of elements in the array
Size; \size (in bytes) of each element
int I, J, Mid, Temp;
[I:= 0;
J:= Num-1;
Mid:= Array(J>>1);
while I <= J do
[while Array(I) < Mid do I:= I+1;
while Array(J) > Mid do J:= J-1;
if I <= J then
[Temp:= Array(I); Array(I):= Array(J); Array(J):= Temp;
I:= I+1;
J:= J-1;
];
];
if I < Num-1 then QSort(Array+I*Size, Num-I, Size); \recurse
if J > 0 then QSort(Array, J+1, Size);
]; \QSort
func StrLen(Str); \Return number of characters in an ASCIIZ string
char Str;
int I;
for I:= 0 to -1>>1-1 do
if Str(I) = 0 then return I;
char Str;
[Str:= "Pack my box with five dozen liquor jugs.";
QSort(Str, StrLen(Str), 1);
Text(0, Str); CrLf(0);
]
Output:
" .Pabcdeefghiiijklmnoooqrstuuvwxyz"
Categories:
- Programming Tasks
- Sorting Algorithms
- Recursion
- WikipediaSourced
- ACL2
- ActionScript
- Ada
- ALGOL 68
- APL
- AWK
- AutoHotkey
- BASIC
- BCPL
- C
- C++
- C sharp
- Clojure
- CoffeeScript
- Common Lisp
- Curry
- D
- Dart
- E
- Erlang
- F Sharp
- Factor
- Fexl
- Forth
- Fortran
- Fortran examples needing attention
- Examples needing attention
- Go
- Haskell
- IDL
- Icon
- Unicon
- Io
- J
- Java
- JavaScript
- Joy
- K
- Logo
- Logtalk
- Lua
- Lucid
- M4
- Mathematica
- MATLAB
- MAXScript
- Modula-2
- Modula-3
- Nemerle
- NetRexx
- Nial
- Nimrod
- OCaml
- Octave
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- PL/I
- PowerShell
- Prolog
- PureBasic
- Python
- Qi
- R
- REXX
- Ruby
- Sather
- Scala
- Scheme
- Seed7
- SETL
- Standard ML
- Tcl
- UnixPipes
- Ursala
- V
- GUISS/Omit
- VBA
- XPL0
