Step 6 of 6
Challenge: quickselect
To find the k-th smallest element (a median, a percentile, "the 95th percentile latency"), you don't need to sort everything. Quickselect partitions like quicksort, but then only continues into the one side that contains position k. The other side is never touched.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> latency_ms = {120, 35, 80, 300, 45, 60, 95, 40, 250, 55};
std::vector<int> v = latency_ms;
std::size_t mid = v.size() / 2;
std::nth_element(v.begin(), v.begin() + mid, v.end());
std::cout << "median-ish (index 5): " << v[mid] << "\n";
std::size_t p90 = v.size() * 9 / 10;
std::nth_element(v.begin(), v.begin() + p90, v.end());
std::cout << "90th percentile: " << v[p90] << "\n";
std::sort(latency_ms.begin(), latency_ms.end()); // check against a full sort
std::cout << latency_ms[mid] << " " << latency_ms[p90] << "\n";
}
median-ish (index 5): 80
90th percentile: 300
80 300
std::nth_element puts the element that would be at that position after sorting into place, with smaller ones before it and larger ones after, in no particular order. That's quickselect.
Why O(n) on average
Each partition costs time proportional to the current range, and with a decent pivot the range roughly halves: n + n/2 + n/4 + ... is about 2n, so O(n) on average. Sorting would be O(n log n).
The loop
lo = 0, hi = n - 1
loop:
p = partition(v, lo, hi)
if p == k: return v[k]
if k < p: hi = p - 1
else: lo = p + 1
No recursion is needed, since only one side continues.
Pivot choice
With the last element as the pivot, already-sorted input makes every partition split off just one element, which is O(n²). Taking the middle element as the pivot (swap it to the end, then partition as usual) fixes the common sorted and reverse-sorted cases.
Your turn: write int kth_smallest(std::vector<int> v, int k) (k is 0-based; the vector is passed by value so you may rearrange it) using your own partition loop. Pick the middle element as the pivot (swap it to the end first) so already-sorted input stays fast.