Quicksort

From CodeCodex

Related content:

Implementations[edit]

Pseudocode[edit]

function quicksort(array)
    var list less, equal, greater
    if length(array) ≤ 1  
        return array  
    select a pivot value pivot from array
    for each x in array
        if x < pivot then append x to less
        if x = pivot then append x to equal
        if x > pivot then append x to greater
    return concatenate(quicksort(less), equal, quicksort(greater))

It's about time somoene wrote about this.

AppleScript[edit]

This is a straightforward implementation. It is certainly possible to come up with a more efficient one, but it will probably not be as clear as this one:

 on sort( array, left, right )
     set i to left
     set j to right
     set v to item ( ( left + right ) div 2 ) of array -- pivot
     repeat while ( j > i )
         repeat while ( item i of array < v )
             set i to i + 1
         end repeat
         repeat while ( item j of array > v )
             set j to j - 1
         end repeat
         if ( not i > j ) then
             tell array to set { item i, item j } to { item j, item i } -- swap
             set i to i + 1
             set j to j - 1
         end if
     end repeat 
     if ( left  < j ) then sort( array, left, j  )
     if ( right > i ) then sort( array, i, right )
 end sort

Hey, you're the goto exerpt. Thanks for hanging out here.

AutoIt v3[edit]

This is a straightforward implementation based on the AppleScript example. It is certainly possible to come up with a more efficient one, but it will probably not be as clear as this one:

  Func sort( ByRef $array, $left, $right )
    $i = $left
    $j = $right
    $v = $array[Int( ( $left + $right ) / 2)]
    While ( $j > $i )
        While ($array[$i] < $v )
            $i = $i + 1
        WEnd
        While ( $array[$j] > $v )
            $j = $j - 1
        WEnd
        If ( NOT ($i > $j) ) then
            swap($array[$i], $array[$j])
            $i = $i + 1
            $j = $j - 1
        EndIf
    WEnd
    if ( $left  < $j ) then sort( $array, $left, $j  )
    if ( $right > $i ) then sort( $array, $i, $right )
  EndFunc

C[edit]

The function qsort() in the C standard library can be used to sort arrays of any data type. Its use should be preferred in real code. The following implementations serve as an academic exercise.

The following implementation works with any data type, given its size and a function that compares it. This is similar to what ISO/POSIX compliant C standard libraries provide:

#include <stdlib.h>
#include <stdio.h>

static void swap(void *x, void *y, size_t l) {
   char *a = x, *b = y, c;
   while(l--) {
      c = *a;
      *a++ = *b;
      *b++ = c;
   }
}

static void sort(char *array, size_t size, int (*cmp)(void*,void*), int begin, int end) {
   if (end > begin) {
      void *pivot = array + begin;
      int l = begin + size;
      int r = end;
      while(l < r) {
         if (cmp(array+l,pivot) <= 0) {
            l += size;
         } else {
            r -= size;
            swap(array+l, array+r, size);
         }
      }
      l -= size;
      swap(array+begin, array+l, size);
      sort(array, size, cmp, begin, l);
      sort(array, size, cmp, r, end);
   }
}

void qsort(void *array, size_t nitems, size_t size, int (*cmp)(void*,void*)) {
   sort(array, size, cmp, 0, (nitems-1)*size);
}

typedef int type;

int type_cmp(void *a, void *b){ return (*(type*)a)-(*(type*)b); }

main(){ /* simple test case for type=int */
  int num_list[]={5,4,3,2,1};
  int len=sizeof(num_list)/sizeof(type);
  char *sep="";
  int i;
  qsort(num_list,len,sizeof(type),type_cmp);
  printf("sorted_num_list={");
  for(i=0; i<len; i++){
    printf("%s%d",sep,num_list[i]);
    sep=", ";
  }
  printf("};\n");
}

Result:

sorted_num_list={2, 3, 4, 5, 1};

Here's yet another version with various other improvements:

/*****   macros create functional code   *****/
#define pivot_index() (begin+(end-begin)/2)
#define swap(a,b,t) ((t)=(a),(a)=(b),(b)=(t))

void sort(int array[], int begin, int end) {
   /*** Use of static here will reduce memory footprint, but will make it thread-unsafe ***/
   static int pivot;
   static int t;     /* temporary variable for swap */
   if (end > begin) {
      int l = begin + 1;
      int r = end;
      swap(array[begin], array[pivot_index()], t); /*** choose arbitrary pivot ***/
      pivot = array[begin];
      while(l < r) {
         if (array[l] <= pivot) {
            l++;
         } else {
            while(l < --r && array[r] >= pivot) /*** skip superfluous swaps ***/
               ;
            swap(array[l], array[r], t); 
         }
      }
      l--;
      swap(array[begin], array[l], t);
      sort(array, begin, l);
      sort(array, r, end);
   }
}

#undef swap
#undef pivot_index

An alternate simple C quicksort. The first C implementation above does not sort the list properly if the initial input is a reverse sorted list, or any time in which the pivot turns out be the largest element in the list. Here is another sample quick sort implementation that does address these issues. Note that the swaps are done inline in this implementation. They may be replaced with a swap function as in the above examples.

