Find the k-th largest element in an array (Hoare's selection algorithm)
Naive solution: Sort the array in descending order, using either of the O(nlogn) complexity algorithms (Merge Sort, Quick Sort). Return arr[k] Solution without sorting 1. Build a Max-heap and pop k times to get the k-th largest element. Complexity: O(n) + O(k * logn) = O(n) if k is small. Link: [Joel On Software](http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17), [StackOverflow](http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on?rq=1) 2. QuickSelect: modification over QuickSort - Hoare's selection algorithm Link: [QuickSelect](http://pine.cs.yale.edu/pinewiki/QuickSelect) Code: [QuickSelect](https://github.com/angad/py-algorithms/blob/master/Algorithms/quickselect.py)