15 Quick Select and Finding the Median

Lecture from: 19.12.2024 | Video: Videos ETHZ

Finding the Median

The central problem addressed in this section is the efficient computation of the median. The median of a dataset is defined as the middle element when the data is sorted. For a dataset with an even number of elements, the median is typically calculated as the average of the two central elements. It is crucial to distinguish the median from the mean (average); they are distinct statistical measures.

Relevance to Quicksort

The median holds significant importance in statistics, primarily because it provides a robust measure of central tendency. Unlike the mean, which can be significantly skewed by outliers, the median remains relatively stable.

Furthermore, the median plays a crucial role in the efficiency of the Quicksort algorithm, which was previously discussed (See Quicksort). Quicksort relies on selecting a pivot element, ideally the median, to partition the data. When the median is chosen as the pivot, Quicksort achieves its optimal runtime complexity of $O(n\log n)$.

Recall that Quicksort’s worst-case time complexity is $O(n^2)$. This occurs when the pivot selection consistently results in highly unbalanced partitions (e.g., repeatedly choosing the smallest or largest element). However, if the pivot is chosen randomly, the average runtime complexity is $O(n\log n)$.

The best-case scenario for Quicksort arises when the exact median is selected as the pivot, leading to perfectly balanced partitions and a runtime of $O(n\log n)$. Further analysis, to be covered in a subsequent course (AnW), will demonstrate that selecting a pivot from a range of values near the median can still maintain an average-case time complexity of $O(n\log n)$.

The Need for a Fast Median Algorithm

To guarantee that Quicksort operates with its optimal $O(n\log n)$ time complexity, we require an efficient method for finding the median. Ideally, this method should have a linear time complexity, denoted as $O(n)$. This requirement stems from the recurrence relation analysis of Quicksort, which indicates that even algorithms with complexities like $O(n^2)$ would be insufficient to achieve the desired overall performance.

Let’s examine several potential approaches and their corresponding time complexities:

Idea 1: Pairwise Comparisons

A naive approach might involve comparing each element to all others, counting how many elements are larger or smaller. However, this method inherently possesses a time complexity of $O(n^2)$. This is because, in the worst-case scenario, each element must be compared to every other element.

Idea 2: Balanced Search Tree

Another possibility is to construct a balanced search tree, such as an AVL tree. Once the tree is built, the median can be easily retrieved (e.g., as the root element in a balanced tree). However, the construction of a balanced search tree itself requires $O(n\log n)$ time, due to the necessary balancing operations. This approach does not satisfy the linear time requirement.

Idea 3: Sorting

A straightforward approach would be to sort the entire array, after which the median can be directly accessed. While conceptually simple, this method defeats the purpose, as sorting itself typically requires $O(n\log n)$ time, exceeding our desired linear complexity.

Idea 4: Pseudopolynomial Approach (Bucketsort Variation)

A more promising direction involves adapting a pseudopolynomial algorithm, similar to Bucketsort. Instead of sorting based on keys, elements would be distributed into buckets based on their values. The efficiency of this approach would be heavily dependent on the range of values present in the array. While potentially offering near-linear performance under specific conditions, this method would inherently be pseudopolynomial, meaning its runtime depends on the magnitude of the values, not just the number of elements.

Quickselect

We generalize the median problem to finding the $k$-th smallest element in an unsorted array, for any given $k$. This is the selection problem.

Formal Problem Definition

Given:

• An unsorted array $A$ of $n$ elements.
• An integer $k$ ($1\le k\le n$).

Find:

• The $k$-th smallest element in $A$ (the element at index $k-1$ in a sorted $A$).

Note: The median is a special case. For odd $n$, $k=\lceil n/2\rceil$. For even $n$, it involves averaging the elements at $k=n/2$ and $k=n/2+1$.

Quickselect Algorithm

Quickselect, inspired by Quicksort, solves the selection problem efficiently using recursion and partitioning:

1. Pivot Selection: Choose a pivot element $p$ from $A$. (Pivot selection strategies will be discussed later).

2. Partitioning: Rearrange $A$ around $p$ such that elements less than $p$ are placed before it, and elements greater than $p$ are after it. Let $i$ be the index of $p$ after partitioning. Formally:

   • $A[j]\le p$ for all $1\le j\le i$
   • $A[j]>p$ for all $i<j\le n$ The partition subroutine determines the correct sorted position, $i$, of $p$.