void qsort(int arr[], int beg, int end) 
{
   int temp;
   if (end > beg) 
   {
      int piv = arr[beg], l = beg + 1, r = end;
      while (l < r) 
      {
         if (arr[l] <= piv) 
            l++;
	 else if(arr[r] >= piv)
	    r--;
         else 
         {
	    temp = arr[l];
	    arr[l] = arr[r];
  	    arr[r] = temp;
	 }
      }
      if(arr[l] < piv)
      {
         temp = arr[l];
	 arr[l] = arr[beg];
	 arr[beg] = temp;
	 l--;
      } 
      else
      {
         l--;
	 temp = arr[l];
	 arr[l] = arr[beg];
	 arr[beg] = temp;
      }
      qsort(arr, beg, l);
      qsort(arr, r, end);
   }
}

This sorts an array of integers using quicksort with in-place partition.

 void quicksort(int x[], int first, int last) {
     int pivIndex = 0;
     if(first < last) {
         pivIndex = partition(x,first, last);
         quicksort(x,first,(pivIndex-1));
         quicksort(x,(pivIndex+1),last);
     }
 }

 int partition(int y[], int f, int l) {
     int up,down,temp;
     int piv = y[f];
     up = f;
     down = l;
     goto partLS;
     do { 
         temp = y[up];
         y[up] = y[down];
         y[down] = temp;
     partLS:
         while (y[up] <= piv && up < l) {
             up++;
         }
         while (y[down] > piv  && down > f ) {
             down--;
         }
     } while (down > up);
     y[f] = y[down];
     y[down] = piv;
     return down;
 }


The following sample of C code can be compiled to sort a vector of strings (defined as char *list[ ]), integers, doubles, etc. This piece of code implements a mixed iterative-recursive strategy that avoids out of stack risks even in worst case. It runs faster than the standard C lib function qsort(), expecially when used with partially sorted arrays (compiled with free Borland bcc32 and tested with 1 million strings vector).

/********** QuickSort(): sorts the vector 'list[]' **********/

/**** Compile QuickSort for strings ****/
#define QS_TYPE char*
#define QS_COMPARE(a,b) (strcmp((a),(b)))

/**** Compile QuickSort for integers ****/
//#define QS_TYPE int
//#define QS_COMPARE(a,b) ((a)-(b))

/**** Compile QuickSort for doubles, sort list in inverted order ****/
//#define QS_TYPE double
//#define QS_COMPARE(a,b) ((b)-(a))

void QuickSort(QS_TYPE list[], int beg, int end)
{
    QS_TYPE piv; QS_TYPE tmp;
    
    int  l,r,p;

    while (beg<end)    // This while loop will avoid the second recursive call
    {
        l = beg; p = (beg+end)/2; r = end;

        piv = list[p];

        while (1)
        {
            while ( (l<=r) && ( QS_COMPARE(list[l],piv) <= 0 ) ) l++;
            while ( (l<=r) && ( QS_COMPARE(list[r],piv)  > 0 ) ) r--;

            if (l>r) break;

            tmp=list[l]; list[l]=list[r]; list[r]=tmp;

            if (p==r) p=l;
            
            l++; r--;
        }

        list[p]=list[r]; list[r]=piv;
        r--;

        // Recursion on the shorter side & loop (with new indexes) on the longer
        if ((r-beg)<(end-l))   
        {
            QuickSort(list, beg, r);
            beg=l;
        }
        else
        {
            QuickSort(list, l, end);
            end=r;
        }
    }   
}

C++[edit]

This is a generic, STL-based version of quicksort.

#include <functional>
#include <algorithm>
#include <iterator>

template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
  if( first != last ) {
    BidirectionalIterator left  = first;
    BidirectionalIterator right = last;
    BidirectionalIterator pivot = left++;

    while( left != right ) {
      if( cmp( *left, *pivot ) ) {
         ++left;
      } else {
         while( (left != right) && cmp( *pivot, *right ) )
           --right;
         std::iter_swap( left, right );
      }
    }

    --left;
    std::iter_swap( first, left );

    quick_sort( first, left, cmp );
    quick_sort( right, last, cmp );
  }
}

template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
  quick_sort( first, last,
    std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
  );
}

Here's a shorter version than the one in the core implementations section which takes advantage of the standard library's partition() function:

#include <algorithm>
#include <iterator>
#include <functional>

template <typename T>
void sort(T begin, T end) {
    if (begin != end) {
        T middle = partition (begin, end, bind2nd(
                less<iterator_traits<T>::value_type>(), *begin));
        sort (begin, middle);
        sort (max(begin + 1, middle), end);
    }
}

C#[edit]

The following C# implementation uses a random pivot and is limited to integer arrays; for other value types, replace all instances of int[] with the appropriate type (for example, decimal[]). For object[] comparison, create a delegate to your custom object compare function and pass it as an added parameter to both methods:

class Quicksort {
	private void swap(int[] Array, int Left, int Right) {
                int temp = Array[Right];
                Array[Right] = Array[Left];
                Array[Left] = temp;
        }

	public void sort(int[] Array, int Left, int Right) {
		int LHold = Left;
		int RHold = Right;
		Random ObjRan = new Random();
		int    Pivot  = ObjRan.Next(Left,Right);
		swap(Array,Pivot,Left);
		Pivot = Left;
		Left++;

		while (Right >= Left) {
			if (Array[Left] >= Array[Pivot]
			    && Array[Right] < Array[Pivot])
				swap(Array, Left, Right);
			else if (Array[Left] >= Array[Pivot])
				Right--;
			else if (Array[Right] < Array[Pivot])
				Left++;
			else {
				Right--;
				Left++;
		}	}	
		swap(Array, Pivot, Right);
		Pivot = Right;	
		if (Pivot > LHold)
			sort(Array, LHold,   Pivot);
		if (RHold > Pivot+1)
			sort(Array, Pivot+1, RHold);
}	}

