Quickselect

Quickselect finds the k-th smallest element of an unsorted array in average linear time, without sorting the whole array. It reuses the partition step from quicksort — pick a pivot, move everything smaller to its left and everything larger to its right — but where quicksort then recurses into both sides, quickselect recurses into only the one side that can contain the answer. That single change drops the average cost from O(n log n) to O(n). See Quickselect for background.

Signature

quickselect(arr, k)
// arr: number[]  — the unsorted input (never mutated)
// k:   number    — a 1-indexed rank: 1 = smallest, arr.length = largest
// -> the k-th smallest value in arr

Examples

quickselect([3, 1, 4, 1, 5, 9, 2, 6], 1); // 1  — the smallest
quickselect([3, 1, 4, 1, 5, 9, 2, 6], 8); // 9  — the largest
quickselect([3, 1, 4, 1, 5, 9, 2, 6], 2); // 1  — the 2nd smallest (a duplicate)
quickselect([3, 1, 4, 1, 5, 9, 2, 6], 5); // 4  — the median-ish middle

quickselect([42], 1);          // 42
quickselect([], 1);            // throws RangeError (empty array)
quickselect([1, 2, 3], 0);     // throws RangeError (k below 1)
quickselect([1, 2, 3], 1.5);   // throws RangeError (k not an integer)

Notes

• k is 1-indexed — k = 1 is the minimum and k = arr.length is the maximum. The answer sits at 0-indexed position k - 1 once the array is ordered.
• Throw a RangeError — when arr is empty, or when k is not a whole number in the range 1 to arr.length.
• Never mutate the input — partitioning swaps elements around, so do it on a copy. The caller's array must be untouched after the call.
• Do not fully sort — that is the naive answer. Partition and keep only one side; the target is average O(n), not O(n log n).
• Duplicates count by position — with [1, 1, 2], the 2nd smallest is 1, not 2. Equal values each take a rank.
• Pick the pivot deterministically — choose it from the middle of the range (not always the first or last element) so already-sorted input stays fast. No Math.random.