jharris-code

function bubbleSort(arr) {
  let swapped = true;
  
  while(swapped){
    swapped = false;
    
    for(let j = 0; j < arr.length - 1; j++){
      if(arr[j] > arr[j+1]){
        swapped = true;
        

jharris-code

function binarySearch(nums, target) {
  let start = 0;
  let end = nums.length - 1;
  let p;
  
  while(start <= end) {
    p = Math.floor((start + end) / 2);
    
    if(nums[p] === target) {
      return p;

jharris-code

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

//Time Complexity: O(N) since we traverse every node worst case
//Space Complexity: O(H) height of tree is number of stack frames in memory

jharris-code

//Assumes: 
//a Queue data structure is available with push(), pop(), isEmpty() methods.
//each node in the Queue have left and right properties.

//Time Complexity: O(N)
//Space Complexity: O(N)
const bfs = (root, value) => {
  let q = new Queue();
  
  q.push(root);

jharris-code

//Time Complexity: O(N log N) - mergeSort is called Log N times, each merge iterates over N elements, so N*(Log N)
//Space Complexity: O(N) - the depth of the call stack is Log N, and each recursive call contains a N/2 copy of the array.
//If you sum up each sub array in the call stack this would be N/2 + N/4 + N/8 + 1 which equals N. 
//If new sub arrays were NOT created in each call, then space requirement would be only for the stack frames, which would be Log N.
const mergeSort = (a) => {
  if(a.length === 1) {
    return a;
  }
  let middle = parseInt(a.length / 2);
  let end = a.length;

jharris-code

//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) => {

jharris-code

//Create a sorted array (ascending) from a max heap
//Time Complexity: O(N log N)
//Space Complexity: O(1) because array is sorted in place
const heapSort = (arr, end) => {
  while(end > 0){
    let tmp = arr[end];
    arr[end] = arr[0];
    arr[0] = tmp;
    end -= 1;
    

jharris-code

//converting an array to a heap is performed with two functions, heapify and siftDown.
//The result is an array representation of a max heap.
//A max heap is required to perform a heap sort. 

//Time Complexity: O(N). Although siftDown is O(log n), the overall runtime is O(N). 
//Good info here on time complexity: https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/
//Space Complexity: O(1) auxiliary space is 0 since the array is converted to a heap in place.
const heapify = (arr) => {

  //end is the last element of the array

jharris-code

let a = [3,1,2,15,4,3,8,8,0];
let c = 0;

//Time Complexity: O(N^2)
//Space Complexity: O(1) because auxiliary space required (above original data set) is 0.
const insertionSort = (arr) => {
  for(let i=0; i < arr.length; i++){
    let j = i;
    
    while(j > 0 && arr[j] < arr[j-1]) {

jharris-code

//Storage: O(V^2)

class Graph {
  //O(V^2)
  constructor(size){
    this.vertices = [];
    for(let i = 0; i < size; i++){
      this.vertices.push([]);
      for(let j = 0; j < size; j++){
        this.vertices[i].push(false);