Hard
Quickselect pivoting on the first element
This quickselect always pivots on a[lo], the first element of the current subrange. What is its worst-case complexity, what input triggers it, and what change would restore expected O(n) regardless of input?
main.cpp
int partition(vector<int>& a, int lo, int hi) {
int pivot = a[lo]; // always pivot on the first element
int i = lo;
for (int j = lo + 1; j <= hi; j++)
if (a[j] < pivot) swap(a[++i], a[j]);
swap(a[lo], a[i]);
return i;
}
int quickselect(vector<int>& a, int lo, int hi, int k) {
if (lo == hi) return a[lo];
int p = partition(a, lo, hi);
if (k == p) return a[p];
else if (k < p) return quickselect(a, lo, p - 1, k);
else return quickselect(a, p + 1, hi, k);
}28 of 46 in Data Structures & Algorithms