Partial Sort

Benchmark created on April 2, 2024

Setup

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

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

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

// Sample data & call

Test runner

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

partialSortWithMaxHeap(arr, 3);

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

arr.sort();
if(arr.length > 3) {
	arr.length = 3;
}

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

Revisions

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

• Revision 1: published on April 2, 2024