# Find the Nth largest element

-1- Quick Select
Enter QuickSelect. It is very similar to quicksort, and if you are not already familiar with this algorithm, please read the tutorial for it before continuing with this page. Quickselect works by sorting only the areas it needs to find the desired element. After a quickselect, the data will be roughly sorted and the desired element will be in its correct position. Additionally, all items larger than the target will be to its right, and all items less than the target will be to its left.
To implement a quickselect we just modify a quicksort algorithm. (Changes to the quicksort algorithm are shown in bold)

1. If the area you're searching has only one element in it, you have found the element you are looking for, so stop searching.
2. Choose a pivot element (see Selecting a pivot)
3. Swap the pivot element with the last element
4. First, the program looks at pointer L and moves it right, checking each element in turn. As soon as it finds an element whose value is greater or equal to the pivot, it stops. It also stops if it passes pointer R.
5. Now the program moves pointer R left until it finds an element whose value is less than or equal to the pivot, or it has passed pointer L.
6. If pointers L and R have not met, swap the 2 elements they point to, and continue from step 3. Otherwise, swap the last element (which is the pivot because of step 1) with the element that pointer L is at.
7. If the pivot is the element you're looking for, stop searching. If the pivot is to the right (or larger) than the element you're searching for, repeat the quickselect on the left group only, otherwise repeat the quickselect on the right group only.

http://goanna.cs.rmit.edu.au/~stbird/Tutorials/QuickSelect.html

-2- In Python, use the heapq

import heapq

def nth_largest(n, iter):
    return heapq.nlargest(n, iter)[-1]

Example:

>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920

-3- In C (An Example)

int[] top5 = new int[5]();
top5[0] = top5[1] = top5[2] = top5[3] = top5[4] = 0x80000000; // or your min value

for(int i = 0; i < largeArray.length; i++) {
    if(largeArray[i] > top5[4]) {
       // insert into top5:
       top5[4] = largeArray[i];

       // resort:
       quickSort(top5);
    }
}

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

http://stackoverflow.com/questions/1034846/finding-nth-item-of-unsorted-list-without-sorting-the-list