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](http://en.wikipedia.org/wiki/Quickselect)
 */
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);
}

Copyright © 2008-present Brendan Graetz