
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. 


BEGIN
    # returns the kth lowest element of list using the quick select algorithm #
    PRIO QSELECT = 1;
    OP   QSELECT = ( INT k, REF[]INT list )INT:
         IF LWB list > UPB list THEN
             # empty list #
             0
         ELSE
             # non-empty list #
             # partitions the subset of list from left to right #
             PROC partition = ( REF[]INT list, INT left, right, pivot index )INT:
                  BEGIN
                      # swaps elements a and b in list #
                      PROC swap = ( REF[]INT list, INT a, b )VOID:
                           BEGIN
                               INT t = list[ a ];
                               list[ a ] := list[ b ];
                               list[ b ] := t
                           END # swap # ;
                      INT pivot value = list[ pivot index ];
                      swap( list, pivot index, right );
                      INT store index := left;
                      FOR i FROM left TO right - 1 DO
                          IF list[ i ] < pivot value THEN
                              swap( list, store index, i );
                              store index +:= 1
                          FI
                      OD;
                      swap( list, right, store index );
                      store index
                  END # partition # ;
             INT  left  := LWB list, right := UPB list, result := 0;
             BOOL found := FALSE;
             WHILE NOT found DO
                 IF left = right THEN
                     result := list[ left ];
                     found := TRUE
                 ELSE
                     INT pivot index = partition( list, left, right, left + ENTIER ( ( random * ( right - left ) + 1 ) ) );
                     IF k = pivot index THEN
                         result := list[ k ];
                         found := TRUE
                     ELIF k < pivot index THEN
                         right := pivot index - 1
                     ELSE
                         left  := pivot index + 1
                     FI
                 FI
             OD;
             result
         FI # QSELECT # ;
    # test cases #
    FOR i TO 10 DO
        [ 1 : 10 ]INT test := []INT( 9, 8, 7, 6, 5, 0, 1, 2, 3, 4 );
        print( ( whole( i, -2 ), ": ", whole( i QSELECT test, -3 ), newline ) )
    OD
END