Fundamental Algorithms

I'm starting a new series (will see how it 'll go:)) about some very basic algorithms implemented in C++. The first, order statistics . I use classic divide and conquer strategy, with random pivot (it's not the best, but reasonable choice, I think it gives nearly amortised linear time). As a bonus, there is quicksort algorithm - uses the same partition function. Code (partition and order statistic: quick_select here):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

int partition(int a[], int p, int r) { int t = a[r]; int i = p - 1; for (int j = p; j < r;j++){ if (a[j] <= t) { i += 1; std::swap(a[i], a[j]); } } std::swap(a[i + 1], a[r]); return i + 1; } int quick_select(int a[], int s, int n, int k) { int r = partition_random(a, s, n); if (r - s == k - 1) {return a[r];} else { if (k - 1 < r - s) { return quick_select(a, s, r - 1, k); } else { return quick_select(a, r + 1 , n, k - r + s - 1); } } } int partition_random(int a[], int p, int r) { std::random_device rd; std::mt19937 rng(rd()); std::uniform_int_distribution<int> uni(p, r); auto rn = uni(rng); std::swap(a[r], a[rn]); return partition(a, p, r); }

As seen, quick_select use partition to split initial array, according to some random index; and then recurs in certain part, depends if k - the #nth smallest is top or bottom part of the array.
Partition algorithm is commonly known, explanation can be found on the web; it returns number of elements less than the last element of the array, and mutates array in place (moving the all elements less then pivot, to the left). It could be use to compute, median:

1 2 3 4 5 6 7 8

float median(int a [], int n) { if (n % 2 == 1) return quick_select(a, 0, n - 1, n / 2 + 1); int l = n / 2; int r = n / 2 + 1; return (1.0 * (quick_select(a, 0, n - 1, l) + quick_select(a, 0, n - 1, r))) / 2; }

In C++ Standard Library, order statistics is named: nth_element. Code on github .

Thank you.