Bubble Sort: Iterate through entire list while comparing pairs and swap positions based on their values until all elements sorted.
O(n²), but fast if list is almost sorted.
Insertion Sort: Iterates through unsorted list while building a sorted list. For each value encountered in unsorted list, find appropriate place in sorted list and insert it.
O(n²).
Merge Sort: A type of divide and conquer algorithm: 1) divides the list into two equally sized sub lists 2) sort each sub list 3) merge two sorted lists into final list.
O(n log n) — needs to divide log n times, and for each divide, it needs to go through all n items to merge, thus n times log n.
Heap Sort: 1) Build a heap (min or max) from the unsorted list 2)repeatedly remove the root node from the heap and put into the sorted list.
O(n log n) — remove root node is O(log n), and has to be repeated for each node, thus n times log n.
Quick Sort: A type of divide and conquer algorithm: 1) pick an item in the unsorted list as pivot 2) divided list into 2 sub lists, one contains elements smaller than pivot while the other contains elements greater than the pivot 3) sort the sub lists, and combine the results into final list
O(n log n) — need to divide O(log n) times, and after each divide, the partitioning has to go through all elements, thus overall runtime n times log n.
Linear Search: O(n)
Binary Search: O(log n)
Breadth-First-Search (BFS): Siblings first then children. Use queue usually.
Depth-First-Search (DFS): Children first then siblings. Use stack usually.
A* Search: Goal is to find the shortest path between 2 nodes in a graph. It’s a best-first search. At each iteration it finds the next node to extend the path based on the criteria g(next) + h(next) where g is the distance from next node to starting node and h is the heuristic (estimated) distance of next node to final node. use a heap usually.
Inorder (Left, Root, Right): useful for getting sorted list out of BST
Preorder (Root, Left, Right): useful for making copy of binary trees, or evaluate expression trees.
Postorder (Left, Right, Root): useful for deleting trees (because need to delete children before deleting parent)
| Best | Average | Worst | Space, Worst | |
|---|---|---|---|---|
| Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) |
| Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
| Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) | O(1) |
| Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(n) |
| Shell Sort | Ω(n log(n)) | Θ(n(log(n))^2) | O(n(log(n))^2) | O(1) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) | O(n) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Cubesort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |