Hard
Randomized Lomuto quicksort on an array of identical keys
This quicksort chooses a uniformly random pivot and partitions with Lomuto's scheme. What is its running time on an array of n elements that all hold the same value?
main.cpp
int partition(vector<int>& a, int lo, int hi) {
swap(a[lo + rand() % (hi - lo + 1)], a[hi]); // random pivot to the end
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) swap(a[i++], a[j]);
swap(a[i], a[hi]);
return i;
}
void quicksort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}43 of 46 in Data Structures & Algorithms