
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. 


 
quick: procedure options (main); /* 4 April 2014 */
 
partition: procedure (list, left, right, pivot_Index) returns (fixed binary);
   declare list (*) fixed binary;
   declare (left, right, pivot_index) fixed binary;
   declare (store_index, pivot_value) fixed binary;
   declare I fixed binary;
 
     pivot_Value = list(pivot_Index);
     call swap (pivot_Index, right);  /* Move pivot to end */
     store_Index = left;
     do i = left to right-1;
         if list(i) < pivot_Value then
            do;
               call swap (store_Index, i);
               store_Index = store_index + 1;
            end;
     end;
     call swap (right, store_Index);  /* Move pivot to its final place */
     return (store_Index);
 
swap: procedure (i, j);
   declare (i, j) fixed binary; declare t fixed binary;
 
   t = list(i); list(i) = list(j); list(j) = t;
end swap;
end partition;
 
/* Returns the n-th smallest element of list within left..right inclusive */
/* (i.e. left <= n <= right). */
quick_select: procedure (list, left, right, n) recursive returns (fixed binary);
   declare list(*)          fixed binary;
   declare (left, right, n) fixed binary;
   declare pivot_index      fixed binary;
 
     if left = right then       /* If the list contains only one element */
         return ( list(left) ); /* Return that element                   */
     pivot_Index  = (left+right)/2;
         /* select a pivot_Index between left and right, */
         /* e.g. left + Math.floor(Math.random() * (right - left + 1)) */
     pivot_Index  = partition(list, left, right, pivot_Index);
     /* The pivot is in its final sorted position. */
     if n = pivot_Index then
         return ( list(n) );
     else if n < pivot_Index then
         return ( quick_select(list, left, pivot_Index - 1, n) );
     else
         return ( quick_select(list, pivot_Index + 1, right, n) );
 
end quick_select;
 
   declare a(10) fixed binary static initial (9, 8, 7, 6, 5, 0, 1, 2, 3, 4);
   declare I fixed binary;
 
   do i = 1 to 10;
      put skip edit ('The ', trim(i), '-th element is ', quick_select((a), 1, 10, (i) )) (a);
   end;
 
end quick;