
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


Use the quickselect algorithm on the vector

 [9, 8, 7, 6, 5, 0, 1, 2, 3, 4]
To show the first, second, third, ... up to the tenth largest member of the vector, in order, here on this page.

 Note: Quicksort has a separate task. 


procedure main(A)
    every writes(" ",select(1 to *A, A, 1, *A)|"\n")
end
 
procedure select(k,A,min,max)
    repeat {
        pNI := partition(?(max-min)+min, A, min, max)
        pD := pNI - min + 1
        if pD = k then return A[pNI]
        if k < pD then max := pNI-1
        else (k -:= pD, min := pNI+1)
        }
end
 
procedure partition(pivot,A,min,max)
    pV := (A[max] :=: A[pivot])
    sI := min
    every A[i := min to max-1] <= pV do (A[sI] :=: A[i], sI +:= 1)
    A[max] :=: A[sI]
    return sI
end