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