
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.




 
We create a binary tree from a random array, then we walk the canopy.
 
1) three functions for readability:         
 
{def BT.data  {lambda {:t} {A.get 0 :t}}} -> BT.data
{def BT.left  {lambda {:t} {A.get 1 :t}}} -> BT.left
{def BT.right {lambda {:t} {A.get 2 :t}}} -> BT.right
 
2) adding a leaf to the tree: 
 
{def BT.add {lambda {:x :t}
 {if {A.empty? :t}
  then {A.new :x {A.new} {A.new}}
  else {if   {= :x {BT.data :t}}
        then :t
        else {if {< :x {BT.data :t}}
              then {A.new {BT.data :t} 
                          {BT.add :x {BT.left :t}}
                          {BT.right :t}}
              else {A.new {BT.data :t} 
                          {BT.left :t}
                          {BT.add :x {BT.right :t}} }}}}}}
-> BT.add
 
3) creating the tree from an array of numbers:
 
{def BT.create           
 {def BT.create.rec
  {lambda {:l :t}
   {if {A.empty? :l}
    then :t
    else {BT.create.rec {A.rest :l}
                        {BT.add {A.first :l} :t}} }}}
 {lambda {:l}
  {BT.create.rec :l {A.new}} }}
-> BT.create
 
4) walking the canopy -> sorting in increasing order:
 
{def BT.sort
 {lambda {:t}
  {if {A.empty? :t}
   then else {BT.sort {BT.left :t}}
             {BT.data :t}
             {BT.sort {BT.right :t}} }}}   
-> BT.sort
 
Testing
 
1) generating random numbers:
 
{def L {A.new 
 {S.map {lambda {:n} {floor {* {random} 100000}}} {S.serie 1 100}}}} 
-> L =  [1850,7963,50540,92667,72892,47361,19018,40640,10126,80235,48407,51623,63597,71675,27814,63478,18985,88032,46585,85209,
74053,95005,27592,9575,22162,35904,70467,38527,89715,36594,54309,39950,89345,72224,7772,65756,68766,43942,52422,85144,
66010,38961,21647,53194,72166,33545,49037,23218,27969,83566,19382,53120,55291,77374,27502,66648,99637,37322,9815,432,90565,
37831,26503,99232,87024,65625,75155,55382,30120,58117,70031,13011,81375,10490,39786,1926,71311,4213,55183,2583,22075,90411,
92928,61120,94259,433,93332,88423,64119,40850,94318,27816,84818,90632,5094,36696,94705,50602,45818,61365]
 
2) creating the tree is the main work:
 
{def T {BT.create {L}}} 
-> T = [1850,[432,],[433,],]]],[7963,[7772,[1926,],[4213,[2583,],]],[5094,],]]]],]],[50540,[47361,[19018,[10126,[9575,],
[9815,],]]],[18985,[13011,[10490,],]],]],]]],[40640,[27814,[27592,[22162,[21647,[19382,],]],[22075,],]]],[23218,],
[27502,[26503,],]],]]]],]],[35904,[33545,[27969,[27816,],]],[30120,],]]],]],[38527,[36594,],[37322,[36696,],]],[37831,],]]]],
[39950,[38961,],[39786,],]]],]]]]],[46585,[43942,[40850,],]],[45818,],]]],]]]],[48407,],[49037,],]]]],[92667,[72892,
[51623,[50602,],]],[63597,[63478,[54309,[52422,],[53194,[53120,],]],]]],[55291,[55183,],]],[55382,],[58117,],[61120,],[61365,],]]]]]]],]],[71675,[70467,[65756,[65625,[64119,],]],]],[68766,[66010,],[66648,],]]],[70031,],]]]],[71311,],]]],
[72224,[72166,],]],]]]]],[80235,[74053,],[77374,[75155,],]],]]],[88032,[85209,[85144,[83566,[81375,],]],[84818,],]]],]],
[87024,],]]],[89715,[89345,[88423,],]],]],[90565,[90411,],]],[90632,],]]]]]]],[95005,[92928,],[94259,[93332,],]],[94318,],
[94705,],]]]]],[99637,[99232,],]],]]]]]]]
 
3) walking the canopy is fast:   
 
{BT.sort {T}}
->  432 433 1850 1926 2583 4213 5094 7772 7963 9575 9815 10126 10490 13011 18985 19018 19382 21647 22075 22162 23218 26503
 27502 27592 27814 27816 27969 30120 33545 35904 36594 36696 37322 37831 38527 38961 39786 39950 40640 40850 43942 45818
 46585 47361 48407 49037 50540 50602 51623 52422 53120 53194 54309 55183 55291 55382 58117 61120 61365 63478 63597 64119
 65625 65756 66010 66648 68766 70031 70467 71311 71675 72166 72224 72892 74053 75155 77374 80235 81375 83566 84818 85144
 85209 87024 88032 88423 89345 89715 90411 90565 90632 92667 92928 93332 94259 94318 94705 95005 99232 99637     
 
4) walking with new leaves is fast:
 
{BT.sort {BT.add -1 {T}}}
->  -1 432 433 1850 1926 2583 4213 5094 7772 7963 9575 9815 10126 10490 13011 18985 19018 19382 21647 22075 22162 23218 26503
 27502 27592 27814 27816 27969 30120 33545 35904 36594 36696 37322 37831 38527 38961 39786 39950 40640 40850 43942 45818 46585
 47361 48407 49037 50540 50602 51623 52422 53120 53194 54309 55183 55291 55382 58117 61120 61365 63478 63597 64119 65625 65756
 66010 66648 68766 70031 70467 71311 71675 72166 72224 72892 74053 75155 77374 80235 81375 83566 84818 85144 85209 87024 88032
 88423 89345 89715 90411 90565 90632 92667 92928 93332 94259 94318 94705 95005 99232 99637
 
{BT.sort {BT.add 50000 {T}}}
->  432 433 1850 1926 2583 4213 5094 7772 7963 9575 9815 10126 10490 13011 18985 19018 19382 21647 22075 22162 23218 26503
 27502 27592 27814 27816 27969 30120 33545 35904 36594 36696 37322 37831 38527 38961 39786 39950 40640 40850 43942 45818 46585
 47361 48407 49037 50000 50540 50602 51623 52422 53120 53194 54309 55183 55291 55382 58117 61120 61365 63478 63597 64119 65625
 65756 66010 66648 68766 70031 70467 71311 71675 72166 72224 72892 74053 75155 77374 80235 81375 83566 84818 85144 85209 87024
 88032 88423 89345 89715 90411 90565 90632 92667 92928 93332 94259 94318 94705 95005 99232 99637
 
{BT.sort {BT.add 100000 {T}}}
->  432 433 1850 1926 2583 4213 5094 7772 7963 9575 9815 10126 10490 13011 18985 19018 19382 21647 22075 22162 23218 26503
 27502 27592 27814 27816 27969 30120 33545 35904 36594 36696 37322 37831 38527 38961 39786 39950 40640 40850 43942 45818 46585
 47361 48407 49037 50540 50602 51623 52422 53120 53194 54309 55183 55291 55382 58117 61120 61365 63478 63597 64119 65625 65756
 66010 66648 68766 70031 70467 71311 71675 72166 72224 72892 74053 75155 77374 80235 81375 83566 84818 85144 85209 87024 88032
 88423 89345 89715 90411 90565 90632 92667 92928 93332 94259 94318 94705 95005 99232 99637 100000
 