
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. 


# Swap the values at two indices of a list
proc swap {list i j} {
    upvar 1 $list l
    set tmp [lindex $l $i]
    lset l $i [lindex $l $j]
    lset l $j $tmp
}
 
proc quickselect {vector k {left 0} {right ""}} {
    set last [expr {[llength $vector] - 1}]
    if {$right eq ""} {
	set right $last
    }
    # Sanity assertions
    if {![llength $vector] || $k <= 0} {
	error "Either empty vector, or k <= 0"
    } elseif {![tcl::mathop::<= 0 $left $last]} {
	error "left is out of range"
    } elseif {![tcl::mathop::<= $left $right $last]} {
	error "right is out of range"
    }
 
    # the _select core, inlined
    while 1 {
	set pivotIndex [expr {int(rand()*($right-$left))+$left}]
 
	# the partition core, inlined
	set pivotValue [lindex $vector $pivotIndex]
	swap vector $pivotIndex $right
	set storeIndex $left
	for {set i $left} {$i <= $right} {incr i} {
	    if {[lindex $vector $i] < $pivotValue} {
		swap vector $storeIndex $i
		incr storeIndex
	    }
	}
	swap vector $right $storeIndex
	set pivotNewIndex $storeIndex
 
	set pivotDist [expr {$pivotNewIndex - $left + 1}]
	if {$pivotDist == $k} {
	    return [lindex $vector $pivotNewIndex]
	} elseif {$k < $pivotDist} {
	    set right [expr {$pivotNewIndex - 1}]
	} else {
	    set k [expr {$k - $pivotDist}]
	    set left [expr {$pivotNewIndex + 1}]
	}
    }
}