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,

  • 1
    "Typical approaches... (are) not something that I am looking for." - then, what? It's not too hard to adapt methods for finding the median...2012-08-01
  • 0
    There is a list of sorting algorithms on Wikipedia ; I don't know anything about sorting, but I think you should at least take the time to read and study it yourself : http://en.wikipedia.org/wiki/Sorting_algorithm2012-08-01
  • 0
    Thanks J.M. Now I know how to solve this one :)2012-08-01
  • 0
    Remove the largest element, and you're finding the median. There is a "well-known" linear-time algorithm for that.2012-08-01
  • 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
    But finding the median can be done in $O(n)$.2012-08-01
  • 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