Smaller left, bigger right
Pick a pivot, move everything smaller to its left and bigger to its right — the pivot is now in its final place. Recurse on both sides: that's quicksort, usually the fastest sort in practice. Recurse on only the side containing position k and you get quickselect: the k-th smallest item without sorting everything.
Partition, sort, select
function partition(a, lo, hi) {
const p = lo + Math.floor(Math.random() * (hi - lo + 1));
[a[p], a[hi]] = [a[hi], a[p]];
const pivot = a[hi];
let store = lo;
for (let i = lo; i < hi; i++) {
if (a[i] < pivot) {
[a[i], a[store]] = [a[store], a[i]];
store++;
}
}
[a[store], a[hi]] = [a[hi], a[store]];
return store;
}
function quickSort(a, lo = 0, hi = a.length - 1) {
if (lo >= hi) return a;
const p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
return a;
}
console.log(quickSort([9, 3, 7, 1, 8, 2, 5]));
function kthSmallest(arr, k) {
const a = arr.slice();
let lo = 0, hi = a.length - 1;
for (;;) {
const p = partition(a, lo, hi);
if (p === k) return a[p];
if (p < k) lo = p + 1; else hi = p - 1;
}
}
console.log("median:", kthSmallest([9, 3, 7, 1, 8, 2, 5], 3));