- 1 Sorting
- 2 Selection
- 3 Graph Algorithms
- 4 Greedy
- 5 Dynamic Programming
- 6 Search
Given: compare(a,b) to compare 2 numbers. Goal: Sort a list of numbers from smallest to largest.
- Maintain a subarray which is always sorted
- Grab a number from the unsorted portion and insert it into the sorted portion
- Repeat until no more numbers are in the unsorted subarray
- Maintain a subarray which is always sorted.
- Every number in the sorted subarray will be smaller than the smallest number in the unsorted subarray.
- Find the smallest number in the unsorted portion and insert it into the sorted portion
- Repeat until no more numbers are in the unsorted subarray.
- Divide an conquer.
- Very fast. Average case O(nlogn).
- Good for multithreaded systems.
Given: compare(a,b) to compare 2 numbers. A number k. Goal: Return the k'th largest number.
- See CLRS
- Idea: Reinterpret your data as a 2D array of size 5 x (n/5)
- Find the median of each column of 5 elements
- Sort the columns by their medians
- Now you can eliminate the upper left (1/4) of elements and the lower right (1/4) of elements
- Recursively iterate on the remaining (1/2) of elements
- Each iteration takes O(n). Consecutive iterations are on n/2 data so we have
- Worst Case
- Worst Case
- Average Case
- Using a good pivot finding algorithm (See finding the median in O(n)) will reduce the worst case to