i think this doesnt work. consider first million numbers all of them to be 1. next million number(all of them ) to be 2. and so on....
if you take first element from each million then you will end up with 1,2........ but the smallest million numbers are all 1. On Fri, Sep 4, 2009 at 8:29 AM, viswanath ramakrishnan < [email protected]> wrote: > > > Q.3: Given a set of 1 Trillion integers on hard disk, find the > smallest 1 > million of them. You can fit at most 1 million integers in memory at a > time. > State the fastest solution you can think of. > > take the first 1 million out of 1 trillion and sort the 1 million > integersand store it back in the hard disk. > In this way carry on the sorting for every group of 1 million integers > and store it in the hard drive . Now groups of 1 million integers are > sorted upto 1 trillion. > now compare the first element of all the sorted groups the minimum of > them is the minimum of the 1 trillion. store it as the first element > in the memory. > next take the second element from the group from which the smallest > elemnt came and then check it with all other groups first element. > In this way repeat the procedureuntil the first 1 million is sorted > and stored in the memory. > > correct me if i am wrong..... > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
