Linear Time Median

Summary

We can find the median of a list of numbers without sorting by combining ideas of QuickSort and Sample Sort.

Contents

• Problem
• Basic Approach
  • Psuedocode
  • Reverse Engineering
    • Representative Sample
  • FastSelect

Problem

Given an unsorted list $A = \left[ a_1, \ldots, a_n \right]$ of n numbers, find the median of $A$.

median
$\left\lceil\frac{n}{2}\right\rceil$th smallest element

When n is odd:

$n = 2l + 1$

$\text{median} = \left(l + 1\right)^{st} \text{ smallest}$

More generally,

Given an unsorted list $A = \left[ a_1, \ldots, a_n \right]$ of n numbers and an integer k where $1 \le k \le n$, find the kth smallest of A.

Basic Approach

QuickSort style

1. Choose a pivot p
2. Partition A into $A < p, A=p, A>p$
3. Recursively sort $A <p &amp; A>p$

In order to make our median selecting algorithm $O(n)$ instead of $O\left( n\log{n} \right)$, we only need to recursively search one of the sub lists, not both.

Psuedocode

QuickSelect(A,k):

• Choose a pivot p
• Partition A into $A < p, A=p, A>p$
• Recurse
  • If $k \le |A < p|$ then return QuickSelect($A<p, k$)
  • If $|A < p| < k \le |A<p| + |A=p|$ then return p
  • If $k > |A<p| + |A=p|$ then return QuicSelect($A>p, k - |A<p| - |A=p|$)

Reverse Engineering

good pivot
$|A<p| \le \frac{3n}{4} \& |A>p| \le \frac{3n}{4}$

If we randomly select a pivot, there’s a 50% chance its good. We can instead choose a representative sample to choose the pivot from to gaurantee it’s good.

Representative Sample

We want to choose a subset S, then find a median of S, and have that median be an approximation of the median of A.

for each $x \in S$, we want a few (2) elements of A are $\le x$ and a few (2) elements that are $\ge x$

Break A into $\frac{n}{5}$ groups of 5 elements each. Then sort each group and find the median of the middle group.

FastSelect

• Break A into $\frac{n}{5}$ groups, $G_1, G_2, \cdots, G_{\frac{n}{5}}$
• For i = 1 -> $\frac{n}{5}$
  • Sort $G_i$ and let $m_i = \text{median}(G_i)$
• let $S = \lbrace m_1, \cdots, m_{\frac{n}{5}} \rbrace$
• p = FastSelect($S, \frac{n}{10}$)
• Partition A into $A < p, A=p, A>p$
• Recurse
  • If $k \le |A < p|$ then return FastSelect($A<p, k$)
  • If $|A < p| < k \le |A<p| + |A=p|$ then return p
  • If $k > |A<p| + |A=p|$ then return FastSelect($A>p, k - |A<p| - |A=p|$)