mk13
BAN USERin bitmap method, we'll take a byte array where each bit of byte will represent unique number.. e.g. byte_[n], so this byte_[n] will represent the range {8*(n-1)+1to 8*(n-1)+8}, and so on. To allocate a bit to number x, simply divide x by 8 and get quotient (q) and reminder(r) and make r'th bit of byte_[q] ON.
this is how bitmap works.
now your point is correct as what happen when number repeats, since here in this file sorting, we need to retain all numbers, bitmap won't work. if it is given that many no repeats n times, then we can take n different bitmaps.. but by that many bit may be waste.. we can't re-initialize bitmap as it'll lost some other no... to get over this no, we can take any other small array if only few number repeats and for repeating no, we can update that array..
if you have any idea, plz put that here..
@Achilles: u are right.. internally to compute log(base_n)K, it'll take the same time as computing N^N.. but we can check unit digit of k just to check whether it's divisible by n or not, so if not then n^n!=k, it'll be in constant time and if yes,then i think it'll take same time as to compute n^n..
@kiran kumar: let say we divide file in three chunk A,B,C and after sorting individully, content of these parts is like: A{12,18,20,25,33,35,37},B{8,13,14,40,41,45,47},C{2,15,50,70,72,75,78}.
Now suppose in memory, we have {12,18,20,25} {8,13,14,40} {2,15,50,70} respectively from A,B,C. now we'll select 2 from C's part as its minimum, so put this in remaining 1GB and replace 2 in memory by an element of chunk C. i.e. insert 72 in C's part in memory.. next replace 8 by 41 and so on.. we are maintaining a min heap.. i think its clear now
Divide the file in 3 parts(3GB+3GB+4GB,(each part must be less than 4GB )) and sort each chunk using any O(nlogn) sorting algo(as it is less than 4GB we can apply any in-place sorting algo). once each chunk of file sorted, bring 1GB of each chunk in memory, so it'll occupy 3GB(1+1+1), now sort this 3GB data(by 3-way merge sort),select a number,add that in remaining 1GB, and while selecting this number, bring a number from corresponding chunk to replace it, finally write sorted 1GB to secondary storage.
- mk13 May 25, 2012
- mk13 July 11, 2012