In: Computer Science
IN JAVA!!!
In this project, you will use radix.txt as the input file, and output the integers SORTED USING RADIX SORT. You may assume all your input consists of integers <=9999.
Your main program will input the integers and put them into a QUEUE. It will then pass this queue to a method called radixSort which will sort the numbers in the queue, passing the sorted queue back to main.
The main program will then call another method to print the contents of this (sorted queue) .
Notes:
1. radixSort method will need an array of queues. (you had a similar assignment, H4, where you needed an array of linked lists. You may need to look this up to refresh how to create an array of data structures. H4 was an array of linked lists, this is an array of queues - do NOT make it an array of linked lists)
2. radixSort will NOT print the queue.
3. Use the java Queue class (the Interface).
radix.txt
2345 67 89 1145 36 39 40 11 95 4707 299 278 256 6189 170 8167 1459 1234 1226 998 889 4434 3912 4570 66
file-name: RadixSort.java ------------------------------------- import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.*; public class RadixSort { public static void main(String[] args) { Queue<Integer> radixQueue = new LinkedList<>(); BufferedReader br ; try { br = new BufferedReader(new FileReader("/home/rahul/Pictures/radix.txt")); String line = br.readLine(); while(line != null) { String[] str = line.split(" "); int i = 0; while (i < str.length) { radixQueue.add(Integer.parseInt(str[i])); i++; } line = br.readLine(); } } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } System.out.println("Before sorting"); printQueue(radixQueue); // calling the radixSort method to sort the elements in the Queue Queue<Integer> sorted = radixSort(radixQueue); System.out.println("\n--------------------------------------"); System.out.println("After sorting"); // printing printQueue(sorted); } // END of main() method public static Queue<Integer> radixSort(Queue<Integer> Q) { int max = getMax(Q); for(int exp =1; max/exp > 0; exp = exp*10) { Q = countSort(Q,exp); } return Q; } public static int getMax(Queue<Integer> Q) { // System.out.println("MAX value: "+Collections.max(Q)); return Collections.max(Q); } public static Queue<Integer> countSort(Queue<Integer> Q, int exp) { ArrayList<Integer> al = new ArrayList<>(Q); int output[] = new int[al.size()]; int count[] = new int[10]; Arrays.fill(count, 0); for(int i: al) { count[(i/exp)%10]++; } // for(int i=0;i<10;i++) { // System.out.println(count[i]); // } for(int i=1; i<10;i++) { count[i] = count[i] + count[i-1]; } for(int i = al.size()-1; i>=0;i--) { output[count[(al.get(i)/exp)%10] -1] = al.get(i); count[(al.get(i)/exp)%10]--; } Queue<Integer> new_q = new LinkedList<>(); for(int i : output) { new_q.add(i); } return new_q; } public static void printQueue(Queue<Integer> Q) { Iterator iterator = Q.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); } } } // END of class
---------------------------------------------------------------------------
OUTPUT:
The one in white background is output on console and the one in background is input file.
THANK YOU!!