5,337
edits
Line 38: | Line 38: | ||
Given: compare(a,b) to compare 2 numbers. A number k. | Given: compare(a,b) to compare 2 numbers. A number k. | ||
Goal: Return the k'th largest number. | Goal: Return the k'th largest number. | ||
===Median finding=== | |||
[https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/ Reference] | |||
* 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 <math>O(n) + O(n/2) + ... = O(n)</math> | |||
* Worst Case <math>O(n)</math> | |||
===Quickselect=== | |||
* Worst Case <math>O(n^2)</math> | |||
* Average Case <math>O(n)</math> | |||
;Notes | |||
* Using a good <math>O(n)</math> pivot finding algorithm (See finding the median in O(n)) will reduce the worst case to <math>O(n)</math> | |||
==Graph Algorithms== | ==Graph Algorithms== |