http://en.wikipedia.org/wiki/Selection_algorithm
1. partition algorithm
1 function partition(list, left, right, pivotIndex)
2 pivotValue := list[pivotIndex]
3 swap list[pivotIndex] and list[right] // Move pivot to end
4 storeIndex := left
5 for i from left to right-1
6 if list[i] < pivotValue
7 swap list[storeIndex] and list[i]
8 storeIndex := storeIndex + 1
9 swap list[right] and list[storeIndex] // Move pivot to its final place
10 return storeIndex
2. selection algorithm
1 function select(list, left, right, k)
2 loop
3 select pivotIndex between left and right
4 pivotNewIndex := partition(list, left, right, pivotIndex)
5 if k = pivotNewIndex - left + 1
6 return list[pivotNewIndex]
7 else if k < pivotNewIndex - left + 1
8 right := pivotNewIndex-1
9 else
10 left := pivotNewIndex+1
11 k := k - pivotNewIndex
>>
In above last statement, one bug. Should be k := k-pivotNewIndex-left+1 left := pivotNewIndex+13. code
1 int partition(std::vector<int>& a, int l, int r)
2 {
3 int i = l, j = l;
4 int p = a[r];
5 while (j<r) {
6 if (a[j] < p) {
7 std::swap(a[i], a[j]);
8 i++;
9 }
10 j++;
11 }
12 std::swap(a[r], a[i]);
13 return i;
14 }
15
16 void select_kth_smallest(std::vector<int>& a, int l, int r, int k)
17 {
18 while (1) {
19 int cut = partition(a, l, r);
20 #if 0
21 std::copy(a.begin()+l, a.begin()+cut, std::ostream_iterator<int>(std::cout, " "));
22 std::cout << " <=" << a[cut] << "=> ";
23 std::copy(a.begin()+cut+1, a.begin()+r+1, std::ostream_iterator<int>(std::cout, " "));
24 std::cout << "cut("<<cut<<"),k("<<k<<"),l("<<l<<"),r("<<r<<")\n";
25 #endif
26 if (cut-l+1==k)
27 break;
28 else if (k < cut-l+1)
29 r = cut-1;
30 else {
31 k = k-cut-1+l;
32 l = cut+1;
33 }
34 }
35 }
36