
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.




;--------------------------------------------------------------------------------------------------------------------
; Quicksort, inputs (__sdcccall(1) calling convention):
; HL = uint16_t* A (pointer to beginning of array)
; DE = uint16_t len (number of word elements in array)
; modifies: AF, A'F', BC, DE, HL
; WARNING: array can't be aligned to start/end of 64ki address space, like HL == 0x0000, or having last value at 0xFFFE
; WARNING: stack space required is on average about 6*log(len) (depending on the data, in extreme case it may be more)
quicksort_a:
    ; convert arguments to HL=A.begin(), DE=A.end() and continue with quicksort_a_impl
    ex      de,hl
    add     hl,hl
    add     hl,de
    ex      de,hl
    ;  |
    ; fallthrough into implementation
    ;  |
    ;  v
;--------------------------------------------------------------------------------------------------------------------
; Quicksort implementation, inputs:
; HL = uint16_t* A.begin() (pointer to beginning of array)
; DE = uint16_t* A.end() (pointer beyond array)
; modifies: AF, A'F', BC, HL (DE is preserved)
quicksort_a_impl:
    ; array must be located within 0x0002..0xFFFD
    ld      c,l
    ld      b,h         ; BC = A.begin()
    ; if (len < 2) return; -> if (end <= begin+2) return;
    inc     hl
    inc     hl
    or      a
    sbc     hl,de       ; HL = -(2*len-2), len = (2-HL)/2
    ret     nc          ; case: begin+2 >= end <=> (len < 2)
 
    push    de          ; preserve A.end() for recursion
    push    bc          ; preserve A.begin() for recursion
 
    ; uint16_t pivot = A[len / 2];
    rr      h
    rr      l
    dec     hl
    res     0,l
    add     hl,de
    ld      a,(hl)
    inc     hl
    ld      l,(hl)
    ld      h,b
    ld      b,l
    ld      l,c
    ld      c,a         ; HL = A.begin(), DE = A.end(), BC = pivot
 
    ; flip HL/DE meaning, it makes simpler the recursive tail and (A[j] > pivot) test
    ex      de,hl       ; DE = A.begin(), HL = A.end(), BC = pivot
    dec     de          ; but keep "from" address (related to A[i]) at -1 as "default" state
 
    ; for (i = 0, j = len - 1; ; i++, j--) { ; DE = (A+i-1).hi, HL = A+j+1
.find_next_swap:
 
    ; while (A[j] > pivot) j--;
.find_j:
    dec     hl
    ld      a,b
    sub     (hl)
    dec     hl          ; HL = A+j (finally)
    jr      c,.find_j   ; if cf=1, A[j].hi > pivot.hi
    jr      nz,.j_found ; if zf=0, A[j].hi < pivot.hi
    ld      a,c         ; if (A[j].hi == pivot.hi) then A[j].lo vs pivot.lo is checked
    sub     (hl)
    jr      c,.find_j
.j_found:
 
    ; while (A[i] < pivot) i++;
.find_i:
    inc     de
    ld      a,(de)
    inc     de          ; DE = (A+i).hi (ahead +0.5 for swap)
    sub     c
    ld      a,(de)
    sbc     a,b
    jr      c,.find_i   ; cf=1 -> A[i] < pivot
 
    ; if (i >= j) break; // DE = (A+i).hi, HL = A+j, BC=pivot
    sbc     hl,de       ; cf=0 since `jr c,.find_i`
    jr      c,.swaps_done
    add     hl,de       ; DE = (A+i).hi, HL = A+j
 
    ; swap(A[i], A[j]);
    inc     hl
    ld      a,(de)
    ldd
    ex      af,af
    ld      a,(de)
    ldi
    ex      af,af
    ld      (hl),a      ; Swap(A[i].hi, A[j].hi) done
    dec     hl
    ex      af,af
    ld      (hl),a      ; Swap(A[i].lo, A[j].lo) done
 
    inc     bc
    inc     bc          ; pivot value restored (was -=2 by ldd+ldi)
    ; --j; HL = A+j is A+j+1 for next loop (ready)
    ; ++i; DE = (A+i).hi is (A+i-1).hi for next loop (ready)
    jp      .find_next_swap
 
.swaps_done:
    ; i >= j, all elements were already swapped WRT pivot, call recursively for the two sub-parts
    dec     de          ; DE = A+i
 
    ; quicksort_c(A, i);
    pop     hl          ; HL = A
    call    quicksort_a_impl
 
    ; quicksort_c(A + i, len - i);
    ex      de,hl       ; HL = A+i
    pop     de          ; DE = end() (and return it preserved)
    jp      quicksort_a_impl