1

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

Is there any algorithm of finding the middle value of given list without performing the sorting operation.

for example if the list is maintained as stack and contains ( 1,2,5,3,4,6 ) then the middle value should be 4 so my question is how to get this value without performing the sorting operation on the list.

is this possible?

Community
  • 1
  • 1
paul
  • 23
  • 1
  • 4
  • Why don't you want to sort the list? *curious* – Buhake Sindi Aug 22 '11 at 05:43
  • 2
    how do you compute the middle value ? As far as I can see, it could be 3 or 4 in your example. – Nicolas Modrzyk Aug 22 '11 at 05:45
  • Why is 4 the middle value? Is that an average of 3 and 4 rounded up? – nnnnnn Aug 22 '11 at 05:45
  • Probably the OP just wants the median. Most sorts are nlogn but there are near-linear algorithms. Not that they are necessarily faster, but they are interesting. – Ray Toal Aug 22 '11 at 05:47
  • i did sorting so obtained 1 2 3 4 5 6 then mid=list[size()/2+1] and that is equal to 4 – paul Aug 22 '11 at 05:51
  • Without sorting it's not possible.Even if you will go for any algorithm it must do the sorting internally to find middle value.So it does not matter internally or external.Finally sorting is there. – Android Killer Aug 22 '11 at 06:05

1 Answers1

3

Yes, there are well-known algorithms to find the kth largest element of a list. See How to find the kth largest element in an unsorted array of length n in O(n)?

Here k is pre-computed as length/2 of course, adjusted to the nearest integer if there are an even number of elements in your list.

Community
  • 1
  • 1
Ray Toal
  • 86,166
  • 18
  • 182
  • 232