3. Recursive Calls: Based on $i$ and $k$:

   • Case 1 ($i=k$): Return $p$ (it’s the $k$-th smallest).
   • Case 2 ($i<k$): Recursively call $\text{Quickselect}(A[i+1\dots n],k-i)$ (search the right subarray, adjusting the rank).
   • Case 3 ($i>k$): Recursively call $\text{Quickselect}(A[1\dots i-1],k)$ (search the left subarray).

This “divide and conquer” approach reduces the problem size at each step. Partitioning eliminates a portion of the array, focusing only on the subarray containing the $k$-th smallest element. Recursion continues until $i=k$, at which point the element is found.

Pivot Selection

The choice of pivot significantly impacts Quickselect’s performance. A consistently poor pivot choice (e.g., always the smallest or largest element) leads to a worst-case runtime of $O(n^2)$, similar to Quicksort’s worst case. However, as with Quicksort, a “good enough” pivot, even if not the exact median, can still ensure efficiency.

Formalization

To formalize this, consider an array of size $n$. Let $ϵ$ represent a fraction representing the proportion of elements at either end of the sorted array that we want to avoid selecting as the pivot. A “good” pivot, then, is one that falls within the central $(1-2ϵ)$ portion of the sorted array. The worst-case size of the subproblem, within this “good” range, is then at most $(1-ϵ)n$. Let $p=1-ϵ$.

We can express the recurrence relation for the runtime, $T(n)$, when consistently choosing a “good” pivot as:

$T(n)\le T(p\cdot n)+cn$

where $c$ is a constant representing the time taken for partitioning and other operations. Telescoping this recurrence (repeatedly substituting):

This is a geometric series. Since $0<p<1$, the series converges:

$cn{\sum }_{i=0}^{\infty }{p}^i=cn\left(\frac{1}{1-p}\right)$

Since $c$ and $\frac{1}{1-p}$ are constants (independent of $n$), we have:

$T(n)\in O(n)$

Therefore, even with a pivot that isn’t precisely the median, but consistently falls within a defined central range of the sorted array, Quickselect achieves a linear expected runtime. This is because the problem size is reduced by a constant factor in each recursive step.

Choosing the Pivot (Median of Medians)

The remaining challenge is to efficiently find a “good” pivot deterministically. The algorithm described here is due to Blum, Floyd, Pratt, Rivest, and Tarjan. It modifies the pivot selection step (step 1) of the standard Quickselect algorithm.

We modify the $\text{Quickselect}(A,k)$ algorithm with a new Step 1 (Pivot Selection):

1. Median of Medians Pivot Selection:
   • a. Group into Fives: Divide the input array $A$ into groups of five elements each. If the number of elements, $n$, is not divisible by 5, the last group may have fewer than five elements. This is acceptable.
   • b. Find Group Medians: For each group of five (or fewer) elements, find its median. This can be done efficiently using a constant number of comparisons since each group has a fixed, small size (at most 5). Store these medians in a new array, $M$.
   • c. Recursive Call: Recursively call Quickselect on the array $M$ of medians to find the median of $M$. Specifically, call $\text{Quickselect}(M,\lceil |M|/2\rceil )$. The result of this recursive call is the pivot, $p$, that will be used in the main Quickselect algorithm’s partitioning step.

The rest of the Quickselect algorithm (partitioning and recursive calls based on the pivot’s position) remains unchanged. This median-of-medians approach provides a deterministic way to select a pivot that guarantees a good split, leading to a worst-case linear time complexity for the overall selection problem.

How good is $p$?

Let $p$ be the pivot chosen by the median-of-medians algorithm. We conjecture that $p$ is a “good” pivot in the sense defined earlier, meaning it’s neither too close to the smallest nor the largest element in the sorted array.

Let $M$ be the array of medians found in step 1b. Since $p$ is the median of $M$, at least half of the elements in $M$ are less than or equal to $p$. $|M|=\lceil n/5\rceil$, so at least $\lceil \frac{1}{2}\lceil n/5\rceil \rceil \ge \frac{n}{10}$ elements in $M$ are less than or equal to $p$.

Each element in $M$ that is less than or equal to $p$ is itself the median of a group of five elements in the original array $A$. Therefore, for each such median, there are at least three elements in its group (including itself) that are less than or equal to $p$ (the median and the two elements smaller than it). The exception is the possible last group with less than 5 elements. However, its size is bounded and does not significantly affect the overall analysis as $n$ grows.

