Quicksort comparison count for random pivot

quicksort_comparison_count_random_pivot.js

#!/usr/bin/env node
//
// Count the number of comparisons required by quicksort using the following
// three pivot-selection strategies:
//
// 1. Always pick the first element.
// 2. Always pick the last element.
// 3. Pick the median of the first, last, and middle elements. If the list
//    length is even, pick the element with the smaller index.
//
// The comparison count will be incremented by m-1 (where m is the length of the
// subarray being sorted) for each call to quickSort().
//

const fs = require('fs');
const util = require('util');
const file = process.argv[2];

let randomCount = 0;

/**
 * @typedef {string} PivotSelectionStrategy
 */
const PIVOT_SELECTION_STRATEGIES = {
    CHOOSE_FIRST: 'choose first',
    CHOOSE_LAST: 'choose last',
    CHOOSE_MEDIAN: 'choose median of three',
    CHOOSE_RANDOM: 'choose random of list',
};

if (file === undefined) {
    const programFileName = process.argv[1].split('/').pop();
    console.log(`Usage: node ${programFileName} {filename}`);
    process.exit(1);
}

fs.readFile(file, 'utf8', (err, fileContents) => {
    if (err) {
        throw err;
    }
    // const list = fileContents.split('\n').filter(Boolean).map(Number);
    const list = [1, 2];
    // const list = [3, 2, 4, 6, 1, 7, 8, 5];
    // Count comparisons using three distinct pivot selection strategies, and print the results.
    // countComparisons(list.slice(0), PIVOT_SELECTION_STRATEGIES.CHOOSE_FIRST);
    // countComparisons(list.slice(0), PIVOT_SELECTION_STRATEGIES.CHOOSE_LAST);
    // countComparisons(list.slice(0), PIVOT_SELECTION_STRATEGIES.CHOOSE_MEDIAN);
    for (let j = 0; j < 10; j++) {
        list.push(j + 2);
        const startTime = Date.now();
        for (let i = 0; i < 1000000; i++) {
            countComparisons(shuffle(list.slice(0)), PIVOT_SELECTION_STRATEGIES.CHOOSE_RANDOM);
        }
        const endTime = Date.now();
        console.log(`Random average for 1000000 loop with list size of ${list.length}: ${randomCount / 1000000} (${endTime - startTime} ms)`);
        randomCount = 0;
    }
});

/**
 * Given a list of unsorted integers and a pivot selection strategy, count the
 * number of comparisons required to sort the list using quicksort.
 *
 * @param {Array} list - The list of unsorted integers.
 * @param {PivotSelectionStrategy} strategy - The pivot selection strategy.
 */
const countComparisons = (function () {
    const beforeMessage = (size, strategy) => util.format('\nCounting the number of comparisons required to sort list ' +
        'of size %d using "%s" pivot selection strategy...', size, strategy);
    const afterMessage = comparisons => util.format('It took %d comparisons to sort the list.', comparisons);
    const timerLabel = strategy => `count-comparisons--${strategy}`;

    return function (list, strategy) {
        const label = timerLabel(strategy);
        if (strategy !== PIVOT_SELECTION_STRATEGIES.CHOOSE_RANDOM) {
            console.log(beforeMessage(list.length, strategy));
            console.time(label);
        }
        const counter = { comparisons: 0 };
        quickSort(list, 0, list.length - 1, counter, strategy);
        if (strategy !== PIVOT_SELECTION_STRATEGIES.CHOOSE_RANDOM) {
            console.timeEnd(label);
        }
        if (strategy === PIVOT_SELECTION_STRATEGIES.CHOOSE_RANDOM) {
            randomCount += counter.comparisons;
        } else {
            console.log(afterMessage(counter.comparisons));
        }
        return counter.comparisons;
    };
})();

const quickSort = function (list, lo, hi, counter, strategy) {
    if ((hi - lo) < 1) {
        return;
    }
    counter.comparisons += hi - lo;
    const pivotIndex = partition(list, lo, hi, strategy);
    quickSort(list, lo, pivotIndex - 1, counter, strategy);
    quickSort(list, pivotIndex + 1, hi, counter, strategy);
};

const partition = function (list, lo, hi, strategy) {
    const pivotIndex = choosePivotIndex(list, lo, hi, strategy);
    const pivot = list[pivotIndex];
    if (pivotIndex !== lo) {
        swap(list, lo, pivotIndex);
    }
    var i = lo + 1;
    for (var j = i; j <= hi; j++) {
        if (list[j] < pivot) {
            swap(list, i, j);
            i++;
        }
    }
    const finalPivotIndex = i - 1;
    swap(list, lo, finalPivotIndex);
    return finalPivotIndex;
};

const swap = function (list, a, b) {
    const temp = list[a];
    list[a] = list[b];
    list[b] = temp;
};

const choosePivotIndex = function (list, lo, hi, strategy) {
    if (strategy === PIVOT_SELECTION_STRATEGIES.CHOOSE_RANDOM) {
        return Math.floor(Math.random() * (hi - lo)) + lo;
    }
    if (strategy === PIVOT_SELECTION_STRATEGIES.CHOOSE_FIRST) {
        return lo;
    }
    if (strategy === PIVOT_SELECTION_STRATEGIES.CHOOSE_LAST) {
        return hi;
    }
    const middleIndex = Math.floor((hi + lo) / 2);
    const first = list[lo];
    const middle = list[middleIndex];
    const last = list[hi];
    const median = medianOfThree(first, middle, last);
    if (median === first) {
        return lo;
    }
    if (median === middle) {
        return middleIndex;
    }
    return hi;
};

const medianOfThree = function (a, b, c) {
    const min = Math.min(a, b, c);
    const max = Math.max(a, b, c);
    if (min !== a && max !== a) {
        return a;
    }
    if (min !== b && max !== b) {
        return b;
    }
    return c;
};

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;
}

/**
Random average for 1000000 loop with list size of 3: 2.334159 (165 ms)
Random average for 1000000 loop with list size of 4: 4.833968 (251 ms)
Random average for 1000000 loop with list size of 5: 7.565625 (281 ms)
Random average for 1000000 loop with list size of 6: 10.568803 (331 ms)
Random average for 1000000 loop with list size of 7: 13.823106 (399 ms)
Random average for 1000000 loop with list size of 8: 17.30519 (460 ms)
Random average for 1000000 loop with list size of 9: 20.991364 (526 ms)
Random average for 1000000 loop with list size of 10: 24.876246 (593 ms)
Random average for 1000000 loop with list size of 11: 28.94485 (665 ms)
Random average for 1000000 loop with list size of 12: 33.171851 (726 ms)
 */