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 (or list) 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. The algorithm goes like this (from the wiki):

function quicksort(array)
    var list lessOrEqual, greater
    if length(array) ≤ 1  
        return array  
    select a pivot value pivot from array
    for each x in array
        if x ≤ pivot then add x to lessOrEqual
        if x > pivot then add x to greater
    return concatenate(quicksort(lessOrEqual), quicksort(greater))

The "pivot" separates the dataset into two groups: those that are less than or equal to the value at the pivot and those that are greater than the pivot. The Quicksort's worst case time is O(n^2) for a completely sorted set, but otherwise it is O(n * log n). Its average time is slightly faster than that of the merge sort in most cases, even though they are both O(n * log n) sorts.

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 > 2 then
      Pivot_Index := Index_Type'Val((Index_Type'Pos(Item'Last) + 1 + 
                                    Index_Type'Pos(Item'First)) / 2);
      Pivot_Value := Item(Pivot_Index);
      loop
         Left  := Item'First;
         Right := Item'Last;
         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..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;

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);
}

D

An implementation much similar to the C one is possible too, this is slower and simpler, derived from the Python one. This is a function template:

import std.stdio;

T[] quickSort(T)(T[] items) {
    T[] less, more;
    if (items.length <= 1)
        return items;
    else {
        T pivot = items[0];
        foreach(el; items[1 .. $])
            if (el < pivot)
                less ~= el;
            else
                more ~= el;
        return quickSort(less) ~ pivot ~ quickSort(more);
    }
}

void main() {
    auto a1 = [4, 65, 2, -31, 0, 99, 2, 83, 782, 1];
    writefln(quickSort(a1));
    auto a2 = [4.0,65.0,2.0,-31.0,0.0,99.0,2.0,83.0,782.0,1.0];
    writefln(quickSort(a2));
}

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 ;

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

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

J

sel=: 1 : 'x # ['

quicksort=: 3 : 0
 if. 1 >: #y do. y else. (quicksort y <sel e),(y =sel e),quicksort y >sel e=.y{~?#y end.
)

To actually sort data in J, it is more convenient and more efficient to use /:~ .

Joy

DEFINE qsort ==
   [small]
   []
   [uncons [>] split]
   [[swap] dip cons concat]
   binrec .

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

Perl

sub quick_sort {
  $arr = shift;
  $less = [];
  $pivot_list = [];
  $more = [];
  if ($#{$arr} <= 0) {
    return $arr;
  } else {
    $pivot = $arr->[0];
    foreach my $i (@{$arr}) {
      if ($i < $pivot) {
        push @{$less}, $i;
      } elsif ($i > $pivot) {
        push @{$more}, $i;
      } else {
        push @{$pivot_list}, $i;
      }
    }
    $less = quick_sort($less);
    $more = quick_sort($more);
    return [@{$less}, @{$pivot_list}, @{$more}];
  }
}

print join(' ', @{quick_sort([4, 65, 2, -31, 0, 99, 83, 782, 1])}), "\n";

Output:

-31 0 1 2 4 65 83 99 782

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):
    if len(L) <= 1: return L
    pivot, L = L[0], L[1:]
    return qsort([y for y in L if y <= pivot]) + [y for y in L if y == pivot] + \
           qsort([y for y in L if y >  pivot])

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: [1]