Heapsort comparison count

heapsort_comparison_count.js

let count = 0;

function shuffle(array) {
    var currentIndex = array.length, temporaryValue, randomIndex;

    // While there remain elements to shuffle...
    while (0 !== currentIndex) {

        // Pick a remaining element...
        randomIndex = Math.floor(Math.random() * currentIndex);
        currentIndex -= 1;

        // And swap it with the current element.
        temporaryValue = array[currentIndex];
        array[currentIndex] = array[randomIndex];
        array[randomIndex] = temporaryValue;
    }

    return array;
}


class HeapSort {
    constructor(inputArray) {
        this.inputArray = inputArray;
        this.heapSize = inputArray.length;
        this.count = 0;
    }

    main() {

        // console.log("Heap sort launched.");

        // the largest element is moved at the first place
        this.buildMaxHeap();

        // the first element is moved to the end and the next largest element is moved to the first place on each iteration
        // the heapsize decreases because the end of the array become ordered
        for (var j = this.inputArray.length - 1; j >= 0; j--) {
            this.inputArray.swap(0, j);
            this.heapSize--;
            this.maxHeapify(0);
        }

        count += this.count;

        // console.log(this.inputArray, this.count);

    }

    buildMaxHeap() {
        // we only need to process the first half of the array because all element will be checked (as we check the
        // right and left node)
        for (var j = Math.floor(this.inputArray.length / 2); j >= 0; j--) {
            this.maxHeapify(j);
        }
    }

    // the largest element between i, left(i) and right(i) will take the place of i
    maxHeapify(i) {

        var left = this.left(i);
        var right = this.right(i);
        var largest = i;

        this.count += 3;

        if (left < this.heapSize && this.inputArray[left] > this.inputArray[i]) {
            largest = left;
        }

        if (right < this.heapSize && this.inputArray[right] > this.inputArray[largest]) {
            largest = right;
        }

        if (largest != i) {
            this.inputArray.swap(i, largest);
            // we recursively call max heapify on the smallest element freshly moved so that it will moved in the array
            // regarding its size
            this.maxHeapify(largest);
        }
    }

    // our graph is represented as a flat array
    // to access the left and right node of an element we need their index
    // see: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/141_a.gif and apply the formula using the picture

    left(i) {
        return 2 * i + 1; // +1 because an array start at 0
    }

    right(i) {
        return 2 * i + 2; // +1 because an array start at 0
    }
}

Array.prototype.swap = function (x, y) {
    var b = this[x];
    this[x] = this[y];
    this[y] = b;
    return this;
}

const list = [1, 2];
for (let j = 0; j < 10; j++) {
    list.push(j + 2);
    const startTime = Date.now();
    for (let i = 0; i < 1000000; i++) {
        new HeapSort(shuffle(list.slice(0))).main();
    }
    const endTime = Date.now();
    console.log(`Random average for 1000000 loop with list size of ${list.length}: ${count / 1000000} (${endTime - startTime} ms)`);
    count = 0;
}

/**
Random average for 1000000 loop with list size of 3: 16.999659 (131 ms)
Random average for 1000000 loop with list size of 4: 28.003032 (223 ms)
Random average for 1000000 loop with list size of 5: 36.101535 (204 ms)
Random average for 1000000 loop with list size of 6: 48.198732 (259 ms)
Random average for 1000000 loop with list size of 7: 56.558256 (316 ms)
Random average for 1000000 loop with list size of 8: 71.903922 (385 ms)
Random average for 1000000 loop with list size of 9: 83.073018 (445 ms)
Random average for 1000000 loop with list size of 10: 98.21235 (529 ms)
Random average for 1000000 loop with list size of 11: 109.328262 (596 ms)
Random average for 1000000 loop with list size of 12: 125.389611 (690 ms)
 */