# Quick Select Algorithm, a Javascript Implementation

The function description comment says it all.

/* * Places the `k`

smallest elements (by `propName`

) in `arr`

in the first `k`

indices: `[0..k-1]`

* Modifies the passed in array *in place* * Returns a slice of the wanted eleemnts for convenience * Efficient mainly because it never performs a full sort. * * The only guarantees are that: * * - The `k`

th element is in its final sort index (if the array were to be sorted) * - All elements before index `k`

are smaller than the `k`

th element * * Reference */ function quickSelectInPlace(arr, k, propName) { if (!arr || arr.length <= k || typeof propName !== ‘string’) { throw ‘Invalid arguments to quickSelectInPlace’; } var len = arr.length;

var from = 0; var to = len - 1; while (from < to) { var left = from; var right = to; var pivot = arr[Math.ceil((left + right) * 0.5)][propName];

while (left < right) { if (arr[left][propName] >= pivot) { var tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; –right; } else { ++left; } }

if (arr[left][propName] > pivot) { –left; }

if (k <= left) { to = left; } else { from = left + 1; } } return arr.slice(0, k); }