Finding Nth item of unsorted list without sorting the list
arrays, python, sorting
Solution
Sorting would require O(nlogn) runtime at minimum - There are very efficient selection algorithms which can solve your problem in linear time.
`Partition-based selection` (sometimes `Quick select`), which is based on the idea of quicksort (recursive partitioning), is a good solution (see link for pseudocode + Another example).
Problem
Hey. I have a very large array and I want to find the Nth largest value. Trivially I can sort the array and then take the Nth element but I'm only interested in one element so there's probably a better way than sorting the entire array...