Example of QuickSort using delegates. Pass the array of objects in the constructor of the class. For comparing other type of objects rewrite your own compare function instead of CompareInt.

class QuickSort {
	private delegate int CmpOp(object Left, object Right);
	private void swap(object[] Array, int Left, int Right, CmpOp Cmp) {
			object tempObj = Array[Left];
			Array[Left]    = Array[Right];
			Array[Right]   = tempObj;
	}
	private int CmpInt(object Left, object Right) {
		if ((int) Left < (int) Right)
			return -1;
		else 
			return -2;
	}
	public QuickSort(object[] Array) {
		CmpOp Cmp = new CmpOp(CmpInt);
		Sort(Array, 0, Array.Length-1, Cmp);			
	}
	private void Sort(object[] Array, int Left, int Right, CmpOp Cmp) {
		int LHold = Left;
		int RHold = Right;
		Random ObjRan = new Random();
		int Pivot = ObjRan.Next(Left,Right);
		swap(Array, Pivot, Left, Cmp);
		Pivot = Left;
		Left++;

		while (Right >= Left) {
			if (Cmp(Array[Left], Array[Pivot])!= -1
			    && Cmp(Array[Right], ArrObj[Pivot])== -1)
				swap(Array, Left, Right, Cmp);
			else if (Cmp(Array[Left], Array[Pivot]) != -1)
				Right--;
			else if (Cmp(Array[Right],Array[Pivot]) == -1)
				Left++;
			else {
				Right--;
				Left++;
		}       }	
		swap(Array, Pivot, Right, Cmp);
		Pivot = Right;

		if (Pivot > LHold)
			Sort(Array, LHold,  Pivot, Cmp);
		if (RHold > Pivot+1)
			Sort(Array, Pivot+1,RHold, Cmp);
}	}

The following is an example of using QuickSort to sort an array of strings.

class Quicksort {
	private void quickSwap(string[] Array, int Left, int Right) 
	{
		string Temp = Array[Right];
		Array[Right] = Array[Left];
		Array[Left] = Temp;
	}

	public void quickSort(string[] Array, int Left, int Right) 
	{
		int LHold = Left;
		int RHold = Right;
		Random ObjRan = new Random();
		int Pivot = ObjRan.Next(Left, Right);
		quickSwap(Array, Pivot, Left);
		Pivot = Left;
		Left++;

		while (Right >= Left) 
		{
			int cmpLeftVal = Array[Left].CompareTo(Array[Pivot]);
			int cmpRightVal = Array[Right].CompareTo(Array[Pivot]);

			if ((cmpLeftVal >= 0) && (cmpRightVal < 0))
			{
				quickSwap(Array, Left, Right);
			}
			else 
			{
				if (cmpLeftVal >= 0)
				{
					Right--;
				}
				else 
				{
					if (cmpRightVal < 0)
					{
						Left++;
					}
					else 
					{
						Right--;
						Left++;
					}
				}
			}
		}       
		quickSwap(Array, Pivot, Right);
		Pivot = Right;  
		if (Pivot > LHold)
		{
			quickSort(Array, LHold, Pivot);
		}
		if (RHold > Pivot + 1)
		{
			quickSort(Array, Pivot + 1, RHold);
		}
	}
}

Common Lisp[edit]

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

D[edit]

void sort(T)(T arr) {
    if (arr.length > 1) {
        quickSort(arr.ptr, arr.ptr + (arr.length - 1));
    }
}

void quickSort(T)(T *left, T *right) {
    if (right > left) {
        T pivot = left[(right - left) / 2];
        T* r = right, l = left;
        do {
            while (*l < pivot) l++;
            while (*r > pivot) r--;
            if (l <= r) swap(*l++, *r--);
        } while (l <= r);
        quickSort(left, r);
        quickSort(l, right);
    }
}

Delphi[edit]

This example sorts strings using quicksort.

Note: This can be considered bad code, as it is very slow.

procedure QuickSort(const AList: TStrings; const AStart, AEnd: Integer);
  procedure Swap(const AIdx1, AIdx2: Integer);
  var
    Tmp: string;
  begin
    Tmp := AList[AIdx1];
    AList[AIdx1] := AList[AIdx2];
    AList[AIdx2] := Tmp;
  end;

var
  Left: Integer;
  Pivot: string;
  Right: Integer;
begin
  if AStart >= AEnd then
    Exit;
  Pivot := AList[AStart];
  Left := AStart + 1;
  Right := AEnd;
  while Left < Right do
    begin
      if AList[Left] < Pivot then
        Inc(Left)
      else
        begin
          Swap(Left, Right);
          Dec(Right);
        end;
    end;
  Dec(Left);
  Swap(Left, AStart);
  Dec(Left);
  QuickSort(AList, AStart, Left);
  QuickSort(AList, Right, AEnd);
end;

This implementation sorts an array of integers.

