3
$\begingroup$

Given a list of $2n$ elements, we have to find the $n$'th largest element. Which is the best algorithm (Time complexity + comparison) for this particular problem?

I know that this could be solved in general by sorting or by finding finding the k-th order statistic. But I am looking for something way simpler than k-th order statistic which solves this particular problem due to the $2n$ and $n$'th restriction.

Hurrah!! Problem is solved!

Thanks,

  • 0
    Also http://stackoverflow.com/questions/1054802/c-program-to-search-n-th-smallest-element-in-array-without-sorting2012-08-01

2 Answers 2

5

Use the median of medians algorithm to find the median in linear time. This is the best possible since all elements must be examined. It is interesting for a number of reasons: it violates the intuition that sorting is the fastest way to accomplish this, it is an optimal algorithm for the median problem and problems with optimal algorithms are rare, and also it calls into question the zero-one-infinity rule by dividing the list into fifths or smaller parts (thirds yields a log-linear algorithm, like sorting). Recently I mentioned this algorithm as an anecdote about the number $5$ itself.

1

Why not sort? Just comparing the $2n$ elements to anything will take $O(n)$ time, and it's easy to see that all $2n$ elements will have to be compared to something. To sort it takes only $O(n\ln n)$ time, worst-case.

EDIT As Robert Israel pointed out, one can find the median in $O(n)$ time. In fact, the selection algorithm can find the $k^{th}$ smallest element in $O(n)$ time. Learn something new everyday.

  • 1
    ...and of course, there are [methods for finding the median that don't need a preliminary sorting](http://en.wikipedia.org/wiki/Selection_algorithm).2012-08-01