Quick Sort

quick_sort.js

//Time Complexity: Worst: O(N^2) - if pivot point is most extreme, and array is already fully sorted, 
//then complexity of partition will be N, then N - 1, then N - 2, etc. Sum up all the N's and this results in N^2
//Average/Best case: O(N Log N) - if pivot point is at the middle then N + (N/2) + (N/4) + (N/8)... = N * (Log N)
//Space Complexity: O(log N) - array is sorted in place, however, stack frames result in Log N recursive calls

let arr = [5,1,9,10,15,7,7,12];

//Time Complexity O(N)
const partition = (low, high) => {

  let pivot = arr[high];
  let i = low - 1;

  //loop through all elements in this set which will be N reduced by X elements each iteration
  for(let j = low; j <= high - 1; j++) {
    //The goal is to move all values LEFT of the pivot value
    //so each time we find a value LESS than pivot, swap it to the LEFT
    //This results in all values less than pivot on left.
    //However, at the end, the pivot value will still be on the far right
    if(arr[j] <= pivot){
      i += 1;

      let tmp = arr[j];
      arr[j] = arr[i];
      arr[i] = tmp;
    }
  }
  
  //This final swap moves the right hand pivot value inbetween the low and high values.
  let tmp = arr[high];
  arr[high] = arr[i + 1];
  arr[i + 1] = tmp;
  return i + 1; //<-- this is the pivot point
}

//Time Complexity: O(2^N)
const quickSort = (low, high) => {
  //if low = high, then we are looking at one element and should exit
  if(low < high){
    //p = the new index of the original partition point which was the last element
    let p = partition(low, high);

    //recursively call for the left and right side, not including the pivot point
    quickSort(low, p - 1);
    quickSort(p + 1, high);
  }
}

quickSort(0, arr.length - 1)
//output: [1,5,7,7,9,10,12,15]
console.log(arr);