SortCompares.js

// var a = ['S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E'];
var a = [];

function generateRandomData(limit) {
  const alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
  for (let i = 0; i < limit; i++) {
    let item = alphabet[Math.floor(Math.random() * alphabet.length)];
    a.push(item);
  }
}

generateRandomData(100000);

var a2 = [];

function insertionSort(a) {
  var start = new Date();
  for (var i = 0; i < a.length; i++) {
    for (var f = 0; f < a2.length; f++) {
      if (a[i] <= a2[f]) {
        a2.splice(f, 0, a[i]);
        break;
      } else if (f == (a2.length - 1)) {
        a2.splice(a2.length, 0, a[i]);
        break;
      }
    }
    if (a2.length == 0) {
      a2 = [a[0]];
    }
  }
  var end = new Date();
  var time = end - start;
  console.log('insertionSort total execution time = ' + (time / 1000.00) + ' seconds');
  return a2;
	/*
	insertion sort 
		this uses ~ N^4/4 compares and ~ N^4/4 exchanges on average
		the worst case scenario it uses ~ N^2/2 compares and ~ N^2/2 exchanges
		in the best case scenario it uses N-1 compares and 0 exchanges
		The number of exchanges used by insertion sort is equal to the number of inversions in the array,
		and the number of compares is at least equal to the number of inversions and at most equal to the number of inversions plus the array size minus 1.
	*/
}

console.log("insertion sort running...");
a2 = [];
a2 = insertionSort(a);
console.log("insertion sort complete");

function isSorted(arr) {
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) {
      console.log(arr[i], "is less than", arr[i - 1]);
      return false;
      break;
    }
    return true;
  }
}

function isCorrectLength(a2, a) {
  if (a2.length != a.length) {
    console.log("The length of the arrays are not equal");
    return false;
  } else {
    return true;
  }
}

if (!isSorted(a2) || !isCorrectLength(a2, a)) {
  console.error('Sort failed');
}

function selectionSort(a) {
  var start = new Date();
  for (let i = 0; i < a.length; i++) {
    let f = i;
    let low = f;

    while (f < a.length) {
      if (a[f] > a[low]) {
        low = f;
      }
      f++;
    }
    let tempValue = a[low];
    a.splice(low, 1);
    a.unshift(tempValue);
  }
  var end = new Date();
  var time = end - start;
  console.log('selectionSort total execution time = ' + (time / 1000.00) + ' seconds');
  return a;
	/*
	  Selection sort
	  this uses N^2/2 compares and N exchanges to sort an array of length N.
	  runtime of this on an array that is fully in order is the same as an array that is fully out of order!
	  this is because of the N exchanges
	*/
}
a2 = [];
a2 = selectionSort(a);
console.log("Selection sort complete");

if (!isSorted(a2) || !isCorrectLength(a2, a)) {
  console.error('Sort failed');
}

function shellSort(a, h) {
  var start = new Date();
  while (h > 0) {
    console.log('Shell sort at an h of', h);
    for (let y = 0; y <= h; y++) {
      for (let i = y; i < a.length; i += h) {
        let leftx = a[i];
        let rightx = a[i + h];
        if (rightx !== undefined && rightx < leftx) {
          a.splice(i, 1, rightx);
          a.splice((i + h), 1, leftx);
        }
      }
    }
    h--;
  }
  var end = new Date();
  var time = end - start;
  console.log('shellSort total execution time = ' + (time / 1000.00) + ' seconds');
  return insertionSort(a);
}
a2 = [];
a2 = shellSort(a, 3);
console.log("shellSort sort complete");

if (!isSorted(a2) || !isCorrectLength(a2, a)) {
  console.error('Sort failed');
}