procedure QSort(var A: array of Integer);
  procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
  var Lo, Hi, Mid, T: Integer;
  begin
    Lo := iLo;
    Hi := iHi;
    Mid := A[(Lo + Hi) div 2];
    repeat
      while A[Lo] < Mid do
        Inc(Lo);
      while A[Hi] > Mid do
        Dec(Hi);
      if Lo <= Hi then begin
        T := A[Lo];
        A[Lo] := A[Hi];
        A[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > iLo then
      QuickSort(A, iLo, Hi);
    if Lo < iHi then
      QuickSort(A, Lo, iHi);
  end;
begin
  QuickSort(A, Low(A), High(A));
end;

This slightly modified implementation sorts an array of records. This is approximately 8x quicker than the previous one. Note: this is QuickSort only, more speedup can be gain with handling trivial case (comparing two values), or implementing Bubble or Shell sort on small ranges.

type
  TCustomRecord = record
    Key: WideString;
    foo1:Int64;
    foo2:TDatetime;
    foo3:Extended;
  end;
  TCustomArray = array of TCustomRecord;

procedure QuickSort(var A: TCustomArray; L, R: Integer; var tmp: TCustomRecord);
var
  OrigL,
  OrigR: Integer;
  Pivot: WideString;
  GoodPivot,
  SortPartitions: Boolean;
begin
  if L<R then begin
    Pivot:=A[L+Random(R-L)].Key;
    OrigL:=L; //saving original bounds
    OrigR:=R;
    repeat
      L:=OrigL; //restoring original bounds if we
      R:=OrigR; //have chosen a bad pivot value
      while L<R do begin
        while (L<R) and (A[L].Key<Pivot) do Inc(L);
        while (L<R) and (A[R].Key>=Pivot) do Dec(R);
        if (L<R) then begin
          tmp:=A[L];
          A[L]:=A[R];
          A[R]:=tmp;
          Dec(R);
          Inc(L);
        end;
      end;
      if A[L].Key>=Pivot then Dec(L);                            //has we managed to choose
      GoodPivot:=L>=OrigL;                                       //a good pivot value?
      SortPartitions:=True;                                      //if so, then sort on
      if not GoodPivot then begin                                //bad luck, the pivot is the smallest one in our range
        GoodPivot:=True;                                         //let's presume that all the values are equal to pivot
        SortPartitions:=False;                                   //then no need to sort it
        for R := OrigL to OrigR do if A[R].Key<>Pivot then begin //we have at least one different value than our pivot
          Pivot:=A[R].Key;                                       //so this will be our new pivot
          GoodPivot:=False;                                      //we have to start again sorting this range
          Break;
        end;
      end;
    until GoodPivot;
    if SortPartitions then begin
      QuickSort(A, OrigL, L, tmp);
      QuickSort(A, L+1, OrigR, tmp);
    end;
  end;
end;

Erlang[edit]

The following Erlang code sorts lists of items of any type.

qsort([]) -> [];
qsort([Pivot|Rest]) ->
    qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).

Haskell[edit]

