Randomized Algorithms

This section concerns about the ith order statistic selection problem and many other significant yet practical randomized algorithms.

Randomized Selection

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.

Pseudocode

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)

Algorithm Analysis

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.

Randomized Quick Sort

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.