how about using binary index tree?? On Tue, May 25, 2010 at 5:41 PM, liu yan <ryu...@gmail.com> wrote:
> 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- yezhu malai vaasa venkataramana Govinda Govinda -- 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.
