Algorithms refer to the logistics in manipulating data in these structures, such as searching or sorting. It is a method for solving a problem expressed as a sequence of steps. It serves the role that recipe is used in cooking.
Main Points
Sorting Algorithms
Searching Algorithms
Tree Traversals
Suggested Reading
Algorithm | Chapter |
---|---|
Linear Search, Binary Search |
Lafore Ch 2 |
Bubble Sort, Insertion Sort, Selection Sort |
Lafore Ch 3 |
Quicksort | Lafore Ch 7, CLRS Ch 7 |
Mergesort | Lafore Ch 6, CLRS Ch |
Heapsort |
Lafore Ch 12, CLRS Ch6 |
Tree Traversal | Lafore Ch 8 |
Big O notation for algorithm efficiency
Sorting Algorithm | Worst Case | Best Case | In Place? | Stability |
---|---|---|---|---|
Bubble Sort | O(n^{2}) | O(n) | Yes | Yes |
Insertion Sort | O(n2) | O(n) | Yes | Yes |
Selection Sort | O(n2) | O(n2) | Yes | No - When moving selected value, it introduces a new index. |
Mergesort | O(nlogn) | O(nlogn) | No - Requires additional memory for merge operation. |
Yes |
Quicksort | O(n2) | O(nlogn) | Yes | No - partitioning based on pivot values moves elements into different locations |
Heapsort | O(nlogn) | O(nlogn) | Yes | No - heapify reshifts nodes in the heap |