Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted

Inline

Revision as of 04:33, 25 October 2009

In this task, the goal is to sort an array (or list) of 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. 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
    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. An optimally selected pivot will result in partitions of equal length (or lengths differing by 1). The partitioning step may be thought of as a special sorting step using the attribute x ≤ pivot as the sort key, with possible values <true, false>. Quicksort's worst case time is O(n²),e.g., for a completely sorted set with the pivot chosen as the first or last element, 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.

Quicksort may be thought of as being situated at one end of the spectrum of divide-conquer algorithms, with Mergesort at the other end. In Quicksort, which some have called a conquer-divide algorithm, most of the work is done in the partitioning and recursive calls. The subsequent reassembly of the sorted segments involves trivial effort. In Mergesort, in contrast, the partitioning is done in a trivial way by splitting the input array in half. In Quicksort, every element in the first partition is less or equal to every element in the second partition. It is this property that makes the merge phase of Quicksort so trivial that it does not even need mentioning.

ActionScript

Works with: ActionScript version 3

The functional programming way <lang actionscript>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; })));

}</lang>

The faster way <lang actionscript>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));

}</lang>

Ada

This example is implemented as a generic procedure. The procedure specification is: <lang ada>

-----------------------------------------------------------------------
-- 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);</lang>

The procedure body deals with any discrete index type, either an integer type or an enumerated type. <lang ada>

-----------------------------------------------------------------------
-- 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);
      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;</lang>

An example of how this procedure may be used is: <lang ada>

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;</lang>

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

APL

Works with: Dyalog APL

Translation of: J

      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).

AutoHotkey

translated from python example <lang AutoHotkey> 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

} </lang>

C

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

}</lang>

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). <lang cpp>

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

} </lang>

A simpler version of the above that just uses the first element as the pivot and only does one "partition". <lang cpp>

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

} </lang>

Clojure

A very Haskell-like solution using list comprehensions and lazy evaluation.

(defn qsort [L]
  (if (nil? 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))))))

Common Lisp

The functional programming way

<lang lisp>(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))))))</lang>

In-place non-functional

<lang lisp>(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))</lang>

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: <lang d>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));

} </lang>

E

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

}</lang>

Erlang

like haskell <lang erlang>qsort([]) -> []; qsort([X|Xs]) ->

  qsort([ Y || Y <- Xs, Y < X]) ++ [X] ++ qsort([ Y || Y <- Xs, Y >= X]).</lang>

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 ;

Fortran

Works with: Fortran version 90 and later

<lang 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</lang>

Haskell

The famous two-liner, reflecting the underlying algorithm directly: <lang haskell> qsort [] = [] qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x] </lang> A more efficient version, doing only one comparison per element: <lang haskell> import Data.List

qsort [] = [] qsort (x:xs) = qsort ys ++ x : qsort zs where (ys, zs) = partition (< x) xs </lang>

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

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

<lang 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.

)</lang>

See the Quicksort essay in the J Wiki for additional explanations and examples.

Java

Works with: Java version 1.5+

Translation of: Python

<lang java5>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;

}</lang>

JavaScript

<lang javascript>function sort(a,less) {

 function swap(i,j) { var t=a[i]; a[i]=a[j]; a[j]=t }
 function qs(l,r) {
   if (l<r) {
     var pivot = a[(l+r)>>1];
     var l2=l, r2=r;
     do {
       while (less(a[l2], pivot) ++l2;
       while (less(pivot, a[r2]) --r2;
       if (l2 <= r2) swap(l2++, r2--);
     } while (l2 <= r2);
     qs(l, r2);
     qs(l2, r);
   }
 }
 qs(0, a.length-1);
 return a;

}</lang>

The functional programming way

<lang javascript>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());

}</lang>

Joy

<lang joy> DEFINE qsort ==

  [small]
  []
  [uncons [>] split]
  [swapd cons concat]
  binrec .

</lang>

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] </lang> <lang logo>

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 </lang>

Lucid

[1]

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

M4

<lang 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)) </lang>

Output:

(1,1,3,4,5,9)

MATLAB

<lang Matlab> 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 return

N=256*256; v=rand(N,1); tic,u=quicksort(v); toc issorted(u) </lang>

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

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

OCaml

<lang 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]</lang>

Octave

Translation of: MATLAB

(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)

<lang octave>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</lang>

Perl

<lang perl> sub quick_sort {

  $arr = shift;
  local $less = [];
  local $pivot_list = [];
  local $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";</lang>

Output:

-31 0 1 2 4 65 83 99 782

In a more functional style: <lang perl> sub quicksort { @_ <= 1 ? @_ : do { my $pivot = pop; quicksort( grep {$_ <= $pivot} @_ ), $pivot, quicksort( grep {$_ > $pivot} @_ ) } } </lang> Accepting a sort function: <lang perl> sub quicksort (&@) { my $c = shift; @_ <= 1 ? @_ : do { local ($a, $b) = splice @_, rand @_, 1; my (@low, @high); for $b (@_) { $c->() <= 0 ? $high[@high] : $low[@low] = $b } quicksort( $c => @low ), $a, quicksort( $c => @high ) } }

print join ', ' => quicksort { $a <=> $b } 3, 5, 7, 1, -6, 12, 2; </lang>

PL/I

<lang 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);</lang>

Prolog

<lang prolog>qsort( [], [] ). qsort( [X], [X] ). qsort( [H|U], S ) :- splitBy(H, U, L, R), qsort(L, SL), qsort(R, SR), combine(H, SL, SR, S).

% splitBy( H, U, LS, RS ) % True if LS = { L in U | L <= H }; RS = { R in U | R > H } splitBy( H, [], LS, RS). 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).

% combine( H, L, R, S ) % True if S is L ++ [H] ++ R (in Haskell notation) combine( H, L, R, S ) :- append(L, [H|R], S).</lang>

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)

</lang>

In a Haskell fashion -- <lang python> 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

</lang>

More readable, but still using list comprehensions: <lang python> 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)

</lang>

R

Translation of: Octave

<lang 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)</lang>

Ruby

<lang ruby>class Array

 def quick_sort
   return self if length <= 1
   pivot = self[length / 2]
   return (find_all { |i| i <  pivot }).quick_sort +
          (find_all { |i| i == pivot }) +
          (find_all { |i| i >  pivot }).quick_sort
 end

end</lang>

Scheme

<lang scheme>(define (split-by l p)

 (let loop ((low (list)) (high (list)) (l l))
   (if (null? l)
       (cons low high)
       (if (p (car l))
           (loop low (cons (car l) high) (cdr l))
           (loop (cons (car l) low) high (cdr l))))))

(define (quicksort l gt?)

 (let q ((l l))
   (if (null? l)
       l
       (let ((s (split-by (cdr l) (lambda (x) (gt? x (car l))))))
         (append (q (car s)) (list (car l)) (q (cdr s)))))))
(quicksort (list 1 3 5 7 9 8 6 4 2) >)</lang>

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]

SETL

In-place sort (looks much the same as the C version) <lang SETL>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;</lang>

Copying sort using comprehensions:

<lang SETL>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;</lang>

Standard ML

<lang ocaml>fun quicksort [] = []

 | quicksort (x::xs) =
   let 
       val (left, right) = List.partition (fn y => y<x) xs
   in
       quicksort left @ [x] @ quicksort right
   end</lang>

Tcl

<lang 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</lang>

UnixPipes

Works with: Zsh

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

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> </lang> output:

<367,381,475,506,694,1377,1580,1704,1872,3712>

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].