basic sorting algorithm reference

basic_sorting_algorithms.js

let arr = [2, 7, 1, 3, 9, 5, 10, 4, 6, 8];

/*
  Bubble Sort

  Loop through the array comparing each item with the adjacent item. 
  If the item value is less than the item to the left, swap the two items.
  Repeat until you make it through the entire array without swapping any items.

  O(n^2) time complexity worst case
*/

function bubbleSort(arr) {
  let swap = false;
  do {
    swap = false;
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < arr[i - 1]) {
        let tmp = arr[i];
        arr[i] = arr[i - 1];
        arr[i -1] = tmp;
        swap = true;
      }
    }
  } while(swap);
  return arr;
}

bubbleSort(arr);

/*
  Insertion Sort

  Loop through the array picking each element in turn and then
  inserting it at the appropriate place of the already-sorted 
  portion of the array. Start with second item, place it before 
  or after the first depending on value. Then insert the third
  item in the correct place among items one and two by comparing
  to each until you find the first item greater than this item, 
  insert it before that item. Continue until you reach the end 
  of the array.

  Similar to how most people sort a hand of cards.



  Can be more efficient than bubble sort, but still
  O(n^2) worst case
*/


function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[i] < arr[j]) {
        let tmp = arr.splice(i, 1);
        arr.splice(j, 0, tmp[0]);
      }
    }
  }
  return arr;
}

// insertionSort(arr);


/**
 * Merge Sort
 * 
 * Divide and conquer approach. It is a stable sort (as are
 * Bubble and Insertion sort above).
 * 
 * Stitch function can assume that sublists are sorted.
 * Walk the two lists, comparing items from list a to item from
 * list b starting from left and inserting the smaller value. 
 * 
 * O(n log n) time complexity. Space complexity is O(n), so a
 * bit worse than Bubble and Insertion
 * 
 */


function mergeSort(arr) {
  let len = arr.length;
  if (len === 1) {
    return arr;
  }
  let mid = Math.ceil(len / 2);
  let arr1 = arr.slice(0, mid);
  let arr2 = arr.slice(mid);
  arr1 = mergeSort(arr1);
  arr2 = mergeSort(arr2);
  return stitch(arr1, arr2);
}

/**
 * could simplify this using shift instead
 * of only array indices but this theoreticaly
 * could impact perf
 */
function stitch (arr1, arr2) {
  let sortedArray = [];
  let index1 = 0;
  let index2 = 0;
  let len1 = arr1.length;
  let len2 = arr2.length;
  while (index1 < len1 || index2 < len2) {
    if (index1 === len1) {
      sortedArray.push(arr2[index2]);
      index2++;
    } else if (index2 === len2) {
      sortedArray.push(arr1[index1]);
      index1++;
    }
    else if (arr1[index1] < arr2[index2]) {
      sortedArray.push(arr1[index1]);
      index1++;
    } else {
      sortedArray.push(arr2[index2]);
      index2++;
    }   
  }
  return sortedArray;
}


/**
 * QuickSort
 * 
 * Another divide and conquer approach, QuickSort 
 * uses a pivot index to divide the array into two lists.
 * Every item less than pivot value goes into left list,
 * everything greater than pivot value goes into right list,
 * then concatenate left + pivot + right.
 * 
 * One variation is QuickSort 3, which looks at pivots at
 * first, mid, and last position and chooses the value in the 
 * middle - this mitigates against the worst case where the pivot
 * is at the beginning or end of the sorted values.
 * 
 * O(n log(n) often faster than merge sort, but can get n^2
 * in the worst case of an already sorted array. QuickSort is not 
 * stable.
 * 
 */

function quickSort(arr) {
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  
  let pivotIndex = len - 1;
  let pivot = arr[pivotIndex];
  let curr;
  let left = [];
  let right = [];
  for (let i = 0; i < pivotIndex; i++) {
    curr = arr[i];
    if (pivot > curr) {
      left.push(curr);
    } else {
      right.push(curr);
    }
  }
  left = quickSort(left);
  right = quickSort(right);
  return left.concat(pivot, right);
}

// quickSort(arr);