Tag: JavaScript

I designed and implemented this fancy sorting algorithm that combines natural runs in the input array with a heap data structure:

function ArrayRangeException(message) {
    this.message = message;
    this.getMessage = function() { return this.message; }
}

function RangeCheck(arrayLength, fromIndex, toIndex) {
    if (fromIndex < 0) {
        throw new ArrayRangeException("'fromIndex' is negative: " + fromIndex);
    }

    if (toIndex > arrayLength) {
        throw new ArrayRangeException(
                "'toIndex' is too large: " + toIndex + ", array length: " + 
                arrayLength);
    }

    if (fromIndex > toIndex) {
        throw new ArrayRangeException(
            "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
    }
}   

function RunHeap(array, cmp) {
    this.cmp = cmp;
    this.array = array;
    const auxArrayLength = (array.length >>> 1) + 1;
    this.fromIndexArray = Array(auxArrayLength);
    this.toIndexArray = Array(auxArrayLength);
    this.size = 0;

    this.pushRun = function(fromIndex, toIndex) {
        const nodeIndex = this.size++;
        this.fromIndexArray(nodeIndex) = fromIndex;
        this.toIndexArray(nodeIndex) = toIndex;
    },

    this.popElement = function() {
        const returnValue = this.array(this.fromIndexArray(0));
        this.fromIndexArray(0)++;

        if (this.fromIndexArray(0) === this.toIndexArray(0)) {
            const last1 = this.fromIndexArray(--this.size);
            this.fromIndexArray(0) = last1;

            const last2 = this.toIndexArray(this.size);
            this.toIndexArray(0) = last2;
        }

        this.siftDown(0);
        return returnValue;
    },

    this.swap = function(array, index1, index2) {
        const tmp = array(index1);
        array(index1) = array(index2);
        array(index2) = tmp;
    },

    this.isLessThan = function(runIndex1, runIndex2) {
        const element1 = this.array(this.fromIndexArray(runIndex1));
        const element2 = this.array(this.fromIndexArray(runIndex2));
        const cmp = this.cmp(element1, element2);

        if (cmp != 0) {
            return cmp < 0;
        }

        return this.fromIndexArray(runIndex1) < this.fromIndexArray(runIndex2);
    },

    this.siftDown = function(index) {
        let nodeIndex = index;
        let leftChildIndex = (index << 1) + 1
        let rightChildIndex = leftChildIndex + 1;
        let minIndex = index;

        while (true) {
            if (leftChildIndex < this.size 
            && this.isLessThan(leftChildIndex, nodeIndex)) {
                minIndex = leftChildIndex;
            }

            if (rightChildIndex < this.size 
            && this.isLessThan(rightChildIndex, minIndex)) {
                minIndex = rightChildIndex;
            }

            if (minIndex === nodeIndex) {
                return;
            }

            this.swap(this.fromIndexArray, minIndex, nodeIndex);
            this.swap(this.toIndexArray, minIndex, nodeIndex);

            nodeIndex = minIndex;
            leftChildIndex = (nodeIndex << 1) + 1;
            rightChildIndex = leftChildIndex + 1;
        }
    },

    this.buildHeap = function() {
        for (i = Math.floor(this.size / 2); i >= 0; --i) {
            this.siftDown(i);
        }
    },

    this.extendRun = function(length) {
        this.toIndexArray(this.size - 1) += length;
    },

    this.appendRun = function(fromIndex, toIndex) {
        this.fromIndexArray(this.size) = fromIndex;
        this.toIndexArray(this.size) = toIndex;
        this.size++;
    }
}

function reverseRun(array, fromIndex, toIndex) {
    for (i1 = fromIndex, i2 = toIndex; i1 < i2; i1++, i2--) {
        const savedArrayComponent = array(i1);
        array(i1) = array(i2);
        array(i2) = savedArrayComponent;
    }
}

function createRunHeap(array, cmp) {
    let runHeap = new RunHeap(array, cmp);
    let left = 0;
    let right = 1;
    let last = array.length - 1;
    let previousWasDescending = false;

    while (left < last) {
        head = left;
        right = left + 1;

        if (cmp(array(left), array(right)) <= 0) {
            while (left < last && cmp(array(left), array(right)) <= 0) {
                ++left;
                ++right;
            }

            if (previousWasDescending) {
                if (cmp(array(head - 1), array(head)) <= 0) {
                    runHeap.extendRun(right - head);
                } else {
                    runHeap.appendRun(head, right);
                }
            } else {
                runHeap.appendRun(head, right);
            }

            previousWasDescending = false;
        } else { // Scan a descending run:
            while (left < last && cmp(array(left), array(right)) > 0) {
                ++left;
                ++right;
            }

            reverseRun(array, head, left);

            if (previousWasDescending) {
                if (cmp(array(head - 1), array(head)) <= 0) {
                    runHeap.extendRun(right - head);
                } else {
                    runHeap.appendRun(head, right);
                }
            } else {
                runHeap.appendRun(head, right);
            }

            previousWasDescending = true;
        }

        ++left;
        ++right;
    }

    if (left === last) {
        if (cmp(array(last - 1), array(last)) <= 0) {
            runHeap.extendRun(1);
        } else {
            runHeap.appendRun(last, last + 1);
        }
    }

    return runHeap;
}

Array.prototype.heapSelectionSort = 
function(cmp, fromIndex, toIndex) {
    if (!cmp) {
        cmp = (a, b) => a - b;
    }

    if (!fromIndex) {
        fromIndex = 0;
    }

    if (!toIndex) {
        toIndex = this.length;
    }

    RangeCheck(this.length, fromIndex, toIndex);

    if (toIndex - fromIndex < 2) {
        return this;
    }

    const aux = this.slice(fromIndex, toIndex);
    const runHeap = createRunHeap(aux, cmp);
    runHeap.buildHeap();

    let index = fromIndex;

    while (index < toIndex) {
        this(index) = runHeap.popElement();
        index++;
    }

    return this;
};

(You can find the entire demo list here: https://gist.github.com/coderodde/47ae57983954c89ab7bef21b3fa7b232)

Critical inquiry

Since I am not a professional Javascript developer, I would like to equate my code above with the idiomatic JS code.