3.2 Selection, quickselect, and linear-time sorting

The selection problem asks for the kth smallest element, not for a fully sorted array. That distinction matters. Sorting always solves selection, but it often does more work than the question requires.

This section connects three ideas from the local tutorial and sorting slides: partial selection, quickselect, and non-comparison sorting.

The selection problem

The simplest special case is the minimum. Scanning once is enough, so the cost is O(n). But the general kth smallest problem is more subtle, because we need enough order information to know which element has rank k.

Two naive approaches

The tutorial gives two natural approaches.

First, sort the whole array and read the kth position. This is easy to reason about, but if the sorting algorithm is comparison-based, the typical cost is at least around O(n log n).

Second, repeatedly find and remove the smallest element until the kth round. This is partial selection sort. It avoids completing the entire sort, but each round still scans a remaining suffix.

Quickselect uses the quicksort partition idea differently

Quicksort partitions and then recursively sorts both sides. Quickselect uses the same partition idea, but it recurses into only one side.

After partitioning around a pivot, the pivot has a rank position relative to the current subarray. If that rank is exactly k, we are done. If the desired rank is smaller, recurse only on the left side. If it is larger, recurse only on the right side with an adjusted rank.

The important word is "can". Pivot choices still matter. A bad pivot sequence can make quickselect behave quadratically, while good or randomized pivot choices give much better expected behavior.

Comparison sorting has a lower bound

The linear-time sorting slides remind us that merge sort, heapsort, and quicksort are comparison sorts. In the worst case, comparison sorting needs Omega(n log n) comparisons. To beat that barrier, an algorithm must use extra information about the keys instead of relying only on pairwise comparisons.

Counting sort

The range assumption is essential. If keys lie in 0 to $K$, we need a count array whose size depends on $K$.

The algorithm has three conceptual steps:

1. count occurrences of each key;
2. accumulate the counts so each entry tells how many keys are at most that value;
3. place each input element into the output position determined by the cumulative counts.

Counting sort is linear when $K = O(n)$, but it is not in-place and it is not a general-purpose comparison sort.

Radix sort

Radix sort sorts numbers digit by digit. The slides emphasize that it commonly uses a stable sorting routine such as counting sort as a subroutine.

Stability is not optional here. If a later digit pass destroys the order created by an earlier digit pass, the final result can be wrong.

Common mistakes

• Solving selection by sorting without noticing the extra work.
• Claiming quickselect is always linear without stating pivot assumptions.
• Saying counting sort is O(n) while ignoring the key range $K$.
• Using a non-stable subroutine inside radix sort.

Exercises

1. Explain why quickselect recurses on only one partition side.
2. Give a case where partial selection sort is reasonable.
3. Explain why radix sort usually needs a stable subroutine.