Randomized Algorithms (Spring 2010)/Introduction

Randomized Quicksort

For an input set S with an arbitrary order, the Quicksort algorithm sorts [math]\displaystyle{ S }[/math] as described in following psuedocode:

• if [math]\displaystyle{ |S|\gt 1 }[/math] do:
  • pick an element [math]\displaystyle{ x }[/math] from [math]\displaystyle{ S }[/math] as the pivot;
  • partition [math]\displaystyle{ S }[/math] into [math]\displaystyle{ S_1 }[/math], [math]\displaystyle{ \{x\} }[/math], and [math]\displaystyle{ S_2 }[/math], where all elements in [math]\displaystyle{ S_1 }[/math] are smaller than [math]\displaystyle{ x }[/math] and all elements in [math]\displaystyle{ S_2 }[/math] are larger than [math]\displaystyle{ x }[/math];
  • recursively sort [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math];

Let us measure the time complexity of this sorting algorithm by the number of comparisons.

For the deterministic quicksort algorithm, the pivot element is chosen deterministically (usually the first one in the sequence [math]\displaystyle{ S }[/math]). This will make the worst-case time complexity [math]\displaystyle{ \Omega(n^2) }[/math], which means there exists a bad case [math]\displaystyle{ S }[/math], sorting which will cost us [math]\displaystyle{ \Omega(n^2) }[/math] comparisons, every time!

It is just so unfair to have an unbeatable case for this brilliant algorithm. So we tweak the algorithm a little bit:

Algorithm: RandQSort

• if [math]\displaystyle{ |S|\gt 1 }[/math] do:
  • uniformly pick a random element [math]\displaystyle{ x }[/math] from [math]\displaystyle{ S }[/math] as the pivot;
  • partition [math]\displaystyle{ S }[/math] into [math]\displaystyle{ S_1 }[/math], [math]\displaystyle{ \{x\} }[/math], and [math]\displaystyle{ S_2 }[/math], where all elements in [math]\displaystyle{ S_1 }[/math] are smaller than [math]\displaystyle{ x }[/math] and all elements in [math]\displaystyle{ S_2 }[/math] are larger than [math]\displaystyle{ x }[/math];
  • recursively sort [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math];

Analysis of RandQSort

Suppose that [math]\displaystyle{ S=\{a_1,a_2,\ldots,a_n\} }[/math], where [math]\displaystyle{ a_1\lt a_2\lt \ldots\lt a_n }[/math]. Let [math]\displaystyle{ X_{ij}\in\{0,1\} }[/math] be the random variable which indicates whether [math]\displaystyle{ a_i }[/math] and [math]\displaystyle{ a_j }[/math] are compared during the execution of RandQSort. That is:

[math]\displaystyle{ \begin{align} X_{ij} &= \begin{cases} 1 & a_i\mbox{ and }a_j\mbox{ are compared}\\ 0 & \mbox{otherwise} \end{cases}. \end{align} }[/math]

Elements [math]\displaystyle{ a_i }[/math] and [math]\displaystyle{ a_j }[/math] are compared only if one of them is chosen as pivot and after comparison they are separated (thus never compared again). Observation 1: Every pair of [math]\displaystyle{ a_i }[/math] and [math]\displaystyle{ a_j }[/math] are compared at most once.