32.2 Quick Select

Dissatisfied with the result that Quicksort is unable to completely defeat Mergesort and truly claim the title for "fastest comparison-based sorting" algorithm, let's shoot our one last shot to overturn the result: use Quick Select to identify the median.

Quick Select Algorithm

Goal: find the median using partioning.

Key idea: Median of an length n array will be around index n /2.

1. Initialize array with the leftmost item as the pivot.

Initial Array

For this example, the index of the median should be 9 / 2 = 4.

1. Partition around pivot.

Pivot lands at index 2

Since the pivot is at index 2, which is not the median. Therefore, need to continue. However, will only partition the right subproblem because median can't be to the left! (index n/2 > 2)

1. Partition the subproblem. Repeat the process.

Pivot is at index 6, which means that it is not at the median. Continue.

1. Stop when the pivot is at the median index.

Since pivot is at index 4, we are done.

Quick Select Performance

Worst Case Runtime

The worst case is when the array is in sorted order, which yields a runtime of $\theta(N^2)$.

Expected Runtime

The expected runtime for the Quick Select Algorithm is $\theta(N)$. Here's an intuitive diagram that justifies this result:

Using one of our favorite sums, we can see the runtime is:

$$N + N/2 + N/4 +.... + 1 = \theta(N)$$

Compared to MergeSort?

Unfortunately, even using Quickselect to find the exact median, the resulting algorithm is still quite slow.

Team Mergesort wins, sadly.