Partial Sort (v2)

Revision 2 of this benchmark created on

Setup

Test runner

Ready to run.

Testing in
TestOps/sec
Max Heap (3, a)
// A few Heap-functions that operate on an array
function maxSiftDown(arr, i=0, value=arr[i], comparator) {
    if (i >= arr.length) return;
    while (true) {
        var j = i*2+1;
        if (j+1 < arr.length && comparator(arr[j], arr[j+1])) j++;
        if (j >= arr.length || !comparator(value, arr[j])) break;
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = value;
}

function maxHeapify(arr, comparator) {
    for (var i = arr.length>>1; i--; ) maxSiftDown(arr, i, arr[i], comparator);
    return arr;
}

// The main algorithm
function partialSortWithMaxHeap(items, k, comparator) {
    var heap = maxHeapify(items.slice(0, k), comparator);
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (comparator(item, heap[0])) maxSiftDown(heap, 0, item, comparator);
    }
    return heap.sort(comparator);
}

// Sample data & call

var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

partialSortWithMaxHeap(arr, 3, (a, b) => a < b);
ready
Native Sort (3)
var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

arr.sort((a, b) => a < b);
if(arr.length > 3) {
	arr.length = 3;
}
ready
Max Heap (5)
// A few Heap-functions that operate on an array
function maxSiftDown(arr, i=0, value=arr[i], comparator) {
    if (i >= arr.length) return;
    while (true) {
        var j = i*2+1;
        if (j+1 < arr.length && comparator(arr[j], arr[j+1])) j++;
        if (j >= arr.length || !comparator(value, arr[j])) break;
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = value;
}

function maxHeapify(arr, comparator) {
    for (var i = arr.length>>1; i--; ) maxSiftDown(arr, i, arr[i], comparator);
    return arr;
}

// The main algorithm
function partialSortWithMaxHeap(items, k, comparator) {
    var heap = maxHeapify(items.slice(0, k), comparator);
    for (var i = k, len = items.length; i < len; ++i) {
        var item = items[i];
        if (comparator(item, heap[0])) maxSiftDown(heap, 0, item, comparator);
    }
    return heap.sort(comparator);
}

// Sample data & call

var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

partialSortWithMaxHeap(arr, 5, (a, b) => a < b);
ready
Native Sort (5)
var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

arr.sort((a, b) => a < b);
if(arr.length > 5) {
	arr.length = 5;
}
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.