Sorting Algorithms Quick Rundown

Bubble Sort

  • Runtime: O(n^2)
  • Memory: O(1)
  1. Start at the beginning
  2. Swap the first 2 elements if the first > second
  3. Repeat until the list is sorted
const bubbleSort = array => {
    for (i = 0; i < array.length; i++) {
        for (j = 1; j < array.length; j++) {
            if (array[j - 1] > array[j]) {
                const temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
            }
        }
    }

    return array;
};

Selection Sort

  • Runtime: O(n^2)
  • Memory: O(1)
  1. Find the smallest element using linear scan
  2. Swap the element with the first element
  3. Find the next smallest and swap and so on
const selectionSort = array => {
    for (i = 0; i < array.length; i++) {
        let min = i;
        for (j = i + 1; j < array.length; j++) {
            if (array[j] < array[min]) {
                min = j;
            }
        }
        if (i !== min) {
            const temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }

    return array;
};

Merge Sort

  • Runtime: O(n log(n))
  • Memory: O(n)
  1. Divide the array in half
  2. Sort each of the halves
  3. Merge back together
  • Essentially it comes to sorting 2 elements at a time then merging them
const mergeSort = (array) => {
  if (array.length == 1) {
    return array;
  }

  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
  let result = [];
  let indexLeft = 0;
  let indexRight = 0;

  while (indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] < right[indexRight]) {
      result.push(left[indexLeft]);
      indexLeft++;
    } else {
      result.push(right[indexRight]);
      indexRight++;
    }
  }

  return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight));
};

Quick Sort

  • Runtime: O(n log(n))
  • Worst: O(n^2)
    • The selected element could always be the furthest from being the median, thus it can take longer
  • Memory: O(log(n))
  1. Pick a random element
  2. Partition the array with that element
  3. Partition all elements less than the selected element to the left and the other to the right
  4. Array will eventually become sorted
const quickSort = array => {
    if (array.length <= 1) {
        return array;
    }

    let left = [];
    let right = [];
    let pivot = array.pop();

    for (i = 0; i < array.length; i++) {
        if (array[i] <= pivot) {
            left.push(array[i]);
        } else {
            right.push(array[i]);
        }
    }
    return [].concat(quickSort(left), pivot, quickSort(right));
};

Radix Sort

  • Runtime: O(kn)
  1. Iterate through each digit of the number
  2. Group numbers by each digit
  3. Repeat sorting by each subsequent digit until it’s sorted

Essential Data Structures

Array & String

Hashtables

  • Compute key’s hash code -> Int/long
    • keys can share the same hash
  • Find index of the array
    • hash % array_length
  • Use linkedlist to store key and value at this index

ArrayList & Resizable Arrays

  • Resizing ArrayList takes O(1)
    • Doubling takes O(n) but very rare so its amortized insertion time is still O(1)

StringBuilder

  • Creates a resizable array and copies strings over only when necessary

Stack

Type

  • LIFO (last in first out)\

Functions

  • pop()
    • Remove the top item from the stack
  • push(item)
    • Add an item to the top of the stack
  • peek()/top()
    • Return the top of a stack
  • isEmpty()
    • Return true iff the stack is empty

Runtimes

  • O(1) add/remove
  • O(n) access

Implementation


class Stack {
  constructor(items) {
    this.items = items == null ? [] : items;
  }

  push(data) {
    this.items[this.items.length] = data;
  }

  pop() {
    if (this.items.length === 0) return undefined;

    var removed = this.items[this.items.length - 1];
    // Cannot do
    // delete this.items[this.items.length - 1]
    // Because that will leave the index as undefined instead of removing the index altogether
    this.items.splice(this.items.length - 1, this.items.length);
    return removed;
  }

  peek() {
    if (this.items.length === 0) return undefined;
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

}

Usage

  • Good for certain recursive algorithms
  • Can be used to implement a recursive algorithm iteratively

 

Queue

Type

  • FIFO (first in first out)

Functions

  • add(item)
    • Add an item to the end of the list
  • remove()
    • Remove the first item in the list
  • peek()/top()
    • Return the top of the stack
  • isEmpty()
    • Return true iff the stack is empty

Implementation


class Queue {
  constructor(items) {
    this.items = items == null ? [] : items;
  }

  enqueue(data) {
    return this.items.push(data);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }

  isEmpty() {
    return this.items.length == 0;
  }
}

Usage

  • BFS
  • Implementing cache

 

Linked Lists

  • Sequence of nodes, each points to the next and previous nodes in the list
  • Can add or remove from the beginnning of the list in constant time

Deleting a node

  • Single
    • Set prev.next = n.prev
  • Double
    • Set prev.next = n.prev
    • Set n.next.prev = n.prev

Implementation


class LinkedList {
  constructor(head) {
    this.head = head;
  }

  push(data) {
    var node = new LinkedListNode(data, null);
    var current;
    if (!this.head) {
      this.head = node;
    } else {
      var current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
  }

  remove(data) {
    var current = this.head;

    // Remove the only node in the LinkedList
    if (current.data == data) {
      this.head = current.next;
    } else {
      var prev = current;

      while (current.next) {
        // Remove the node in between the nodes
        if (current.data == data) {
          prev.next = current.next;
          break;
        }
        prev = current;
        current = current.next;
      }

      // Remove last no9de
      if (current.data == data) {
        prev.next == null;
      }
    }
  }
}

class LinkedListNode {
  constructor(data, next) {
    this.data = data;
    this.next = next;
  }