The Haskell code in the core implementations section is almost self explanatory but can suffer from inefficiencies because it crawls through the list "rest" twice, once for each list comprehension. A smart implementation can perform optimizations to prevent this inefficiency, but these are not required by the language. The following implementation does not have the aforementioned inefficiency, as it uses a partition function that ensures that we only traverse `xs' once:

partition:: (Ord a) => [a] -> a -> ([a],[a]) -> ([a],[a])

partition [] _ part = part -- base case

partition (x:xs) pivot (lesseq,greater) = 
  if x<= pivot then partition xs pivot (x:lesseq,greater)
               else partition xs pivot (lesseq,x:greater)

sort:: (Ord a) => [a] -> [a]
sort [] = []
sort (x:xs) = sort lesseq ++ [x] ++ sort greater where
  (lesseq,greater) = partition xs x ([],[])

Another version:

quicksort :: Ord a => [a] -> [a]
quicksort []           = []
quicksort (pivot:tail) = quicksort less ++ [pivot] ++ quicksort greater
   where less    = [y | y <- tail, y < pivot]
         greater = [y | y <- tail, y >= pivot]

An even shorter version:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

J[edit]

The J example in the core implementations section is extremely terse and difficult to understand. This implementation, from the J Dictionary, is less obtuse:

sel=: adverb def 'x. # ['

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

Java[edit]

With the advent of J2SE 5.0 you can use parameterized types to avoid passing the Comparator used above.

The following implementations use Generics to

The following Java implementation uses a randomly selected pivot. It sorts objects that implement the Comparator interface using the natural ordering of their compareTo method.

 import java.util.Arrays;
 import java.util.Random;
 
 public class QuickSort {
     public static final Random RND = new Random();
 
     private static void swap(Object[] array, int i, int j) {
         Object tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
     }
 
     private static <E extends Comparable<? super E>> int partition(E[] array, int begin, int end) {
         int index = begin + RND.nextInt(end - begin + 1);
         E pivot = array[index];
         swap(array, index, end);
         for (int i = index = begin; i < end; ++i) {
             if (array[i].compareTo(pivot) <= 0) {
                 swap(array, index++, i);
             }
         }
         swap(array, index, end);
         return (index);
     }
 
     private static <E extends Comparable<? super E>> void qsort(E[] array, int begin, int end) {
         if (end > begin) {
             int index = partition(array, begin, end);
             qsort(array, begin, index - 1);
             qsort(array, index + 1, end);
         }
     }
 
     public static <E extends Comparable<? super E>> void sort(E[] array) {
         qsort(array, 0, array.length - 1);
     }
 
     // Example uses
     public static void main(String[] args) {
         Integer[] l1 = { 5, 1024, 1, 88, 0, 1024 };
         System.out.println("l1  start:" + Arrays.toString(l1));
         QuickSort.sort(l1);
         System.out.println("l1 sorted:" + Arrays.toString(l1));
 
         String[] l2 = { "gamma", "beta", "alpha", "zoolander" };
         System.out.println("l2  start:" + Arrays.toString(l2));
         QuickSort.sort(l2);
         System.out.println("l2 sorted:" + Arrays.toString(l2));
     }
 }

Analogously to the Erlang solution above, a user-supplied {{Javadoc:SE|java/util|Comparator}} determines the partial ordering of array elements:

 import java.util.Comparator;
 import java.util.Random;
 
 public class Quicksort {
     public static final Random RND = new Random();	
     private static void swap(Object[] array, int i, int j) {
         Object tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
     }
     private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) {
         int index = begin + RND.nextInt(end - begin + 1);
         Object pivot = array[index];
         swap(array, index, end);	
         for (int i = index = begin; i < end; ++ i) {
             if (cmp.compare(array[i], pivot) <= 0) {
                 swap(array, index++, i);
             }
         }
         swap(array, index, end);	
         return (index);
     }
     private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
         if (end > begin) {
             int index = partition(array, begin, end, cmp);
             qsort(array, begin, index - 1, cmp);
             qsort(array, index + 1,  end,  cmp);
         }
     }
     public static <E> void sort(E[] array, Comparator<? super E> cmp) {
         qsort(array, 0, array.length - 1, cmp);
     }
 }

another[edit]

import java.util.*;
public class QuickSort 
{
    public static final Random RND = new Random();	

    public static void main(String[] args) 
    {
        /* Data to be sorted */
        List<Integer> data = createRandomData();
        
        /* Generate a random permutation of the data.
         * This sometimes improves the performance of QuickSort
         */
        Collections.shuffle(data);
        
        /* Call quick sort */
        List<Integer> sorted = quickSort(data);
        
        /* Print sorted data to the standard output */
        System.out.println(sorted);
    }
    
    /* Add data to be sorted to the list */
    public static List<Integer> createRandomData()
    {
        int max = 1000000;
        int len = 1000;
        List<Integer> list = new ArrayList<Integer>();
        for (int i=0; i<len; i++)
        {
            /* You can add any type that implements
             * the Comparable interface */             
            list.add(new Integer(RND.nextInt(max)));
        }
        return list;
    }
    
    public static <E extends Comparable<? super E>> List<E> quickSort(List<E> data)
    {
        List<E> sorted = new ArrayList<E>();
        rQuickSort(data, sorted);
        return sorted;
    }
    
    /**
     * A recursive implementation of QuickSort. Pivot selection
     * is random. The algorithm is stable.
     */
    public static <E extends Comparable<? super E>> void rQuickSort(List<E> data, List<E> sorted)
    {   
        if (data.size() == 1)
        {
            sorted.add(data.get(0));
            return;
        }
        
        if (data.size() == 0)
        {
            return;
        }
        
        /* choose the pivot randomly */
        int pivot = RND.nextInt(data.size());
        E pivotI = data.get(pivot);
        List<E> fatPivot = new ArrayList<E>();
        List<E> left = new ArrayList<E>();
        List<E> right = new ArrayList<E>();
        
        // partition data
        for (E next : data)
        {
            int compare = pivotI.compareTo(next);
            if (compare < 0)
            {
                right.add(next);
            }
            else if (compare > 0)
            {
                left.add(next);
            }
            else
            {
                fatPivot.add(next);
            }
        }
        rQuickSort(left, sorted);
        sorted.addAll(fatPivot);
        rQuickSort(right, sorted);
    }
}

JavaScript[edit]

function qsort(a) {
    if (a.length == 0) return [];

    var left = [];
    var right = [];
    var pivot = a[0];
    for (var i = a.length; --i;) {
        if (a[i] < pivot)
            left.push(a[i]);
        else
            right.push(a[i]);
    }

    return qsort(left).concat(pivot, qsort(right));
}

Mathematica[edit]

Here's a functional-style implementation:

QSort[{}] := {}
QSort[{h_, t___}] :=
  Join[QSort[Select[{t}, # < h &]], {h}, QSort[Select[{t}, # >= h &]]]

Here's a test driver which should yield True:

OrderedQ[QSort[Table[Random[Integer, {1, 10000}], {i, 1, 10000}]]]

MATLAB[edit]

   function [y]=quicksort(x)
        % Uses quicksort to sort an array. Two dimensional arrays are sorted column-wise.
	[n,m]=size(x);
	if(m>1)
		y=x;
		for j=1:m
			y(:,j)=quicksort(x(:,j));
		end
		return;
        end
	% The trivial cases
	if(n<=1);y=x;return;end;
	if(n==2)
		if(x(1)>x(2))
			x=[x(2); x(1)];
		end
		y=x;
		return;
	end
	% The non-trivial case
	% Find a pivot, and divide the array into two parts.
	% All elements of the first part are less than the
	% pivot, and the elements of the other part are greater 
	% than or equal to the pivot.
	m=fix(n/2);
        pivot=x(m);
	ltIndices=find(x<pivot); % Indices of all elements less than pivot.
	if(isempty(ltIndices)) % This happens when pivot is miniumum of all elements.
		ind=find(x>pivot); % Find the indices of elements greater than pivot.
		if(isempty(ind));y= x;return;end; % This happens when all elements are the same.
		pivot=x(ind(1)); % Use new pivot.
		ltIndices=find(x<pivot);
	end
        % Now find the indices of all elements not less than pivot.
	% Since the pivot is an element of the array, 
	% geIndices cannot be empty.
	geIndices=find(x>=pivot);
	% Recursively sort the two parts of the array and concatenate 
	% the sorted parts.
	y= [quicksort(x(ltIndices));quicksort(x(geIndices))];

Miranda[edit]

   sort []           = []  
   sort (pivot:rest) = sort [ y | y <- rest; y <= pivot ]  
                        ++ [pivot] ++
                       sort [ y | y <- rest; y >  pivot ]

OCaml[edit]

let rec sort = function
      [] -> []
    | pivot :: rest ->
        let left, right = List.partition (( > ) pivot) rest in
        sort left @ pivot :: sort right

Perl[edit]

Readable:

sub quicksort {
    my @list = @_;

    if ( scalar @list <= 1 ) {
        return (@list);
    }

    my $pivot   = shift @list;

    my @less    = grep($_ < $pivot, @list);
    my @greater = grep($_ > $pivot, @list);

    return ( quicksort(@less), $pivot, quicksort(@greater));
}

Laconic:

sub qsort {
  return () if !@_;
  return (qsort(grep { $_ < $_[0] } (@_)[1..$#_]), $_[0],
          qsort(grep { $_ >= $_[0] } (@_)[1..$#_]));
}

Or:

sub qsort {
  @_ or return ();
  my $p = shift;
  (qsort(grep $_ < $p, @_), $p, qsort(grep $_ >= $p, @_));
}

Perl 6[edit]

multi quicksort () { () }
multi quicksort (*$x, *@xs) {
   my @pre  = @xs.grep:{ $_ <  $x };
   my @post = @xs.grep:{ $_ >= $x };
   (@pre.quicksort, $x, @post.quicksort);
}

PHP[edit]

function quicksort($seq)
{
	if(!count($seq)) return $seq;
	
	$k = $seq[0];
	$x = $y = array();
	
	for($i=count($seq); --$i;)
	{
		if($seq[$i] <= $k)
		{
			$x[] = $seq[$i];
		}
		else
		{
			$y[] = $seq[$i];
		}
	}
	
	return array_merge(quicksort($x), array($k), quicksort($y));
}

Prolog[edit]

The version in the core implementations section is concise and, because it uses tail recursion, efficient. Here's another version:

append([], L, L).
append([H | L1], L2, [H | Result]) :- append(L1, L2, Result).

partition([], _, [], []).
partition([H | T], X, [H | Left], Right) :- H =< X, partition(T, X, Left, Right).
partition([H | T], X, Left, [H | Right]) :- H > X, partition(T, X, Left, Right).

qsort([],[]).
qsort([H | Tail], Sorted) :-
        partition(Tail, H, Left, Right),
        qsort(Left, SortedLeft),
        qsort(Right, SortedRight),
        append(SortedLeft, [X | SortedRight], Sorted).

Another version:

quicksort([], []).
quicksort([Pivot|Tail], Sorted) :-
    partition(Pivot, Tail, Smaller, Greater),
    quicksort(Smaller, SmallerSorted),
    quicksort(Greater, GreaterSorted),
    append(SmallerSorted, [Pivot|GreaterSorted], Sorted).
partition(_, [], [], []).
partition(Pivot, [Head|Tail], [Head|Smaller], Greater) :-
    Pivot > Head,
    partition(Pivot, Tail, Smaller, Greater).
partition(Pivot, [Head|Tail], Smaller, [Head|Greater]) :-
    Pivot =< Head,
    partition(Pivot, Tail, Smaller, Greater).

Python[edit]

Using list comprehensions and conditional espressions:

def qsort(L):
    return ((qsort([x for x in L[1:] if x < L[0]]) + L[0:1] +
             qsort([x for x in L[1:] if x >= L[0]])
            ) if L
            else [])

Using a less functional approach:

def qsort2(L):
    if len(L)<=1:
        return L
    pivot=L[0]
    less=    [x for x in L if x<pivot]
    equal=   [x for x in L if x==pivot]
    greater= [x for x in L if x>pivot]
    return qsort2(less)+equal+qsort2(greater)


In-place, O(log n) space and very readable(IMHO) version

  
def qsort3(arr, l, r):
    def swap(arr, s, d):
        if s != d:
            tmp = arr[s]
            arr[s] = arr[d]
            arr[d] = tmp
    if l >= r:
        return    
    m = l
    for i in range(l, r):
        if arr[i] <= arr[r]:
            swap(arr, i, m)
            m += 1
    swap(arr, m, r)
    qsort3(arr, l, m-1)
    qsort3(arr, m+1, r)
    return arr

Ruby[edit]

def quicksort(list)
  return list if list.size <= 1
  pivot = list.sample
  left, right = list.partition { |e| e < pivot }
  quicksort(left) + quicksort(right)
end

Scheme[edit]

This uses SRFI 1 and SRFI 8. It avoids redundantly traversing the list: it partitions it with the pivot in one traversal, not two, and it avoids copying entire lists to append them, by instead only adding elements on the front of the output list's tail.

(define (quicksort list elt<)
  (let qsort ((list list) (tail '()))
    (if (null-list? list)
        tail
        (let ((pivot (car list)))
          (receive (smaller larger)
                   (partition (lambda (x) (elt< x pivot))
                              (cdr list))
            (qsort smaller (cons pivot (qsort larger tail))))))))

Seed7[edit]

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]

Standard ML[edit]

The following example—though less general than the snippet in the core implementations section in that it does not accept a predicate argument—strives to more closely resemble the implementations in the other functional languages. The use of List.partition in both examples enables the implementation to walk the list only once per call, thereby reducing the constant factor of the algorithm.

fun qsort [] = []
  | qsort (h::t) = let val (left, right) = List.partition (fn x => x < h) t
                   in qsort left @ h :: qsort right
                   end;

Replacing the predicate is trivial:

fun qsort pred [] = []
  | qsort pred (h::t) = let val (left, right) = List.partition (fn x => pred (x, h)) t
                        in qsort pred left @ h :: qsort pred right
                        end;

A cleaner version that sacrifices the efficiency of List.partition and resembles the list-comprehension versions in other functional languages:

fun qsort [] = []
  | qsort (h::t) = qsort (List.filter (fn x => x < h) t) @ h :: qsort (List.filter (fn x => x >= h) t);

Tcl[edit]

proc qsort list {
 if {[llength $list] <= 1} {return $list}
 set pivot [lindex $list 0]
 set left [set equal [set right[list]]]
 foreach x $list {
        lappend [expr {$x<$pivot ? "left" : $x>$pivot ? "right" : "equal"}] $x
 }
 return [concat [qsort $left] $equal [qsort $right]]
}

TorqueScript[edit]

This is an implementation of Quicksort using script from the Torque game Builder (aka TorqueScript).

// Sorts unordered set %uSet, which must be of the class SimSet.
function Quicksort(%uSet)
{
    %less = new SimSet();
    %pivots = new SimSet();
    %greater = new SimSet();

    if(%uSet.getCount() <= 1)
        return %uSet;

    %pivotVal = %uSet.getObject(getRandom(0, %uSet.getCount()-1)).myValue;
    for(%i = 0; %i < %uSet.getCount(); %i ++)
    {
       // A new SimObject must be created in order to store it in a SimSet.
       %valObj = new SimObject(val)
       {
          myValue = %uSet.getObject(%i).myValue;
       };

        if(%pivotVal > %valObj.myValue)
            %less.add(%valObj);
        else if(%pivotVal == %valObj.myValue)
            %pivots.add(%valObj);
        else //if(%pivotVal < %valObj.myValue)
            %greater.add(%valObj);
    }

    return qConcatenate(Quicksort(%less), %pivots, Quicksort(%greater));
}

function qConcatenate(%less, %equal, %greater)
{
    %all = new SimSet();

    // Concatenate the three arrays, adding them to the SimSet one at a time.
    for(%i = 0; %i < %less.getCount(); %i ++)
    {
        %all.add(%less.getObject(%i));
    }
    for(%i = 0; %i < %equal.getCount(); %i ++)
    {
        %all.add(%equal.getObject(%i));
    }
    for(%i = 0; %i < %greater.getCount(); %i ++)
    {
        %all.add(%greater.getObject(%i));
    }

    return %all;
}

Visual Basic[edit]

Option Explicit

' a position, which is *hopefully* never used:
Public Const N_POS = -2147483648#

Public Sub Swap(ByRef Data() As Variant, _
                Index1 As Long, _
                Index2 As Long)
    If Index1 <> Index2 Then
        Dim tmp As Variant
        
        If IsObject(Data(Index1)) Then
            Set tmp = Data(Index1)
        Else
            tmp = Data(Index1)
        End If
        
        If IsObject(Data(Index2)) Then
            Set Data(Index1) = Data(Index2)
        Else
            Data(Index1) = Data(Index2)
        End If
        
        If IsObject(tmp) Then
            Set Data(Index2) = tmp
        Else
            Data(Index2) = tmp
        End If
        
        Set tmp = Nothing
    End If
End Sub

Public Sub QuickSort(ByRef Data() As Variant, _
                     Optional ByVal Lower As Long = N_POS, _
                     Optional ByVal Upper As Long = N_POS)
    If Lower = N_POS Then
        Lower = LBound(Data)
    End If
    
    If Upper = N_POS Then
        Upper = UBound(Data)
    End If
            
    If Lower < Upper Then
        Dim Right As Long
        Dim Left  As Long
    
        Left = Lower + 1
        Right = Upper + 1
        
        Do While Left < Right
            If Data(Left) <= Data(Lower) Then
                Left = Left + 1
            Else
                Right = Right - 1
                Swap Data, Left, Right
            End If
        Loop
        
        Left = Left - 1
        Swap Data, Lower, Left
        QuickSort Data, Lower, Left - 1
        QuickSort Data, Right, Upper
    End If
End Sub

Another implementation:

Function Quicksort(ByRef aData() As Long) As Long()
    Dim lPivot As Long
    
    Dim aLesser() As Long
    Dim aPivotList() As Long
    Dim aBigger() As Long
    Dim i As Long
    Dim count As Long
    Dim ret() As Long
    
    On Error Resume Next
    
    count = UBound(aData)
    
    If Err Then
        Exit Function
    ElseIf count = 0 Then
        Quicksort = aData
        Exit Function
    End If
    
    On Error GoTo 0
    
    Randomize
    lPivot = aData(Int(Rnd * count))
    
    For i = 0 To count
        If aData(i) < lPivot Then AddTo aData(i), aLesser
        If aData(i) = lPivot Then AddTo aData(i), aPivotList
        If aData(i) > lPivot Then AddTo aData(i), aBigger
    Next

    aLesser = Quicksort(aLesser)
    aPivotList = aPivotList
    aBigger = Quicksort(aBigger)
    
    ret = JoinLists(aLesser, aPivotList, aBigger)
    
    Quicksort = ret
End Function

Sub AddTo(ByVal lData As Long, ByRef aWhere() As Long)
    Dim count As Long
    
    On Error Resume Next
    
    count = UBound(aWhere) + 1
    ReDim Preserve aWhere(count)
    
    aWhere(count) = lData
    On Error GoTo 0
End Sub

Function JoinLists(ByRef Arr1() As Long, ByRef Arr2() As Long, ByRef Arr3() As Long) As Long()
    Dim count1 As Long
    Dim count2 As Long
    Dim count3 As Long
    Dim i As Long
    Dim ret() As Long
    Dim cnt As Long
    
    On Error Resume Next
    
    Err.Clear
    
    count1 = UBound(Arr1)
    If Err Then count1 = -1
    Err.Clear
    
    count2 = UBound(Arr2)
    If Err Then count2 = -1
    Err.Clear
    
    count3 = UBound(Arr3)
    If Err Then count3 = -1
    Err.Clear
    
    On Error GoTo 0
    
    ReDim ret(count1 + (count2 + 1) + (count3 + 1))
    
    For i = 0 To count1
        ret(i) = Arr1(i)
    Next
    
    For i = count1 + 1 To (count2 + 1) + count1
        ret(i) = Arr2(i - count1 - 1)
    Next
    
    For i = count2 + 1 + count1 + 1 To (count3 + 1) + (count2 + 1) + count1
        ret(i) = Arr3(i - count2 - 1 - count1 - 1)
    Next
    
    JoinLists = ret
End Function

To generalize it, simply change types to Variant.

Visual Basic for Applications[edit]

This is an Excel 2003 VBA implementation based on the Visual Basic implementation. I couldn't make it work with Variant so it is implemented as Date. Change Date to the data type relevant to you.

Sub Swap(ByRef Data() As Date, _
                Index1 As Long, _
                Index2 As Long)
    If Index1 <> Index2 Then
        Dim tmp As Variant
        
        tmp = Data(Index1)
        Data(Index1) = Data(Index2)
        Data(Index2) = tmp
        
        Set tmp = Nothing
    End If
End Sub

Sub QuickSort(ByRef Data() As Date, Lower As Long, Upper As Long)
            
    If Lower < Upper Then
        Dim Right As Long
        Dim Left  As Long
    
        Left = Lower + 1
        Right = Upper + 1
        
        Do While Left < Right
            If Data(Left) <= Data(Lower) Then
                Left = Left + 1
            Else
                Right = Right - 1
                Swap Data, Left, Right
            End If
        Loop
        
        Left = Left - 1
        Swap Data, Lower, Left
        QuickSort Data, Lower, Left - 1
        QuickSort Data, Right, Upper
    End If
End Sub

Zilog Z80000 Assembly[edit]

This implementation is in z80 assembly code. The processor is really ancient, and so its basically a register-stack recursion juggling feat. More on it and the author's comments here. It takes the register pairs BC and HL which point to the start and end memory locations to the list of one-byte elements to be sorted. All registers are filled with "garbage" data in the process, so they need to be pushed to the stack to be saved. The script is about 44 bytes long, and doesn't have pivot-optimizing code.

;
; Usage: bc->first, de->last,
;        call qsort
; Destroys: abcdefhl
;
qsort   ld      hl,0
        push    hl
qsloop  ld      h,b
        ld      l,c
        or      a
        sbc     hl,de
        jp      c,next1 ;loop until lo<hi
        pop     bc
        ld      a,b
        or      c
        ret     z       ;bottom of stack
        pop     de
        jp      qsloop
next1   push    de      ;save hi,lo
        push    bc
        ld      a,(bc)  ;pivot
        ld      h,a
        dec     bc
        inc     de
fleft   inc     bc      ;do i++ while cur<piv
        ld      a,(bc)
        cp      h
        jp      c,fleft
fright  dec     de      ;do i-- while cur>piv
        ld      a,(de)
        ld      l,a
        ld      a,h
        cp      l
        jp      c,fright
        push    hl      ;save pivot
        ld      h,d     ;exit if lo>hi
        ld      l,e
        or      a
        sbc     hl,bc
        jp      c,next2
        ld      a,(bc)  ;swap (bc),(de)
        ld      h,a
        ld      a,(de)
        ld      (bc),a
        ld      a,h
        ld      (de),a
        pop     hl      ;restore pivot
        jp      fleft
next2   pop     hl      ;restore pivot
        pop     hl      ;pop lo
        push    bc      ;stack=left-hi
        ld      b,h
        ld      c,l     ;bc=lo,de=right
        jp      qsloop