
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. 


fcn qselect(list,nth){	// in place quick select
   fcn(list,left,right,nth){
      if (left==right) return(list[left]);
      pivotIndex:=(left+right)/2; // or median of first,middle,last
 
      	// partition
      pivot:=list[pivotIndex];
      list.swap(pivotIndex,right);	// move pivot to end
      pivotIndex := left;
      i:=left; do(right-left){	// foreach i in ([left..right-1])
	 if (list[i] < pivot){
	    list.swap(i,pivotIndex);
	    pivotIndex += 1;
	 }
	 i += 1;
      }
      list.swap(pivotIndex,right);	// move pivot to final place
 
      if (nth==pivotIndex) return(list[nth]);
      if (nth<pivotIndex)  return(self.fcn(list,left,pivotIndex-1,nth));
      return(self.fcn(list,pivotIndex+1,right,nth));
   }(list.copy(),0,list.len()-1,nth);
}