  toString() {
    var node = this;
    var output = String(node.data);
    while (node.next) {
      output = output + " -> " + String(node.next.data);
      node = node.next;
    }

    return output;
  }

}

The “Runner” Technique

  • Have 2 pointers for a linked list that has an even number of length
  • Iterate 1 pointer one by one and iterate the other every other
  • By the time the faster pointer reaches the end, the first pointer will be at the midpoint
  • Iterate backwards and connect these nodes alternatively

Recursive Strategy

  • Takes at least O(n) space
  • All recursive methods can be done iteratively

Trees

Fundamentals

  • Each tree has a root node
  • Has zero or more child nodes
  • Each child node has zero or more child nodes
  • Node is called leaf node if no children

class Node {
  public String name;
  public Node[] children;
}

class Tree {
  public Node root;
}

Trees vs Binary Trees

Tree Binary Tree
No limit on # of children nodes Up to 2 children

Binary Tree vs Binary Search Tree

  • Binary Search Tree follows the rule:
    • all left descendents <= n < all right descendents

Balanced vs Unbalanced

  • Balanced tree implies
    • O(log n) insert
    • O(log n) find
  • Balance tree types
    • red-black tree
    • AVL tree

Complete Binary Tree

  • Every level of the tree is fully filled except for the very last one on the right
  • Trees are filled from left to right

Full Binary Tree

  • Binary tree in which every node has zero or two children
  • No nodes have only one child

Perfect Binary Tree

  • Filled and complete
  • All leaf nodes will be at the same level, and has max number of nodes
  • have 2^k – 1 node (where k is the number of levels)

Binary Tree Traversal

In-Order Traversal

  • visit the left branch, then the current node, then right branch

void inOrderTraversal(TreeNode node) {
  if (node != null) {
    inOrderTraversa(node.left);
    visit(node);
    inOrderTraversal(node.right);
  }
}

Pre-Order Traversal

  • visit the current node before child nodes

void preOrderTraversal(TreeNode node) {
  if (node != null) {
    visit(node);
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
  }
}

Post-Order Traversal

  • visit curren node after its child nodes

void postOrderTraversal(TreeNode node) {
  if (node != null) {
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    visit(node);
  }
}

Binary Heaps (Min-Heaps and Max-Heaps)

  • Complete binary tree where each node is smaller than its children
  • The root is the smallest node
  • functions
    • insert()
      • Start by inserting the element at the bottom at the rightmost spot
      • Then swap the new element with its parent until it’s bigger than the parent node (bubble up)
      • O(log n)
    • extract_min()
      • Min is always the root of the tree
      • Swap the min element with the last node in the heap (bottommost rightmost element)
      • Then swap the node with the smallest between the left or right node
      • Continue until the children nodes are bigger than the node

Tries (Prefix Trees)

  • Prefix tree
  • Variant of an n-ary tree which characters are stored at each node, each path down the tree may represent a word
  • The * nodes (null nodes) indicates complete words.
  • Can have 0 to ALPHABET_SIZE + 1 children
  • Can tell if a string is a prefix of any words very quickly
    • O(K) time – K = length of the string

Graphs

  • Tree is a type of graph
  • tree is a connected graph without cycles

What are graphs

  • Collection of nodes with edges between (some of) them
  • Can be directed or undirected, and can have directed or undirected edges
  • may consist of multiple isolated subgraphs
  • Called connected graph if there’s a path between every pair of vertices
  • Can have cycles
  • Acyclic graph = graph with no cycles

Adjacency List

  • Most common way to rep graphs
  • Every vertex stores a list of adjacent vertices
  • List is stored twice in an undirected graph

class Graph {
  public Node[] nodes;
}

class Node {
  public String name;
  public Node[] children;
}

Adjacency Matrices

  • NxN boolean matric (N = number of nodes)]
  • True at matrix[i][j] indicates an edge from node i to node j
  • Adjacency matrix is symmetric in an undirected graph

Depth-first search (DFS)

  • Go deep before wide
  • Preferred when we want to visit every node in the graph
  • Recursive
  1. Start at the root or an arbitrary node
  2. Expore each branch completely before moving on to the next branch

void search(Node root) {
  if (root == null) return;
  visit(root);
  root.visited = true;
  foreach (Node n in root.adjacent) {
    if (n.visited == false) {
      search(n);
    }
  }
}
  • Go wide before deep
  • Preferred when finding shortest path
  • Uses a Queue
  1. Start at the root or an arbitrary node
  2. Explore each neighbor before going to another node

void search(Node root) {
  Queue queue = new Queue();
  root.marked = true;
  queue.enqueue(root);
  
  while (!queue.isEmpty()) {
    Node r = queue.dequeue();
    visit(r);
    foreach(Node n in r.adjacent) {
      n.marked = true;
      queue.enqueue(n);
    }
  }
}
  • Used to find the shortest path between a source and destination node
  • Runs two simultaneous BFS
  • When their searches collide, the path is found
  • Using 1 BFS search
    • O(k^d)
      • k = number of nodes
      • d = number of times
  • Using 2 BFS search (bidirectional)
    • O(k^(d/2))