Thus, there are at least $3\cdot \frac{n}{10}=\frac{3n}{10}$ elements in $A$ that are less than or equal to $p$. By a similar argument, there are at least $\frac{3n}{10}$ elements in $A$ that are greater than or equal to $p$. This implies that the largest subproblem size after partitioning is at most $n-\frac{3n}{10}=\frac{7n}{10}$. So, we have $ϵ=\frac{3}{10}$.

Runtime

Let’s derive the runtime complexity, $T(n)$, of Quickselect with the median-of-medians pivot selection.

The recurrence relation is:

$T(n)\le T\left(\frac{n}{5}\right)+T\left(\frac{7n}{10}\right)+cn$

This is because:

• $T(n/5)$: The recursive call to find the median of medians (finding $p$) operates on an array of size at most $n/5$ (the array $M$).
• $T(7n/10)$: The recursive call on the larger partition after partitioning around $p$ operates on an array of size at most $7n/10$ (as shown above).
• $cn$: The time to divide $A$ into groups of five, find the median of each group, and partition $A$ around $p$ is linear in $n$.

We conjecture that $T(n)\le 10cn$ for some constant $c$, i.e., $T(n)\in O(n)$. We will prove this using strong induction.

Base Case: For $n=1$, $T(1)\le c\le 10c$. The base case holds.

Inductive Step: Assume that $T(k)\le 10ck$ for all $k<n$. We want to show that $T(n)\le 10cn$.

Using the recurrence relation and the inductive hypothesis:

Thus, $T(n)\le 10cn$, completing the inductive step.

Therefore, by strong induction, $T(n)\le 10cn$ for all $n\ge 1$, which means $T(n)\in O(n)$. The median-of-medians Quickselect algorithm has a worst-case linear time complexity.

Why Groups of Five?

A natural question is why we chose groups of five in the median-of-medians algorithm. The choice is crucial for achieving the linear time complexity. The key lies in the coefficients of the recursive terms in the recurrence relation, specifically that their sum must be less than 1.

In the analysis with groups of five, we had:

$T(n)\le T\left(\frac{n}{5}\right)+T\left(\frac{7n}{10}\right)+cn$

The crucial part is that $\frac{1}{5}+\frac{7}{10}=\frac{9}{10}<1$. This sum being less than 1 is essential for the overall runtime to be $O(n)$. If the sum were equal to or greater than 1, the telescoping method would lead to a logarithmic or higher complexity.

Let’s examine what happens if we use groups of three instead:

1. Groups of Three: We divide the array $A$ into groups of three.

2. Medians Array: The array $M$ of medians will have size $\lceil n/3\rceil$.

3. Elements Less Than/Greater Than p: The median of medians, $p$, will have at least $\lceil \frac{1}{2}\lceil n/3\rceil \rceil \ge \frac{n}{6}$ medians in $M$ less than or equal to it. Each of these medians represents two elements in $A$ (itself and one smaller element) that are less than or equal to $p$. Thus, there are at least $2\cdot \frac{n}{6}=\frac{n}{3}$ elements less than or equal to $p$. Similarly, there are at least $\frac{n}{3}$ elements greater than or equal to p.

4. Largest Subproblem: The size of largest partition passed into recursion is $\le \frac{2n}{3}$. So $ϵ=\frac{1}{3}$.

5. Recurrence: This leads to the recurrence relation:

   $T(n)\le T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+cn$

Here, $\frac{1}{3}+\frac{2}{3}=1$. When we telescope this recurrence, the $cn$ terms do not decrease geometrically. Instead, we get a sum of the form $cn+cn+cn+...$ for approximately ${\log }_{3/2}n$ levels of recursion. This results in a runtime complexity of $O(n\log n)$, not $O(n)$.

Using groups of seven (or any larger odd constant) would work. The sum of the coefficients in the recurrence would be less than 1. For example, with groups of seven, you’d get a recurrence like $T(n)\le T(n/7)+T(5n/7)+cn$, and $1/7+5/7=6/7<1$.

However, using a group size of $n$ (the entire array) would be equivalent to directly sorting the array to find the median, which defeats the purpose and leads to an $O(n\log n)$ algorithm. The efficiency of the median-of-medians approach comes from finding an approximate median quickly (in linear time) and using that to partition the array. Finding the exact median of the entire array upfront is too expensive. The constant number of operations for finding the median of a constant-size group is key to maintaining linear overall performance. The choice of 5 is the smallest odd integer that guarantees the desired linear time complexity.

This was the last lecture…