Quicksort for ALPG (http://awal.js.org/alpg/)

alpg-quicksort.js

function getRandomIntInclusive(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function swap(items, firstIndex, secondIndex, transact){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
    
    initialState.swapLeft = firstIndex;
    initialState.swapRight = secondIndex;
    transact();
}

function partition(items, left, right, transact) {
    var pivot   = items[Math.floor((right + left) / 2)],
        i       = left,
        j       = right;


    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }

        while (items[j] > pivot) {
            j--;
        }

        if (i <= j) {
            swap(items, i, j, transact);
            i++;
            j--;
        }
    }

    return i;
}

function quickSort(items, left, right, transact) {
    if (items.length > 1) {
        var index = initialState.index = partition(items, left, right, transact);

        if (left < index - 1) {
            quickSort(items, left, index - 1, transact);
        }

        if (index < right) {
            quickSort(items, index, right, transact);
        }
    }

    return items;
}

function algo(s, transact) {
    quickSort(s.items, s.left, s.right, transact);
}

function render(s, h) {
    return h('div', s.items.map(function (n, idx) {
        var bar = {
            style: { height: '' + n + 'px' }
        };
        
        if (idx == s.index) {
            bar.style.backgroundColor = 'red';
        } else if (idx == s.swapLeft) {
            bar.style.backgroundColor = 'blue';
        } else if (idx == s.swapRight) {
            bar.style.backgroundColor = 'green';
        }
        
        return h('span', bar, '');
    }));
}

var initialState = {
    left: 0,
    right: 29,
    index: -1,
    swapLeft: -1,
    swapRight: -1,
    items: Array(30).fill(0).map(getRandomIntInclusive.bind(null, 10, 100))
};

module.exports = {
    algo: algo,
    render: render,
    initialState: initialState,
    algoName: 'quicksort'
};