Data Structures and Algorithms
The animations are what set the course apart. Viewer doesn’t have to watch the author type out the code.
Two takeaways from this course. 1.) Which data structure and/or algorithm to use in a given situation. 2.) Write the code, and hour a day for 30 days.
Code Editor: Developer Tools, Three Dots to undock and click on sources tab. Top left hit double arrows icon to view Snippets. Click the play button or Ctrl + Enter on windows to run the snippet.
Ctrl + L clears the dev tools console.
Will come up in an interview and make you a better coder. Mathematically figure out which code is better.
Time and Space complexity. Time complexity is measured in the number of operations.
Three Greek Letters: Theta (average), Omega (best), and Omicron (worst). Omicron always measures the worst case.
O(n) is the easiest to get your head around. Basic for loop. Pass the function a number, n, and it runs, n times. Linear Line on graph.
Simplify with a concept known as “drop constants.” For loop followed by another for loop is n + n which equals 2n but this simplifies to O(n).
For loop nested inside of another for loop is n * n which equals O(n^2)
function logItems(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n, j++) {
console.log(i, j)
}
}
}
logItems(10) // outputs 100 itemsFor loop nested inside of another and a third for loop nested inside that is n * n * N which equals n ^ 3 but this simplifies to O(n^2) as it doesn’t mater if it’s O(n^x) it’s always simplified to n^2.
O(n) is more efficient than O(n^2).
Drop non-dominants is another way we simplify Big O notation. Another for loop comes after a nested for loop. The nested for loop runs O(n^2) and the second for loop runs O(n) times and if you combine these together you get O(n^2 + n) which simplifies down to O(n^2)
O(1) is often referred to as constant time and is the most efficient. Flat line across the bottom of the chart.
// O(1)
function addItems(n) {
return n + n + n + n
}
// equals O(3) operations = O(1)O(log n) is described with an example of a sorted 8-item array to find a number using divide and conquer. How many steps? Log sub 2 of 8 equals 3. How many times to divide by 2 to get to one item. Amazingly powerful when you get very large arrays. Horizontal-ish on the chart above O(1).
O(nlog n) is another Big-O for some sorting algorithms, most efficient you can make a sorting algorithm unless you are sorting only numbers. On the chart this is to the right of O (n^2).
Different terms for inputs. Trick interview question. Passing multiple arguments to a function that has two for loops, (not nested). These arguments are the variables for each for loop. The novice may thing the first loop is O(n) and the second loop is O(n) so that is O(2n) and we’ll drop the constants to be O(n). But you cannot have both variables be equal to n. The first for loop is O(a), or whatever the variable may be and the second for loop is O(b) which simplifies to O(a + b).
// Different terms for inputs
function logItems(a, b) {
for (let i = 0; i < a; i++) {
console.log(i)
}
for (let j = 0; j < b; j++) {
console.log(j)
}
}
// Big O equals O(a + b)
// Nested for loop would be O(a * b)Big O of arrays
Push/pop are O(1) but it’s different on the other end of the array because we need to re-index, (shift and unshift are O(n)). Splice is O(n) since you need to re-index everything after the insert. Removing is also O(n). Finding by value is O(n) but finding by index is O(1).
Summary of the simplifications shown: Drop constants, drop non-dominants.
Words and phrases used with the different types of Big O
O(n^2) is a loop with a loop, O(n) is proportional, O(log n) is proportional, and O(1) is constant.
Classes: Cookie Cutter Analogy
class Cookie {
constructor(color) {
this.color = color
}
getColor() {
return this.color
}
setColor(color) {
this.color = color
}
push(value) {...}
insert(index, value) {...}
unshift(value) {...}
remove(index) {...}
pop() {...}
shift() {...}
}
let cookieOne = new Cookie("green")
let cookieTwo = newCookie("blue")
Pointers:
Example of not using a pointer:
// doesn't use pointers
let num1 = 5
let num2 = num1
// if we later change num1 it does not change num2Example of using a pointer:
let obj1 = {
value: 11
}
let obj2 = obj1
// if we later change obj1 it does change obj2 !!!
obj1.value = 22
console.log(obj2.value)
// result 22The code above says make “obj2” point to the exact same object in memory as “obj1.” These pointers can be moved to a different place. If this results in an object that is not being pointed to it will just be sitting in memory since it is not being used. JS will use “garbage collection” to periodically clean up things like this.
Like arrays but no index. Are also anywhere in memory which is another difference from arrays. Arrays are in a continuous place in memory where linked lists can be all over the place in memory. Has a head and a tail. May be heard referenced as a “null terminated list” since the last node points to null.
Linked Lists Big O push: O(1)
Linked Lists Big O pop: O(n)
Linked Lists Big O unshift: O(1)
Linked Lists Big O shift: O(1)
Linked Lists Big O insert: O(n)
Linked Lists Big O remove: O(n)
Linked Lists Big O find (by value or by index): O(n)
Comparing the above with arrays there are some differences. These differences may make you choose the use of one data structure over another. For example, “pop” for an array is O(1) and lookup by index for an array is also O(1). Shift and unshift are better for Linked Lists O(1) whereas for arrays these are O(n).
Big O Cheatsheet is Awesome
Under the Hood: Node made up of value and the pointer. An object with “value” and “next” keys.
{
head: {
value: 11,
next: {
value: 3,
next: {
value: 23,
next: {
value: 7,
next: {
value: 4,
next: null
}
}
}
}
}
}Before we build out the Linked List we realize that the class itself and other methods will need to create a Node. So instead of repeating this code over and over, we will just create a Node class of its own and then call that when we need a new node object.
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
// to call this use const newNode = new Node(4)class LinkedList {
constructor(value) {
const newNode = new Node(value)
this.head = newNode
this.tail = this.head
this.length = 1
}
}
const myLinkedList = new LinkedList(4)Note: When you call the “new” keyword it is specifically calling the constructor function.
The edge case for “push” is adding a node to a Linked List that doesn’t have any nodes yet.
push(value) {
const newNode = new Node(value)
if(!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++
return this
} // end pushNeed to code “pop” to handle the three cases of no nodes, one node, and multiple nodes. How do we keep track of the node before the end? With “pre” and “temp” variables.
pop() {
if(!this.head) return undefined
let temp = this.head
let pre = this.head
while(temp.next) {
pre = temp
temp = temp.next
}
this.tail = pre
this.tail.next = null
this.length--
if(this.length === 0) {
this.head = null
this.tail = null
}
return temp
} // end pop The “unshift” method is pretty straightforward.
unshift(value) {
const newNode = new Node(value)
if(!this.head) {
this.head = newNode
this.tail = newNode
} else {
newNode.next = this.head
this.head = newNode
}
this.length++
return this
}The “shift” method needs to account for having no items, having multiple items, and having one item. We will need the help of a “temp” variable.
shift() {
if(!this.head) return undefined
let temp = this.head
let head = this.head.next
temp.next = null
this.length--
if(this.length === 0) {
this.tail = null
}
return temp
}get(index) {
if(index < 0 || index >= this.length) {
return undefined
}
let temp = this.head
for(let i = 0; i < index; i++) {
temp = temp.next
}
return temp
}Before coding the “set” method we get a hint that we can use other methods inside of a method.
set(index, value) {
if(index < 0 || index >= this.length) {
return undefined
}
let temp = this.get(index)
if(temp) {
temp.value = value
return true
}
return false
}insert(index, value) {
if(index < 0 || index > this.length) return false
if(index === this.length) return this.push(value)
if(index === 0) return this.unshift(value)
const newNode = newNode(value)
const temp = this.get(index - 1)
newNode.next = temp.next
temp.next = newNode
this.length++
return true
}remove(index) {
if(index < 0 || index >= this.length) return undefined
if(index === this.length - 1) return this.pop()
if(index === 0) return this.shift()
const before = this.get(index - 1)
const temp = before.next
before.next = temp.next
temp.next = null
this.length--
return temp
}Note: In the code above, we could set “temp” to “this.get(index)” but that is O(n) and there is a more efficient operation. So we set “temp” to “before.next”
Being able to reverse a Linked List is a very common interview question. And this is complicated.
Take head and tail and switch them. And then one by one, take the arrows and point them the other way. Notice that there is a gap when we are switching each arrow, and this is the hard part, keeping track of where everything is while introducing all of these gaps, all the way down the Linked List and continue to reverse until it is completely reversed.
We use a “temp” variable that we can set equal to “head” so we can get “head” over to the “tail” and the “tail” over to “temp.”
We will also need something after “temp” called “next” that should point to the next node after “temp” set equal to “temp.next.” We will also have a variable “prev” that we will have before “temp” and initially set it to null. Then we use a “for loop” to move these through the Linked List.
Need “next” variable to help cross the opening and handle an opening being on either side of “temp.”
reverse() {
let temp = this.head
this.head = this.tail
this.tail = temp
let next = temp.next
let prev = null
for(let i = 0; i < this.length; i++) {
next = temp.next
temp.next = prev // what flips the arrow
prev = temp
temp = next
}
return this
}Doubly Linked Lists are the same as Linked Lists but they have an additional arrow that goes the other way. This is represented in the object by adding a “prev” key that is initially set to null in the constructor in the Node class.
Nothing changes in the constructor for the Doubly Linked List compared to the constructor in the Linked List, (the constructor in the Node class is what changes as mentioned above).
class DoublyLinkedList {
constructor(value) {
const newNode = new Node(value)
this.head = newNode
this.tail = this.head
this.length = 1
}
}push(value) {
const newNode = new Node(value)
if(!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
}
this.length++
return this
}DLL: Pop: The “pop” method becomes more efficient with the Doubly Linked List
pop() {
if(this.length === 0) return undefined
let temp = this.tail
this.tail = this.tail.prev
this.tail.next = null
temp.prev = null
this.length--
if(this.length === 0) {
this.head = null
this.tail = null
}
return temp
}The code above isn’t all that readable and we can accomplish the same thing, in a more readable way with some slight changes
pop() {
if(this.length === 0) return undefined
let temp = this.tail
if(this.length === 1) {
this.head = null
this.tail = null
} else {
this.tail = this.tail.prev
this.tail.next = null
temp.prev = null
}
this.length--
return temp
}DLL: Unshift: Write code for no items and items.
unshift(value) {
const newNode = new Node(value)
if(this.lengthv === 0) {
this.head = newNode
this.tail = newNode
} else {
newNode.next = this.head
this.head.prev = newNode
this.head = newNode
}
this.length++
return this
}DLL: Shift: Write code for no items, q item, and two or more items
shift() {
if(this.length === 0) return undefined
let temp = this.head
if(this.length === 1) {
this.head = null
this.tail = null
} else {
this.head = this.head.next
this.head.prev = null
temp.next = null
}
this.length--
return temp
}DLL: Get: Similar to the “get” method for Linked List but since we have “prev” and “next” we can start at the “tail” if we can get to the index in less steps by doing so. So we put a “for loop” that starts at the “head” inside and “if check” that test whether the index is less than half of the length minus one. In an “else block” we can have a second “for loop” that starts with the “tail.”
get(index) {
if(index < 0 || index >= this.length) return undefined
let temp = this.head
if(index < this.length / 2) {
for(let i = 0; i < index; i++) {
temp = temp.next
}
} else {
temp = this.tail
for(let i = this.length - 1; i > index; i--) {
temp = temp.prev
}
}
return temp
}DLL: Set:
set(index, value) {
let temp = this.get(index)
if(temp) {
temp.value = value
return true
}
return false
}Note: This is exactly the same method as in the Linked List. The only difference is that the “get method” it leverages is written differently. Because the “get method” is more efficient, this “set method” is now more efficient as well.
Insert: Need “before” and “after” variables. Rember trcik to keep “after” O(1) instead of O(n)
insert(index, value) {
if(index < 0 || index >= this.length) return undefined
if(index === 0) return this.unshift(value)
if(index === this.length) return this.push(value)
const newNode = new node(value)
const before = this.get(index - 1)
const after = before.next
before.next = newNode
newNode.next = after
newNode.prev = before
after.prev = newNode
this.length++
return this
}Remove: Since we have a Doubly Linked List, we don’t need a “prev” variable at all, one “temp” variable will do the trick.
remove(index) {
if(index < 0 || index >= this.length) return undefined
if(index === 0) return this.shift()
if(index === this.length - 1) return this.pop()
let temp = this.get(index)
temp.previous.next = temp.next
temp.next.previous = temp.prev
temp.next = null
temp.prev = null
this.length--
return temp
}Stacks
A Stack is just like a Linked List and a good example of a Stack is a can of tennis balls. Stacks are LIFO. We add and remove from the same end.
A common way to implement a Stack is with an Array. With a Stack we add and remove from the same end and it doesn’t matter which end you choose as long as it is the same end. We won’t use an Array because it is built in to JavaScript and that would be too easy.
If you do implement a stack with an Array it does matter which end you use. When you add or remove to an end of an Array this is O(1). If you do it from the other end, you have to re-index all items when you add or remove making it a less efficient, O(n).
So if you are implementing a stack with an array you always want to do it with the end and not the beginning. An easy way to remember this is that you “push on and pop off” of a stack and these are the methods used with the end of an Array.
We will implement a stack by altering a Linked List. Unlike an Array, when you create a stack with a Linked List, we always use the left side as the top. This keeps the “null-terminated” end at the bottom.
The reason for this is when you remove an item from the end/tail of a Linked List this is O(n) and when you add an item to the end/tail this is O(1). On the left/head/begining of the Linked List, when you add and remove items these are both O(1) operations. So we can use the “shift” and “unshift” methods for a Linked List to help us create the methods of “push” and “pop,” with slight alterations, for our stack.
We also rename the “head” and “tail” to be “top” and “bottom” and we actually don’t even need the “bottom.”
The “Node” class from the Linked List is exactly the same.
We can also take some other things from the Linekd List.
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
class Stack {
constructor(value) {
const newNode = new Node(value)
this.top = null
this.length = 1
}
}Stack: Push
push(value) {
const newNode = new Node(value)
if(this.length === 0) {
this.top = newNode
} else {
newNode.next = this.top
this.top = newNode
}
this.length++
return this
}Stack: Pop
pop() {
if(this.length === 0) return undefined
let temp = this.top
this.top = this.top.next
temp.next = null
this.length--
return temp
}Queue
Queues are like standing in line and are FIFO.
Can use an Array for a Queue. It doesn’t matter which end you use as long as the enqueue/dequeue operations happen at opposite ends. One end will be O(n) and one end will be O(1).
When creating a Queue with Linked Lists you want to enqueue/dequeue from a specific end. This is because adding or “pushing” an item onto the “tail” end is O(1) and removing or “popping” an item from the “tail” end is O(n). On the “left/head” end both of the “shift/unshift” methods are O(1).
So when we create a Queue from a Linked List we don’t want to “dequeue” from the tail end since that is O(n). Instead we want to “dequeue” from the left “head” end and enqueue from the “right/tail” end. This will keep both operations at O(1).
We also rename “head” and “tail” to “first” and “last.”
class Node () {
constructor(value) {
this.value = value
this.next = null
}
}
class Queue {
constructor(value) {
const newNode = new Node(value)
this.first = newNode
this.last = newNode
this.length = 1
}
enqueue(value) {
const newNode = new Node(value)
if (this.length === 0) {
this.first = newNode
this.last = newNode
} else {
this.last.next = newNode
this.last = newNode
}
this.length++
return this
}
dequeue() {
if (this.length === 0) return undefined
let temp = this.first
if (this.length === 1) {
this.first = null
this.last = null
} else {
this.first = this.first.next
temp.next = null
}
this.length--
return temp
}
} // Closes Queue ClassTerminology for Trees: full, perfect, complete, parent, children, leafs.
Binary Search Tree example
class Node {
constructor(value) {
this.value = value
this.left = null
this.right = null
}
}
class BST {
constructor() {
this.root = null
}
insert(value) {
const newNode = new Node(value)
if (this.root === null) {
this.root = newNode
return this
}
let temp = this.root
while(true) {
if (newNode.value === temp.value) return undefined
if (newNode.value < temp.value) {
if (temp.left === null) {
temp.left = newNode
return this
}
temp = temp.left
} else {
if (temp.right === null) {
temp.right = newNode
return this
}
temp = temp.right
}
} // Closes while loop
} // Closes insert method
contains(value) {
if (this.root === null) return false
let temp = this.root
while (temp) {
if(value < temp.value) {
temp = temp.left
} else if (value > temp.value) {
temp = temp.right
} else {
return true
}
}
return false
} // Closes contains method
} // Closes BST classExample of building an inventory for a hardware store using “key/value pairs.”
class HashTable {
constructor(size = 7) {
this.dataMap = new Array(size)
}
_hash(key) {
let hash = 0
for (let i = 0; i < key.length; i++) {
hash = (hash + keycharCodeAt(i) * 23) % this.dataMap.length
}
return hash
} // end _hash method
set(key, value) {
let index = this._hash(key)
if(!this.dataMap[index]) {
this.dataMap[index] = []
}
this.data[index].push([key, value])
return this
} // end set method
get(key) {
let index = this._hash(key)
if(this.dataMap[index]) {
for(let i = 0; i < this.dataMap[index].length; i++) {
if(this.dataMap[index][i][0] === key) {
return this.dataMap[index][i][1]
}
}
}
return undefined
} // end get method
keys() {
let allKeys = []
for(let i = 0; i < this.dataMap.length; i++) {
if(this.dataMap[i]) {
for(let j = 0; j < this.dataMap[i]; j++) {
allKeys.push(this.dataMap[i][j][0])
}
}
}
return allKeys
} // end keys method
} // end HashTable classCommon interview question for hash tables: Some variation of “write a formula to see if two given arrays have any items in common.”
Implementation #1 is to have nested “for loops” but this makes the big O of this implementation O(n^2), which is very inefficient:
function itemInCommon(arr1, arr2) {
for(let i = 0; i < arr1.length; i++) {
for(let j = 0; j < arr2.length; j++) {
if(arr1[i] === arr2[j]) return true
}
}
return false
}
let array1 = [1, 3, 5]
let array2 = [2, 4, 5]
itemInCommon(array1, array2) // returns trueSo the above code works but it’s not very efficient. Instead we will use an object (JavaScript’s built-in hash table) to loop through the first array and for each of the numbers, add to an object as a key with a value of true. Then just loop through the second array and say “is 2 in this object as a key?” and this is an O(1) operation and makes this second implementation O(n) overall and more efficient than implementation #1. Now the number of operations is far less and we went through each array only one time.
function itemInCommon(arr1, arr2) {
let obj = {}
for(let i = 0; i < arr1.length; i++) {
obj.[arr1[i]] = true
}
for(let j = 0; j < arr2.length; j++) {
if (obj[arr2[j]]) return true
}
return false
}Note: in the code above we are setting and assessing a key/property on an object with a variable, so bracket notation must be used for this to work.
Terminology: Vertex (although will hear called a node sometimes). Connect two vertex with an “edge” but you will also here it called a “connection.”
We can “weight” edges, (maybe to represent traffic).
Can have “bi-directional” edges (represented without edges). An example would be you and a friend following each other on a social network.
Can have “uni-directional” edges (represented with arrows). An example would be you following a celebrity.
“Linked Lists” and “Trees” are types of “Graphs”
Adjacency Matrix: X axis is vertex and Y Axis is what it points to or not represented by a 1 or 0. 45 degree line of zeroes in adjacency matrix. if the graph has all “bi-directional” connections the matrix will be symmetrical across that 45 degree line. If the edges are weighted we can store the weights in the graph instead of a 1.
With an Adjacency Matrix, you store the zeroes along with the 1 so this gets very inefficient as the numbers become very large, (example of a company with billions of users).
Adjacency List: Stored in object. Represent vertex as “key” with “value” set to an Array of edges set as Strings. More efficient and simpler to code.
Big O of Graphs:
Space Complexity with Adjacency Matrix very inefficient, O( |v|^2)
Space Complexity with Adjacency List more efficient, O( |V|+|E| )
Time Complexity with Adjacency Matrix adding a vertex, O(|v|^2)
Time Complexity with Adjacency List adding a vertex, O(1)
Time Complexity with Adjacency Matrix adding an edge, O(1)
Time Complexity with Adjacency List adding an edge, O(1)
Time Complexity with Adjacency Matrix removing an edge, O(1)
Time Complexity with Adjacency List removing an edge, O( |E| )
Time Complexity with Adjacency Matrix removing a vertex, O( |V|^2 )
Time Complexity with Adjacency List removing a vertex, O( |V|+|E| )
class Graph {
constructor() {
this.adjacencyList = {}
}
addVertex(vertex) {
if(!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = []
return true
}
return false
}
addEdge(vertex1, vertex2) {
if(this.adjacencyList[vertex1] &&
this.adjacencyList[vertex2]
) {
this.adjacencyList[vertex1].push(vertex2)
this.adjacencyList[vertex2].push(vertex1)
return true
}
return false
} // end addEdge method
removeEdge(vertex1, vertex2) {
if(this.adjacencyList[vertex1] &&
this.adjacencyList[vertex2]
) {
this.adjacencyList[vertex1] = this.adjacencyList[vertex1]
.filter(v => v !== vertex2)
this.adjacencyList[vertex2] = this.adjacencyList[vertex2]
.filter(v => v !== vertex2)
return true
}
return false
} // end removeEdge method
removeVertex(vertex) {
if(!this.adjacencyList[vertex]) return undefined
while(this.adjacencyList[vertex].length) {
let temp = this.adjacencyList[vertex].pop()
this.removeEdge(vertex, temp)
}
delete this.adjacencyList[vertex]
return this
}
} // end GraphA function that calls itself…until it doesn’t
Gift box example: Get a present or another gift box
// pseudo code only; do not run code
function openGiftBox() {
if (isBall) return ball
openGiftBox()
}Two keys rules: 1.) Have to have a base case. The process of whatever you are doing has to be the same, (opening each new box is the same), and 2.) each time we call a function on itself, it needs to be working on a smaller and smaller problem, open a box we make the problem smaller.
Have to have an “if statement,” or some conditional, that when some condition is true, the code will stop running. If not you will face an infinite loop or a “stack overflow.”
Also have to have a “return” statement! A “console.log” will not cut it.
Some key mistakes include having an if statement that is never true.
The call stack:
We used a tennis ball example
Example with non-recursive code first: Three functions that console log the number of the function.
function funcThree() {
console.log('Three')
}
function funcTwo() {
funcThree()
console.log('Two')
}
function funcOne() {
funcTwo()
console.log('One')
}
funcOne()The code above logs three, then two, then one. We add function one two and three to the call stack but we need to wait for three run before we can remove from the call stack and run function two and the same thing happens. So we see the log in the console three two and then one.
Click the left arrow in the top right corner of the dev tools to see the debugger. Collapse everything but the Call Stack and Breakpoints tab. Clicking the number to the left of the code creates a breakpoint. Now when you hit the “play” button to “run snippet” the line will be highlighted green and now we can step through the code line by line (by hitting right arrow with dot).
factorial: Any course that talks about recursion will use factorial as an example
4! = 4 * 3 * 2 * 1
function factorial(n) {
if(n === 1) return 1
return n * factorial(n-1)
}Can check out in the chrome dev tools debugger and see only the word factorial on the call stack but if you click the word in the call stack you will see n = 3 or whichever number corresponds.
Factorials grow incredibly fast so it’s a fun function to play around with.
Bubble Sort: The easiest of the sorting algorithms covered.
Since the highest value is bubbled to the top, the array you are sorting gets smaller and smaller in size and this is represented by having the outer loop decrement.
function bubbleSort(array) {
for(let i = array.length -1; i > 0; i--) {
for(let j = 0; j < i; j++) {
if(array[j] > array[j+1]) {
let temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
}
}
}
return array
}Selection Sort: Have to keep track of the indexes. Store in a “min” variable, the index of the lowest item in the array. After looping through the array comparing items, updating the min variable as necessary, use this “min” variable to switch with the comparison item.
function selectionSort(array) {
let min
for (let i = 0; i < array.length -1; i++) {
min = i
for (let j = i+1; j < array.length; j++) {
if(array[j] < array[min]) min = j
}
if(i !== min) {
let temp = array[i]
array[i] = array[min]
array[min] = temp
}
}
return array
}Insertion Sort: Always starts with the second item and you compare it to the item before it. If it is less than the item before it we switch them and then compare it to the item before that.
function insertionSort(array) {
let temp
for(let i = 1; i < array.length; i++) {
temp = array[i]
for(var j = i - 1; array[j] > temp && temp && j > -1; j--) {
array[j+1] = array[j]
}
array[j+1] = temp
}
return array
}Notice that the variable “i” starts at the second item via the index of one.
Note: We use the “var” keyword because we need to use the “j” variable outside of the “for loop.”
Also note: another example of decrement used in the loop.
I am always confused with code like “array[j+1] = array[j]” as my brain thinks it is overriding/overwriting what is already there. And that’s because it is. And I get that that’s why we have this “temp” variable, to keep a a copy of the working item, array[i], so when it it overwritten we still have it’s value. But whereas the author refers to it as “dropping in an open spot” I don’t see an open spot. And that’s because there isn’t one. It is still whatever the value of array[j] was. Then j is decremented, and the value of array[j] pre-decrement is then overwritten by the line “array[j+1] = temp.” The “open spot” verbiage was causing confusion for me.
Big O for Insertion Sort
A “for loop inside of a for loop” so its O(n^2). With “almost sorted” data you may only loop through once, making this O(n), and faster than even merge sort and quick sort.
Merge sort is our first sorting algorithm that leverages recursion. Leverages the idea that “merging” two sorted arrays is fairly easy.
Merge Sort cuts arrays in half, and then cuts them in half again, and then again, until we have “single item arrays.” Then we take two of them and combine them into one larger sorted array. And then we do it again and again until we have one sorted array.
It looks inefficient but it is actually incredible efficient; in fact, as efficient as you can make a sorting algorithm.
We use a function “merge” that is a helper function we will use in the “Merge Sort” function. It basically says look at both arrays, assuming they have items and are already sorted, and add the appropriate item to a new sorted and combined array.
function merge(array1, array2) {
let combined = []
let i = 0
let j = 0
while(i < array1.length && j < array2.length) {
if(array1[i] < array2[j]) {
combined.push(array1[i])
i++
} else {
combined.push(array2[j])
j++
}
}
while(i < array1.length) {
combined.push(array1[i])
i++
}
while(j < array2.length) {
combined.push(array2[j])
j++
}
return combined
}The big thing Merge Sort does it break things in half. The “putting it back together” is what the helper “merge” function code above is for.
Two things required in recursion is a smaller and smaller problem, (here we have arrays being broken in half). Also need a base case (here that is when array.length is 1). Then we will use merge() to put arrays together.
function mergeSort(array) {
if(array.length === 1) return array
let mid = Math.floor(array.length/2)
let left = array.slice(0, mid)
let right = array.slice(mid)
return merge(mergeSort(left), mergeSort(right))
}Note: What about when there is an odd-numbered array? A non-issue, “Math.floor” rounds down, the extra item will be in the second array. For example, 7/2 = 3.5 = 3 so the first array has three items and the second array has four items.
Merge Sort Big O
Big O for Space Complexity: As you break down the original array in half you actually created two new arrays doubling the memory usage. If you originally had 8 items in an array, and broke down to 8 single-item-arrays, that is O(n).
Big O Time Complexity: When you break them down you have (say 8 items broken down in 3 steps) you have a O(log n) operation. But when you put them back together that is a O(n) operation. So these steps together we have O(n log n).
On the Big O notation graph O(n log n) looks similar to O(n^2) but it is a little to the right, so better thank O(n^2).
When it comes to sorting algorithms, O(n^2) and O(n log n) are pretty much your two options. There are some exceptions with sorting algorithms that sort only numbers because there are some efficiencies with just numbers.
We make the first item a “pivot point” and we compare each item to the pivot point. If we find an item that is less than the pivot we exchange places, not with the pivot, but the first item after the pivot that is greater than the pivot. We continue this until all items in the array have ben compared to pivot. At this point all items lower than pivot are near the front of the array (but still to the right of the pivot). We then swap pivot with the last of those smaller items. The pivot is now sorted (likely into the middle) at this point. We then run the “Quick Sort” function again just for the items on the left of the pivot. And then we run the “Quick Sort” function again just for the items on the right. We continue with this until all items in the array are sorted.
We define “swap” and “pivot” as helper functions for a “Quick Sort” function.
function swap(array, firstIndex, secondIndex) {
let temp = array[firstIndex]
array[firstIndex] = array[secondIndex]
array[secondIndex] = temp
}
function pivot(array, pivotIndex=0, endIndex=array.length-1) {
let swapIndex = pivotIndex
for(let i = pivotIndex + 1; i <= endIndex; i++) {
if(array[i] < array[pivotIndex]) {
swapIndex++
swap(array, swapIndex, i)
}
}
swap(array, pivotIndex, swapIndex)
return swapIndex
}
Note: only need to pass the “pivot” function an array since the other two parameters have defaults. They are needed because we are going to run a function on a subset of the array and will need the first and last index of the subset.
function quickSort(array, left=0, right=array.length-1) {
if(left < right) {
let pivotIndex = pivot(array, left, right)
quickSort(array, left, pivotIndex-1)
quickSort(array, pivotIndex+1, right)
}
return array
}Note: similar to pivot, you only need to pass the “quickSort” function an array.
Big O of Quick Sort for Space Complexity: We don’t create any new items here so we are not duplicating any data so we are O(1). This is an advantage over Merge Sort which has a space complexity of O(n). Note that the Big-O Cheatsheet has the space complexity of Quick Sort at O(log n) and not O(1). Still better than merge sort.
Big O of Quick Sort for Time Complexity: In order to move all of these items around, this is O(n) because we have a “for loop” that goes all the way through to the end. But we have to do this multiple times, O(log n). So when we combine them together we have O(n log n), which is better than O(n^2), but this is only the best case for Quick Sort.
The worst case, which is what big O measures, is not O(n log n) but O(n^2). The worst case happens if you have an “already-sorted” data. Ironically, if you have sorted, or almost sorted data, this is not a good algorithm. It is an excellent sorting algorithm for random data.
Traversing is going through each item. Two broad categories: Breadth First Search and Depth First Search.
Breadth First Search:
Steps: Start at the top and fill across each row, move lower until you have completed. We use two arrays (queue and results) to accomplish our task. The “queue” array gets the entire node where the “results” array gets just the value.
BFS() {
let currentNode = this.root
let queue = []
let results = []
queue.push(currentNode)
while(queue.length) {
currentNode = queue.shift()
results.push(currentNode.value)
if(currentNode.left) queue.push(currentNode.left)
if(currentNdoe.right) {queue.push(currentNode.right)}
}
return results
}Note: The BFS function is a method that should be part of the Binary Search Tree (BST) class as seen in Section 7.
Depth First Search:
Three types of Depth First Search: PreOrder, PostOrder, InOrder
DFS PreOrder:
We write the root to the array first.
DFSPreOrder() {
let results = []
function traverse(currentNode) {
results.push(currentNode.value)
if(currentNode.left) traverse(currentNode.left)
if(currentNode.right) traverse(currentNode.right)
}
traverse(this.root)
return results
}DFS PostOrder:
We write the root to the array last.
DFSPostOrder() {
let results = []
function traverse(currentNode) {
if(currentNode.left) traverse(currentNode.left)
if(currentNode.right) traverse(currentNode.right)
results.push(currentNode.value)
}
traverse(this.root)
return results
}When you compare post order to pre order, in pre order we wrote the root to the array first while in post order we write the root to the array last.
DFS InOrder:
We write the lowest (bottom-left-most) to the array first and goes from lowest to highest.
Always go to the left first and when it cannot go left we write it to the array. And the we try to go right. If we can’t then we go up and write that value, and then try to go right.
DFSInOrder() {
let results = []
function traverse(currentNode) {
if(currentNode.left) traverse(currentNode.left)
results.push(currentNode.value)
if(currentNode.right) traverse(currentNode.right)
}
traverse(this.root)
return results
}Summary Note for DFS Methods:
It is really only the order of the three lines in the traverse function inside of each of these three methods that sets them apart.