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.
