-3

Possible Duplicate:
How to find the kth largest element in an unsorted array of length n in O(n)?

How do I write an algorithm to output the 10th highest number in an unsorted array of size n (in Java)?

Community
  • 1
  • 1
user1305400
  • 11
  • 1
  • 7
    Question has already been answered.. [link]http://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on please search once before asking... :-) – Aravindh Mar 31 '12 at 19:02
  • i have got nothing, just starting from the scratch. – user1305400 Mar 31 '12 at 19:04

3 Answers3

2

You are looking for selection algorithm, which can finds the kth biggest/smallest number in an array in O(n)

It can also be done using a partial sort, or using a min-heap of a fixed size k, which will contain the kth highest numbers at each time, and iterate the array while maintaining this heap.

Note that the last solution [min-heap] is less efficient then selection algorithm in terms of big O notation, for the general problem of an arbitrary k.

amit
  • 175,853
  • 27
  • 231
  • 333
  • 2
    Though, admittedly, if it's always the tenth-largest this might be massively overkilling the problem. :-) – templatetypedef Mar 31 '12 at 19:02
  • yeah, so which particular algorithm of the selection algorithm should i use – user1305400 Mar 31 '12 at 19:05
  • @user: Whichever you like. You can also sort and just extract the highest 10 numbers, which would be `O(n * log n)` instead of `O(n)` for a hardcoded number of items. – Niklas B. Mar 31 '12 at 19:07
  • @user1305400: [referring to arbitrary `k`]: It depends what you want, if you want a guaranteed `O(n)` worst case complexity - the median of medians solution is the way to do. If you want good performance on average case - I'd use [partition based selection algorithm](http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm), and if you want easiest to program, and you already have heap implementation - the heap solution is the way to go. – amit Mar 31 '12 at 19:08
2

Create an array of 10 elements. Keep the elements of your array sorted.

Passing through the original array once, compare the element with the smallest in your array of 10. If it is larger, put it in. Otherwise move on.

DRVic
  • 2,481
  • 1
  • 15
  • 22
  • Note that maintaing this array will require `k` ops per each element you insert. I don't know if it will be better or worse then a heap for `k == 10` - but for larger `k` values - it will start becoming an issue. – amit Mar 31 '12 at 19:20
  • Actually, it'll require an average of k/2 ops. – Nick Johnson Mar 31 '12 at 20:44
  • And for k=10 it is unlikely to be worth structuring the array as a heap. Log 2 of 10 is between 3 and 4, but the cost of an operation is greater. – DRVic Mar 31 '12 at 23:01
  • And you you typically will insert very few elements relative to n, since most of the time you're scanning past elements that are less than the min in the array of 10. – DRVic Mar 31 '12 at 23:02
0

The best way is to use Prune and Search algorithm if the array does not containt discrete elements (is contains for example doubles). If is contains discrete elements (integers) - use Counting sort and pick 10th element)

malejpavouk
  • 4,297
  • 6
  • 41
  • 67