Sorting algorithms/Quicksort

Sorting algorithms/Quicksort
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.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

In this task, the goal is to sort an array of elements using the Quicksort algorithm. The elements must have a total 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.

C

void quick(int *left, int *right)
{
  if (right > left) {
    int pivot = left[(right-left)/2];
    int *r = right, *l = left;
    do {
      while (*l < pivot) l++;
      while (*r > pivot) r--;
      if (l <= r) {
        int t = *l;
        *l++ = *r;
        *r-- = t;
      }
    } while (l <= r);
    quick(left, r);
    quick(l, right);
  }
}
void sort(int *array, int length)
{
  quick(array, array+length-1);
}

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 ;

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

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