Selection Algorithms

Describe the use of selection algorithms and their applications in following cases

1.Partition based
2.Median of median
3.Tournament Method

1.Partition Method: Randomized Select


Algorithm :
QuickSelect:
Given array A of size n and integer k ≤ n,
1. Pick a pivot element p at random from A.
2. Split A into subarrays LESS and GREATER by comparing each element to p as in Quicksort. While we are at it, count the number L of elements going in to LESS.
3. (a) If L = k − 1, then output p.
(b) If L > k − 1, output QuickSelect(LESS, k).
(c) If L < k − 1, output QuickSelect(GREATER, k − L − 1)

NOTE : if we have a duplicate element in the array we can eliminate those by using a O(n) duplicate elimination algorithm. a simple addition to the quickselect.


Randomised algo Summary:
Expected Run time : O(n)
Worst case : O(n2)

2.Median of Medians: Deterministic Select


The algorithm in words:
1. Divide n elements into groups of 5
2. Find median of each group (How? How long?)
3. Use Select() recursively to find median x of the ?n/5? medians
4. Partition the n elements around x. Let k = rank(x)
5. if (i == k) then return x
if (i k) use Select() recursively to find (i-k)th smallest element in last partition

source :
http://www.cs.virginia.edu/~luebke/cs332.fall00/lecture8/tsld017.htm
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm




Useful Links:
http://en.wikipedia.org/wiki/Selection_algorithm