Count the number of comparisons required by quicksort to sort a list of numbers using three distinct pivot selection strategies: choose first, choose last, and choose median of three.

count-comparisons.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];

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

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

/**
 * 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);
    console.log(beforeMessage(list.length, strategy));
    console.time(label);
    const counter = {comparisons: 0};
    quickSort(list, 0, list.length - 1, counter, strategy);
    console.timeEnd(label);
    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_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;
};