@Ankur: When k = 100, the heap method I proposed is O(n). And if you have to program it from scratch, it is a lot easier than the median of medians algorithm.
Dave On Aug 18, 2:35 am, Ankur Garg <ankurga...@gmail.com> wrote: > U can use selection Algorithm to achieve the same ...it has got expected > running time complexity as O(n) ...Read Wikipedia to see the proper > implementation.. > > Just some tweak with Quick Sort ..Also there is one method median of medians > one which has worst case complexity as O(n) > > Regards > > Ankur > > On Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma <amolsharm...@gmail.com>wrote: > > > > > it will be max heap only.....in which root denotes the largest number in > > your set of 100 smallest > > -- > > > Amol Sharma > > Third Year Student > > Computer Science and Engineering > > MNNIT Allahabad > > > On Thu, Aug 18, 2011 at 9:14 AM, aditi garg > > <aditi.garg.6...@gmail.com>wrote: > > >> @ dave : i hv one doubt,we wud be maintaining a max or a min heap?? > > >> On Thu, Aug 18, 2011 at 9:11 AM, aditi garg > >> <aditi.garg.6...@gmail.com>wrote: > > >>> thank u so much dave :) > > >>> On Thu, Aug 18, 2011 at 8:44 AM, Dave <dave_and_da...@juno.com> wrote: > > >>>> @Aditi: Form a max-heap of the first 100 numbers. Then as you read the > >>>> remaining numbers, if a number is less than the root of the max-heap, > >>>> replace the root with it and restore the heap condition. When you > >>>> reach the end of the million numbers, the heap will contain the > >>>> smallest 100 numbers. > > >>>> If there are n numbers and you want the smallest k, this algorithm is > >>>> O(n log k). > > >>>> Dave > > >>>> On Aug 17, 10:05 pm, aditi garg <aditi.garg.6...@gmail.com> wrote: > >>>> > How to find the set of smallest 100 numbers out of 1 million > >>>> numbers... > > >>>> -- > >>>> You received this message because you are subscribed to the Google > >>>> Groups "Algorithm Geeks" group. > >>>> To post to this group, send email to algogeeks@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. > > >>> -- > >>> Aditi Garg > >>> Undergraduate Student > >>> Electronics & Communication Divison > >>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY > >>> Sector 3, Dwarka > >>> New Delhi > > >> -- > >> Aditi Garg > >> Undergraduate Student > >> Electronics & Communication Divison > >> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY > >> Sector 3, Dwarka > >> New Delhi > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algogeeks@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. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@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. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
