Partial Sort (v3)

Revision 3 of this benchmark created on

Description

Comparing Partial Sort implementations

Setup

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

function maxHeapify(arr, comparator) {
    for (var i = arr.length>>1; i--; ) maxSiftDown(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 (item < heap[0]) maxSiftDown(heap, 0, comparator, item);
    }
    return heap.sort(comparator);
}

Test runner

Ready to run.

Testing in
TestOps/sec
Native Sort + Truncate
var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

var new_arr = arr.toSorted((a, b) => a - b);
if(new_arr.length > 3) {
	new_arr.length = 3;
}

if(new_arr[0] > new_arr[1] || new_arr[1] > new_arr[2]) {
	throw new Error(new_arr);
}
ready
Max Heap
var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

var new_arr = partialSortWithMaxHeap(arr, 3, (a, b) => a - b);

if(new_arr[0] > new_arr[1] || new_arr[1] > new_arr[2]) {
	throw new Error(new_arr);
}
ready
No Operation (Measuring constructing the array)
var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));
ready
Sanity (Ensuring they yield the same result)
var arr = Array.from({length:20}, () => Math.floor(Math.random() * 1e5));

var new_arr0 = arr.toSorted((a, b) => a - b);
if(new_arr0.length > 3) {
	new_arr0.length = 3;
}

var new_arr1 = partialSortWithMaxHeap(arr, 3, (a, b) => a - b);

if(new_arr0[0] > new_arr0[1] || new_arr0[1] > new_arr0[2]) {
	throw new Error(new_arr0);
}

if(new_arr0[0] != new_arr1[0] || new_arr0[1] != new_arr1[1] || new_arr0[2] != new_arr1[2]) {
	throw new Error("Different results");
}
ready

Revisions

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