Lesson 2

The main idea of the QuickSort algorithm can be used to design an elegant and efficient randomized algorithm for the order statistics problem. In this problem, one is given a sequence \(A=(a_{0}, \dotsb, a_{n-1})\) of integers and an integer \(k \in \{0,\dotsc,n-1\}\) and is asked to compute the element of rank \(k\), that is, the \((k+1)\)-st smallest element of the sequence.

Randomized QuickSelect proceeds as follows: select a random element \(p\) (called the pivot) of \(A\) and partition \(A\) into three parts containing elements smaller than \(p\), equal to \(p\), and greater than \(p\); then, proceed recursively with one of the three parts.

1. Choose a pivot element \(p\) uniformly at random from \(A\).
2. Partition \(A\) into three multisets: \[S = \{x \in A \colon x < p\}, \quad E = \{x \in A \colon x = p\}, \quad G = \{x \in A \colon x > p\}.\]
3. If \(k < |S|\), recursively select the \(k\)-th smallest element in \(S\).
4. If \(|S| \le k < |S| + |E|\), return \(p\).
5. Otherwise, recursively select the \((k - |S| - |E|)\)-th smallest element in \(G\).

This is how it can be implemented in Python.

from random import choice


def order_statistics(lst, k):
    pivot = choice(lst)

    smaller = [x for x in lst if x < pivot]
    if k < len(smaller):
        return order_statistics(smaller, k)

    equal = [x for x in lst if x == pivot]
    if len(smaller) <= k < len(smaller) + len(equal):
        return pivot

    greater = [x for x in lst if x > pivot]
    return order_statistics(greater, k - len(smaller) - len(equal))


l = [5, 2, 6, 1, 2, 7, 2, 2, 7, 9, 3]
print(order_statistics(l, 4))
print(order_statistics(l, 10))

2
9

Problem. Test your intuition! What is the expected running time of Randomized QuickSelect?