Monday, February 23, 2015

How do you sort 1 million positive int values (assuming they do not repeat) present in a file (integers.txt) using  limited resources (not more than 2 MB or RAM) and creating only 1 more file (containing the sorted ints) ?
/*Gavin SATHAN*/


import java.io.*;
import java.util.*;

public class Super_Sorting {
public static void main(String[] args) {

int step=1024*1024;

int count=0;

Formatter f=null;

long startTime, endTime,duration;

//This block determines the number of lines in the input file
int numLines=0;
Scanner counterSc=null;
try{counterSc=new Scanner(new File("integers.txt"));}
catch(FileNotFoundException fnfe){ }
while(counterSc.hasNext()){
counterSc.next();
numLines++;
}
counterSc.close();

startTime=System.currentTimeMillis();

//For each value of each line, the appropriate value in the bitset is enabled.
try { f=new Formatter("integers_sorted.txt");}
catch (FileNotFoundException e) {e.printStackTrace();}

long start=0;
long end;
end=step;
int pass=0;
while (start
{
BitSet B=new BitSet(step);The size of the BITSET takes only 1 million bits
B.clear();
start=step*pass;
end=start+step;

System.out.println("Pass Number is "+pass+"\n\t => Filtering values between "+ start+ " and "+ end);
Scanner Sc=null;

try{ Sc=new Scanner(new File("integers.txt")); }
catch(FileNotFoundException fnfe){ }

while(Sc.hasNext()){
int val=Integer.parseInt(Sc.nextLine());
if ((val>=start)&&(val B.set(val-(int)start);
}
}//while
Sc.close();

for (int i = 0; i

if (B.get(i)){
int v=(int)start+i;
System.out.println(v);
f.format("%s\n", v);
count++;
}
}//for
start=end;
end+=step;
pass++;
}//for

endTime=System.currentTimeMillis();
f.close();

//This line determines the duration of the algo
duration=(endTime-startTime)/1000;

System.out.println("Number of lines = "+numLines+"\nNumber of integers sorted="+count+"\nSorting Took "+duration+"seconds");
}//main
}


No comments: