d3-sort-visualization/js/quicksort.js

/**
 *
 */
var QuickSort = function() {
    var _this = this;

    this.ui = {
        //
        presort: function presort(left, right, pivot, len) {
            _this
                .instruct(Itemgroup.message, 0, 0, 1, 'Comparisons: ' + _this.comparisons)
                .instruct(Itemgroup.message, 0, 0, 2, 'Swaps: ' + _this.swaps)

                .instruct(Itemgroup.opacity, 1, 0, 0, len, 1)
                .instruct(Itemgroup.opacity, 1, 0, -1, left - 1, 0.2)
                .instruct(Itemgroup.opacity, 1, 0, right + 1, len, 0.2)
                .instruct(Itemgroup.background, 1, 0, 0, _this.ordered.length, Visualizer.bg0)

                .instruct(Itemgroup.message, 0, 0, 3, 'Sorting from [' + left + '] to [' + right + ']')
                .instruct(Itemgroup.message, 0, 0, 4, '')
                .instruct(Itemgroup.message, 0, 100, 5, 'Starting sort.');
        },

        //
        highlight: function highlight(arr, left, right, pivot, msg) {
            if (left >= right) {
                return;
            }

            _this
                .instruct(Itemgroup.background, 1, 0, 0, arr.length, Visualizer.bg0)
                .instruct(Itemgroup.background, 1, 0, pivot, pivot, '#435C11')
                .instruct(Itemgroup.background, 1, 0, left, left, '#0C1E42')
                .instruct(Itemgroup.background, 1, 0, right, right, '#7F9EDB')

                .instruct(Itemgroup.message, 0, 0, 1, `Comparisons: ${_this.comparisons}`)
                .instruct(Itemgroup.message, 0, 0, 4, `Pivot at [${pivot}] = ${arr[pivot]}`)
                .instruct(Itemgroup.message, 0, 100, 5, msg)

                // .instruct(Itemgroup.message, 0, 0, 5, msg)
                // .instruct(Itemgroup.message, 0, 100, 1, `Comparisons: ${_this.comparisons}`)
        },

        //
        stop: function stop(arr, left, right, pivot, msg) {
            _this
                .instruct(Itemgroup.background, 1, 0, 0, arr.length, Visualizer.bg0)
                .instruct(Itemgroup.background, 1, 0, pivot, pivot, '#435C11')
                .instruct(Itemgroup.background, 1, 0, left, left, '#0C1E42')
                .instruct(Itemgroup.background, 1, 0, right, right, '#7F9EDB')

                .instruct(Itemgroup.message, 0, 0, 4, `Pivot at [${pivot}] = ${arr[pivot]}`)
                .instruct(Itemgroup.message, 0, 100, 5, msg)
        },

        //
        swap: function swap(left, right) {
            _this
                .instruct(Itemgroup.message, 0, 0, 2, 'Swaps: ' + _this.swaps)
                .instruct(Itemgroup.message, 0, 0, 4, 'Incremement left...')
                .instruct(Itemgroup.message, 0, 0, 5, 'Decrement right...')
                .instruct(Itemgroup.swap, 1, 300, left, right)
        },

        //
        midsort: function midsort(start, end, left, right) {
            _this
                .instruct(Itemgroup.message, 0, 0, 3, 'Left has passed right.')
                .instruct(Itemgroup.message, 0, 0, 4, `Recurse, sort from [${start}]-[${right}]`)
                .instruct(Itemgroup.message, 0, 100, 5, `Recurse, sort from [${left}]-[${end}]`);
        },

        //
        postsort: function postsort() {
            _this
                .instruct(Itemgroup.opacity, 1, 0, 0, _this.ordered.length, 1)
                .instruct(Itemgroup.background, 1, 0, 0, _this.ordered.length, Visualizer.bg0)

                .instruct(Itemgroup.message, 0, 0, 3, 'Sorting complete.')
                .instruct(Itemgroup.message, 0, 0, 4, '')
                .instruct(Itemgroup.message, 0, 0, 5, '');
        },
    }
};

QuickSort.prototype = Object.create(Sorter.prototype);

/**
 *
 */
QuickSort.prototype.init = function() {
    var len = this.shuffled.length;

    this.actions = [];
    this.swaps = 0;
    this.comparisons = 0;

    this
        .instruct(Itemgroup.items, 0, 0, len)
        .instruct(Itemgroup.items, 1, 0, len)
        .instruct(Itemgroup.items, 2, 0, len)

    for (var i = 0; i < len; i++) {
        this.instruct(Itemgroup.text, 1, 0, i, this.shuffled[i]);
    }

    this
        .instruct(Itemgroup.foreground, 1, 0, 0, len, Visualizer.fg0)
        .instruct(Itemgroup.background, 1, 0, 0, len, Visualizer.bg0)

        .instruct(Itemgroup.opacity, 0, 0, 0, len, 0)
        .instruct(Itemgroup.opacity, 2, 0, 0, len, 0)
};

/**
 *
 */
QuickSort.prototype.sort = function(arr, start, end) {
    if (end <= start) {
        this.ui.postsort();
        return arr;
    }

    var left = start;
    var right = end;

    var pivot = Math.floor((right + left) / 2);
    var pivotval = arr[pivot];
    var tmp;
    var rval;

    this.ui.presort(left, right, pivot, arr.length);

    while (left <= right) {
        while (arr[left] < pivotval) {
            this.comparisons++;
            this.ui.highlight(arr, left, right, pivot, `${arr[left]} < ${arr[pivot]}, increment left`);
            left++;
        }

        this.ui.stop(arr, left, right, pivot, `Left stop: ${arr[left]} >= ${arr[pivot]}`);

        while (arr[right] > pivotval) {
            this.comparisons++;
            this.ui.highlight(arr, left, right, pivot, `${arr[right]} > ${arr[pivot]}, decrement right`);
            right--;
        }

        this.ui.stop(arr, left, right, pivot, `Right stop: ${arr[right]} <= ${arr[pivot]} `);

        if (left <= right) {
            tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;

            left++;
            right--;
            this.swaps++;

            this.ui.swap(left - 1, right + 1);
        }
    }

    this.ui.midsort(start, end, left, right);

    this.sort(arr, start, right);
    this.sort(arr, left, end);

    this.ui.postsort();

    return arr;
};