This section concerns about the ith order statistic selection problem and many other significant yet practical randomized algorithms.
A computation task described as follows: Find the ith smallest element (also termed as the ith order statistic) in a randomly distributed array.
In a more general question that to locate a median within a randomly distributed array, the fundamental idea of randomized selection is also useful, contributing in Quick Sort partition method as well.
RANDOMIZED_SELECT(array, order_statistic)
if length(array) = 1
return array[1]
choose a pivot uniformly from array at random
find the index i of that pivot
if i = order_statistic
return pivot
else if i > order_statistic
return RANDOMIZED_SELECT(array[1..i], order_statistic)
else if i < order_statistic
return RANDOMIZED_SELECT(array[i+1..], order_statistic)
The average running time of RANDOMIZED SELECTION is Ο(n) for every possible input length n.
Proof:
Define a phase j where the set of pivot choices lies between the size of n ⋅ (3/4)j+1 and n ⋅ (3/4)j (in each iteration, choosing a central element that has 1/4 elements smaller than it and 1/4 elements larger than it makes the next length at least 3/4 of the current length).
It takes 50-50 to choose a random splitter that has a 25-75 split and thus E(X) = 1 + 1/2 ⋅ E(X), E(X) = 2, where X is number of iterations before central element is found.
Then, by linearity of expectation,
E(Τ(n)) = cn ∑ (3/4)j ⋅ E(Xj); E(Τ(n)) ⩽ 2 cn ∑ (3/4)j = 8 cn
Then, the average running time is Ο(n), proof ends.
A Quick Sort algorithm aims to swiftly sort the un-ordered elements in the array. With a randomized pivot selection method (borrowed from the idea of randomized selection) introduced to the phase of choosing pivot of partition method, Quick Sort will have an efficiency of Ο(n ⋅ log n) in the expected running time.