
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 log2n) sorts
Shell Sort
O(n2) 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




 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)



Task

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 run-time 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.




/*REXX program  sorts  a  stemmed array  using the   quicksort  algorithm.              */
call gen@                                        /*generate the elements for the array. */
call show@   'before sort'                       /*show  the  before   array elements.  */
call qSort       #                               /*invoke the  quicksort  subroutine.   */
call show@   ' after sort'                       /*show  the   after   array elements.  */
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
inOrder: parse arg n; do j=1  for n-1;  k= j+1;  if @.j>@.k  then return 0; end;  return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
qSort: procedure expose @.; a.1=1; parse arg b.1;  $= 1 /*access @.; get @. size; pivot.*/
       if inOrder(b.1)  then return                     /*Array already in order? Return*/
             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    /*a teeny─tiny loop.*/
                        do k=k  by -1  while j< k & @.k>=p;  end    /*another   "    "  */
                    if j>=k  then leave                             /*segment finished? */
                    _= @.j;   @.j= @.k;   @.k= _                    /*swap J&K elements.*/
                    end   /*forever*/
             $= $ + 1
             k= j - 1;   @.L= @.k;   @.k= p
             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          /*while $¬==0*/
       return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show@: w= length(#);       do j=1  for #;  say 'element'  right(j,w)  arg(1)":"  @.j;  end
       say copies('▒', maxL + w + 22)            /*display a separator (between outputs)*/
       return
/*──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────*/
gen@:  @.=;   maxL=0                                    /*assign a default value for the array.*/
       @.1  = " Rivers that form part of a (USA) state's border "                                   /*this value is adjusted later to include a prefix & suffix.*/
       @.2  = '='                                                                                   /*this value is expanded later.  */
       @.3  = "Perdido River                       Alabama, Florida"
       @.4  = "Chattahoochee River                 Alabama, Georgia"
       @.5  = "Tennessee River                     Alabama, Kentucky, Mississippi, Tennessee"
       @.6  = "Colorado River                      Arizona, California, Nevada, Baja California (Mexico)"
       @.7  = "Mississippi River                   Arkansas, Illinois, Iowa, Kentucky, Minnesota, Mississippi, Missouri, Tennessee, Louisiana, Wisconsin"
       @.8  = "St. Francis River                   Arkansas, Missouri"
       @.9  = "Poteau River                        Arkansas, Oklahoma"
       @.10 = "Arkansas River                      Arkansas, Oklahoma"
       @.11 = "Red River (Mississippi watershed)   Arkansas, Oklahoma, Texas"
       @.12 = "Byram River                         Connecticut, New York"
       @.13 = "Pawcatuck River                     Connecticut, Rhode Island and Providence Plantations"
       @.14 = "Delaware River                      Delaware, New Jersey, New York, Pennsylvania"
       @.15 = "Potomac River                       District of Columbia, Maryland, Virginia, West Virginia"
       @.16 = "St. Marys River                     Florida, Georgia"
       @.17 = "Chattooga River                     Georgia, South Carolina"
       @.18 = "Tugaloo River                       Georgia, South Carolina"
       @.19 = "Savannah River                      Georgia, South Carolina"
       @.20 = "Snake River                         Idaho, Oregon, Washington"
       @.21 = "Wabash River                        Illinois, Indiana"
       @.22 = "Ohio River                          Illinois, Indiana, Kentucky, Ohio, West Virginia"
       @.23 = "Great Miami River (mouth only)      Indiana, Ohio"
       @.24 = "Des Moines River                    Iowa, Missouri"
       @.25 = "Big Sioux River                     Iowa, South Dakota"
       @.26 = "Missouri River                      Kansas, Iowa, Missouri, Nebraska, South Dakota"
       @.27 = "Tug Fork River                      Kentucky, Virginia, West Virginia"
       @.28 = "Big Sandy River                     Kentucky, West Virginia"
       @.29 = "Pearl River                         Louisiana, Mississippi"
       @.30 = "Sabine River                        Louisiana, Texas"
       @.31 = "Monument Creek                      Maine, New Brunswick (Canada)"
       @.32 = "St. Croix River                     Maine, New Brunswick (Canada)"
       @.33 = "Piscataqua River                    Maine, New Hampshire"
       @.34 = "St. Francis River                   Maine, Quebec (Canada)"
       @.35 = "St. John River                      Maine, Quebec (Canada)"
       @.36 = "Pocomoke River                      Maryland, Virginia"
       @.37 = "Palmer River                        Massachusetts, Rhode Island and Providence Plantations"
       @.38 = "Runnins River                       Massachusetts, Rhode Island and Providence Plantations"
       @.39 = "Montreal River                      Michigan (upper peninsula), Wisconsin"
       @.40 = "Detroit River                       Michigan, Ontario (Canada)"
       @.41 = "St. Clair River                     Michigan, Ontario (Canada)"
       @.42 = "St. Marys River                     Michigan, Ontario (Canada)"
       @.43 = "Brule River                         Michigan, Wisconsin"
       @.44 = "Menominee River                     Michigan, Wisconsin"
       @.45 = "Red River of the North              Minnesota, North Dakota"
       @.46 = "Bois de Sioux River                 Minnesota, North Dakota, South Dakota"
       @.47 = "Pigeon River                        Minnesota, Ontario (Canada)"
       @.48 = "Rainy River                         Minnesota, Ontario (Canada)"
       @.49 = "St. Croix River                     Minnesota, Wisconsin"
       @.50 = "St. Louis River                     Minnesota, Wisconsin"
       @.51 = "Halls Stream                        New Hampshire, Canada"
       @.52 = "Salmon Falls River                  New Hampshire, Maine"
       @.53 = "Connecticut River                   New Hampshire, Vermont"
       @.54 = "Arthur Kill                         New Jersey, New York (tidal strait)"
       @.55 = "Kill Van Kull                       New Jersey, New York (tidal strait)"
       @.56 = "Hudson River (lower part only)      New Jersey, New York"
       @.57 = "Rio Grande                          New Mexico, Texas, Tamaulipas (Mexico), Nuevo Leon (Mexico), Coahuila de Zaragoza (Mexico), Chihuahua (Mexico)"
       @.58 = "Niagara River                       New York, Ontario (Canada)"
       @.59 = "St. Lawrence River                  New York, Ontario (Canada)"
       @.60 = "Poultney River                      New York, Vermont"
       @.61 = "Catawba River                       North Carolina, South Carolina"
       @.62 = "Blackwater River                    North Carolina, Virginia"
       @.63 = "Columbia River                      Oregon, Washington"
                       do #=1  until  @.#==''           /*find how many entries in array,  and */
                       maxL=max(maxL, length(@.#))      /*   also find the maximum width entry.*/
                       end   /*#*/;   #= #-1            /*adjust the highest element number.   */
       @.1= center(@.1, maxL, '-')                      /*   "    "  header information.       */
       @.2= copies(@.2, maxL)                           /*   "    "     "   separator.         */
       return