Nth Largest Element

If you need the nth largest element of an unsorted list, an obvious solution comes to mind:

sort(list);
return list[nth];

This is easy to code but runs a little slow, in O(nlgn).

For something fast, there’s an algorithm that runs in expected O(n) called QuickSelect (Wikipedia), a cross between Quicksort and binary search. Like Quicksort, there’s a worst-case time of O(n^2), so where handling large user-supplied inputs consider choosing the partition pivot element randomly.

The gist:

function quickselect(list, nth)

    begin = 0, end = list.size()
    loop
        partition list[begin, end)
        if partition equals nth, return list[partition]
        else drill down on partition's appropriate side
    loop end

My implementation is in git and below:

Leave a Reply