Partial sort in JavaScript

Is there any built-in JavaScript function to do a partial sort? If not, what is a good way to implement it?

Given an unsorted array of N elements, I would like to find K elements that are minimal with respect to some weighting function. K is much smaller than N, so it would be inefficient to sort the whole array and take the first K elements.

I would be happy even if there was something non-standard, browser-dependent. I could still fallback to the custom JavaScript implementation.

PS: This is my current custom implementation (without taking a weighting function into account, just sorting the elements as they are for simplicity):

function bisect(items, x, lo, hi) {
  var mid;
  if (typeof(lo) == 'undefined') lo = 0;
  if (typeof(hi) == 'undefined') hi = items.length;
  while (lo < hi) {
    mid = Math.floor((lo + hi) / 2);
    if (x < items[mid]) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function insort(items, x) {
  items.splice(bisect(items, x), 0, x);
}

function partialSort(items, k) {
  var smallest = [];
  for (var i = 0, len = items.length; i < len; ++i) {
    var item = items[i];
    if (smallest.length < k || item < smallest[smallest.length - 1]) {
      insort(smallest, item);
      if (smallest.length > k)
        smallest.splice(k, 1);
    }
  }
  return smallest;
}

console.log(partialSort([5, 4, 3, 2, 1, 6, 7, 8, 1, 9], 3));

The algorithm walks through the given array one single time, keeping track of a sorted list of the k smallest items so far, using binary search to insert new elements.

Please post alternative solutions if you think they might be faster or more elegant. Timings are very welcome.

Answer

No. There’s only the full array sort, so you will need to use your own implementation.

Little improvement on your code (I had thought of exactly the same algorithm :-)):

function partialSort(items, k) {
    var smallest = items.slice(0, k).sort(),
        max = smallest[k-1];
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (item < max) {
            insort(smallest, item);
            smallest.length = k;
            max = smallest[k-1];
        }
    }
    return smallest;
}

(Even seems to be a little faster, I guess due to caching the max variable)

Leave a Reply

Your email address will not be published. Required fields are marked *