Sorting Algorithm Practice - July 2020

sortingAlgos.js

const smArr = [8, 3, 5, 1, 4, 2];
const sortedSmArr = [1, 2, 3, 4, 5, 8];

//source: https://stackoverflow.com/questions/5836833/create-an-array-with-random-values
for (var lgArr=[],i=0;i<40;++i) lgArr[i]=i;

function shuffle(array) {
  var tmp, current, top = array.length;
  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }
  return array;
}
lgArr = shuffle(lgArr);
const sortedLgArr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39];

//source: https://stackoverflow.com/questions/3115982/how-to-check-if-two-arrays-are-equal-with-javascript
function arraysEqual(a, b) {
  if (a === b) return true;
  if (a == null || b == null) return false;
  if (a.length !== b.length) return false;

  for (var i = 0; i < a.length; ++i) {
    if (a[i] !== b[i]) return false;
  }
  return true;
}
//https://www.freecodecamp.org/news/sorting-algorithms-explained-with-examples-in-python-java-and-c/
//Insertion - best for small # of elements
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
     arr[j + 1] = arr[j];
     j--
    } 
    arr[j + 1] = key;
  }
  
  return arr;
}

//Selection sort - N(N-1)/2, find smallest element, swap into 0, 
// second smallest, swap into 1, so on... 

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let j_min = i;
    
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[j_min]) {
        j_min = j;
      }
    } 
    
    if (j_min !== i) {
      let temp = arr[i];
      arr[i] = arr[j_min];
      arr[j_min] = temp;
    }
  }

  return arr;
}

//Bubble sort - O(n^2), small arrays or comps with limited memory
//Look at two at a time and swap if not in order
function bubbleSort(arr) {
  let sorted = false;
  
  while(!sorted) {
    sorted = true;
    
    for (let i = 0; i < arr.length; i++) {
      if (arr[i - 1] > arr[i]) {
        let temp = arr[i];
        arr[i] = arr[i - 1];
        arr[i - 1] = temp;
        sorted = false;
      }
    }
  }
  
  return arr;
}

//Quick Sort - O(nlog(n)) - can grow to O(n^2) if pivot on arrays of unequal
//sizes, pivot on last/first el, lesser els to left/greater to right,
//recursively sort them
//Not stable, but in place (less memory), good for 
//smaller arrays
function quickSort(arr) {
  if (arr.length <= 1) return arr
  else {
    let p = arr.slice(-1), left = [], right = [];
  
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] <= p) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    let sortedLeft = quickSort(left);
    let sortedRight = quickSort(right);

    return sortedLeft.concat(p, sortedRight);
  }   
}

//Merge Sort - O(nlog(n)) - divide in half/recursively
//sort them, good for linked lists/large datasets,
//requires more memory than QS as it's not in place,
//stable
//https://www.geeksforgeeks.org/quick-sort-vs-merge-sort/
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  let mid = Math.floor(arr.length/2);
  
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  
  return merge(left, right);
}

function merge(a, b) {
  let sorted = [];
  
  while (a.length && b.length) {
    sorted.push(a[0] > b[0] ? b.shift() : a.shift())
  }
  
  return sorted.concat(a.length ? a : b);
}

const tester = {
  1: { test: "smArr should be sorted:", val: smArr, ans: sortedSmArr },
  2: { test: "lgArr should be sorted:", val: lgArr, ans: sortedLgArr }
}

Object.keys(tester).forEach(key => {
//   console.log("Insertion sort test: --------")
//   console.log(tester[key]["test"])
//   console.log(arraysEqual(insertionSort(tester[key]["val"]), tester[key]["ans"]))
//   console.log("Selection sort test: --------")
//   console.log(tester[key]["test"])
//   console.log(arraysEqual(selectionSort(tester[key]["val"]), tester[key]["ans"]))
//   console.log("Bubble sort test: --------")
//   console.log(tester[key]["test"])
//   console.log(arraysEqual(bubbleSort(tester[key]["val"]), tester[key]["ans"]))
//   console.log("Quick sort test: --------")
//   console.log(tester[key]["test"])
//   console.log(arraysEqual(quickSort(tester[key]["val"]), tester[key]["ans"]))
  console.log("Merge sort test: --------")
  console.log(tester[key]["test"])
  console.log(arraysEqual(mergeSort(tester[key]["val"]), tester[key]["ans"]))
});