I think you don't need to use the median number as pivot. As long as you use different number to do partition, after log(k) times recursive, the N element will be sorted.
On Sun, May 23, 2010 at 3:17 PM, Jagadish M <jagadis...@gmail.com> wrote: > > Further to my previous post, one question. > > Can the median be found in O(n) time without using extra memory? > > I am not familiar with the algorithms that find the median though I > > know the > > median can be found in O(n) time. > > > > This is important! I don't see how the standard algorithm for median > finding can be tweaked to use only constant extra space. > > @Bharath: It's a nice algorithm, nevertheless :) > > > -Jagadish > http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Liu Yan -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
