- Definitions:
Online: It works even if you add an e to the end of the list midway through the algoStable: Equal elements are sorted in the same order they appear
Bubble Sort O(n^2)
- Compare e1 with e2, and swap if e1 > e2
- After that, the rightmost e will be at its correct place
- Repeat the process n times
- Stable, InPlace
# Each iteration bubbles the greatest value to the top
def bubbleSort(arr):
for end_idx in range(len(arr), 1, -1):
idx = 1
while idx < end_idx:
if arr[idx] < arr[idx-1]:
temp = arr[idx]
arr[idx] = arr[idx-1]
arr[idx-1] = temp
idx += 1
return arrSelection Sort O(n^2)
- Swap leftmost e with min e of the rest of the list
- After that, the leftmost e will be at its correct place
- Repeat the process n times
- InPlace
# Swap smallest value with current index at each iteration
def selectionSort(arr):
def getMinIdx(start):
idx = 0
_min = float('inf')
for i, n in enumerate(arr[start:]):
if n < _min:
_min = n
idx = i
return (idx + start, _min)
for i in range(len(arr)-1):
min_idx, _min = getMinIdx(i+1)
if arr[i] > _min:
arr[min_idx] = arr[i]
arr[i] = _min
return arrInsertion Sort O(n^2)
- Maintain a running index of list
- For each e at the index, place it in its correct position wrt the left side of the list
- Increment the index and repeat process
- Online, Stable, InPlace
- Good for use cases that have almost sorted and dynamic lists
# Insert value at its correct position on the left side of the array
# This is the only one that is stable!
def insertionSort(arr):
def insert(end_idx, val):
for i in range(0, end_idx):
if val < arr[i]:
arr.insert(i, val)
return
arr.insert(end_idx, val)
for i in range(1, len(arr)):
val = arr.pop(i)
insert(i, val)
return arrMerge Sort O(nlogn)
- Split list into two
- Sort both halves
- Merge the sorted halves (External Sort style)
- Stable
- Takes up O(n) Aux Space unless dealing with a linked list
- Same concept as External Sort
# Split array into half and sort each half recursively before merging the sorted halves together
def mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr)//2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
result = []
left_idx = right_idx = 0
while left_idx < len(left) and right_idx < len(right):
if left[left_idx] > right[right_idx]:
result.append(right[right_idx])
right_idx += 1
elif right[right_idx] > left[left_idx]:
result.append(left[left_idx])
left_idx += 1
else:
result.append(left[left_idx])
result.append(right[right_idx])
left_idx += 1
right_idx += 1
if left_idx < len(left):
result.extend(left[left_idx:])
if right_idx < len(right):
result.extend(right[right_idx:])
return resultQuick Sort O(n^2)
- Choose a pivot, put smaller elements on left, large elements on right
- Either recursively sort both sides or repeat for resulting list excluding the previous pivot
- InPlace
- Perferred over Merge Sort when dealing with large arrays because it is InPlace, and also if the array is partially sorted and pivot is chosen well
# Pivot! Choose a pivot (last element is simplest) and swap elements such that
# the smaller ones are on the left and larger ones are on the right of the pivot,
# and then call quickSort on the left and right sublists.
def quickSort(arr):
# Assumes only 1 CPU core (ignores concurrency issues)
def _quickSort(left_limit, right_limit):
if left_limit >= right_limit:
return
pivot = arr[right_limit]
left_idx = 0
right_idx = right_limit-1
while True:
while arr[left_idx] < pivot:
left_idx += 1
while arr[right_idx] >= pivot:
right_idx -= 1
if left_idx > right_idx:
break
if left_idx > right_idx:
arr[right_limit] = arr[left_idx]
arr[left_idx] = pivot
_quickSort(0, left_idx-1)
_quickSort(left_idx+1, right_limit)
return
else:
temp = arr[left_idx]
arr[left_idx] = arr[right_idx]
arr[right_idx] = temp
_quickSort(0, len(arr)-1)
return arr- Heapify the list (max heap, binary tree structure, O(logn), can be represented by the list itself)
- Swap the top e (max) with the bottom e
- Consider the sublist (without the max value) and repeat
# Heapify an array, extract the largest/smallest element, and then repeat.
def heapSort(arr):
import heapq
result = []
while len(arr) > 1:
heapq.heapify(arr)
result.append(heapq.heappop(arr))
result.append(arr[0])
return resultarr = [12, 45, 78, 34, 56, 0, -56, -98, -98, 45]
assert bubbleSort(arr) == [-98, -98, -56, 0, 12, 34, 45, 45, 56, 78]
assert selectionSort(arr) == [-98, -98, -56, 0, 12, 34, 45, 45, 56, 78]
assert insertionSort(arr) == [-98, -98, -56, 0, 12, 34, 45, 45, 56, 78]
assert mergeSort(arr) == [-98, -98, -56, 0, 12, 34, 45, 45, 56, 78]
assert quickSort(arr) == [-98, -98, -56, 0, 12, 34, 45, 45, 56, 78]
assert heapSort(arr) == [-98, -98, -56, 0, 12, 34, 45, 45, 56, 78]
print("All sorting algos passed!")Sorting before searching is only less expensive if you want to search through a list many times. The amortized cost of sorting + searching can be less than just performing linear search each time.
- V: Vertice/Vertices
- E: Edge/Edges
def create_adjacency_list(edges):
adj_list = {}
for edge in edges:
node1 = edge[0]
node2 = edge[1]
if node1 in adj_list:
adj_list[node1].add(node2)
else:
adj_list[node1] = {node2}
if node2 in adj_list:
adj_list[node2].add(node1)
else:
adj_list[node2] = {node1}
# print(f"adj_list: {adj_list}")
return adj_listBreadth First Search O(logn)
Especially useful to find shortest path on unweighted graphs
- Intuition is exploring all the V on a layer before going on to the next layer
- Implement using a Queue and also keeps track of visited Vs. Each of the current V's neighbours are added to the Queue before moving on to the next V in the Queue until the Queue is empty
def BFS(edges, node_to_find):
if len(edges) == 0: return False
adj_list = create_adjacency_list(edges)
checked = {node:False for node in adj_list}
if edges[0][0] == node_to_find: return True
queue = [edges[0][0]]
checked[edges[0][0]] = True
while len(queue) > 0:
# remove node from queue of current_neighbours
node = queue.pop(0)
for neighbour in adj_list[node]:
# add neighbour to queue of current_neighbours
if not checked[neighbour]:
queue.append(neighbour)
# check the neighbour!
if neighbour == node_to_find: return True
checked[neighbour] = True
return FalseDepth First Search O(logn)
- Intuition is traversing a V until you hit a dead end and then backtrack
- Recursive implementation keeps track of a list of visited Vs, and calls the function on each neighbouring V that has not been visited
- Iterative implementation uses a Stack and also keeps track of visited Vs. While the stack is not empty, we pop a V from the stack, visit it, and then add all Vs unvisited neighbors to the stack
Both implementations have the same time complexity
def DFS(edges, node_to_find):
if len(edges) == 0: return False
adj_list = create_adjacency_list(edges)
checked = {node:False for node in adj_list}
stack = [edges[0][0]]
while len(stack) > 0:
node = stack.pop(-1)
if node == node_to_find: return True
checked[node] = True
for neighbour in adj_list[node]:
if not checked[neighbour]:
stack.append(neighbour)
return Falseedges = [[1,4], [1,10], [2,4], [2,9], [3,5], [3,6], [4,10], [6,8], [6,9], [7,8]]
assert BFS(edges, 0) == False
assert BFS(edges, 1) == True
assert BFS(edges, 2) == True
assert BFS(edges, 3) == True
assert BFS(edges, 4) == True
assert BFS(edges, 5) == True
assert BFS(edges, 6) == True
assert BFS(edges, 7) == True
assert BFS(edges, 8) == True
assert BFS(edges, 9) == True
assert BFS(edges, 10) == True
assert BFS(edges, 11) == False
assert DFS(edges, 0) == False
assert DFS(edges, 1) == True
assert DFS(edges, 2) == True
assert DFS(edges, 3) == True
assert DFS(edges, 4) == True
assert DFS(edges, 5) == True
assert DFS(edges, 6) == True
assert DFS(edges, 7) == True
assert DFS(edges, 8) == True
assert DFS(edges, 9) == True
assert DFS(edges, 10) == True
assert DFS(edges, 11) == False
print("All searching algos passed!")