COP 3530 Section U03 Spring 2017 RADIX SORT ========== I. The Program: --------------- import java.util.ArrayList; public class RadixSort { // driver for public static void main(String[] args) { System.out.println("Sorting an Array Using Bucket Sort"); System.out.println("==================================\n\n"); String[] testArray = { "Papa Bill", "Poco Pelo", "Geezer", "Minuteman", "Tornado", "Gargamel", "Papa Jai", "Baby Trevor" }; // find the length a longest string int maxLen = 0; for (String s : testArray) if (s.length() > maxLen) maxLen = s.length(); // update maxlen padStrings(testArray,maxLen); print("The array before sorting", testArray); radixSortA(testArray,maxLen); print("The array after sorting", testArray); } // make every string in arr have length len by padding it with blanks public static void padStrings(String[] arr, int len) { String blanks = ""; for (int i = 0; i < len; i++) blanks = blanks + " "; // check for enull or empty array if (arr == null || arr.length == 0) return; for (int i = 0; i < arr.length; i++) { if (arr[i].length() < len) { String s = arr[i]; arr[i] = s + blanks.substring(0,len - s.length()); } } } // taken from M.Weiss Data Structures and Algorithms, 3rd Edition // pp 31 // Radix sort an array of strings // assume that all strings have the same lengths // all strings are all ASCII public static void radixSortA(String[] arr, int stringLen) { final int BUCKETS = 256; ArrayList [] buckets = new ArrayList[ BUCKETS ]; // initialize the buckets for (int i = 0; i < BUCKETS ; i++) buckets[i] = new ArrayList<>(); // sort for (int pos = stringLen -1; pos >= 0; pos--) { for (String s : arr) buckets[s.charAt(pos)].add(s); int inx = 0; for( ArrayList thisBucket : buckets) { for (String s :thisBucket) arr[inx++] = s; thisBucket.clear(); } // end inner for // print the string print("The array after position " + pos, arr); System.out.println(); } // end outter for } // end method // print the header msg, then the array arr, item per line public static void print(String msg, String[] arr) { // print the header System.out.println(msg); for (int i = 0; i < msg.length(); i++) System.out.print("-"); System.out.println(); // print the array for (String s: arr) System.out.println(s); // add an empty line System.out.println(); } } II. The Output: --------------- run: Sorting an Array Using Bucket Sort ================================== The array before sorting ------------------------ Papa Bill Poco Pelo Geezer Minuteman Tornado Gargamel Papa Jai Baby Trevor The array after position 10 --------------------------- Papa Bill Poco Pelo Geezer Minuteman Tornado Gargamel Papa Jai Baby Trevor The array after position 9 -------------------------- Papa Bill Poco Pelo Geezer Minuteman Tornado Gargamel Papa Jai Baby Trevor The array after position 8 -------------------------- Geezer Tornado Gargamel Papa Jai Papa Bill Minuteman Poco Pelo Baby Trevor The array after position 7 -------------------------- Geezer Tornado Minuteman Baby Trevor Papa Jai Gargamel Papa Bill Poco Pelo The array after position 6 -------------------------- Geezer Papa Jai Gargamel Poco Pelo Papa Bill Minuteman Tornado Baby Trevor The array after position 5 -------------------------- Papa Bill Papa Jai Poco Pelo Baby Trevor Tornado Minuteman Gargamel Geezer The array after position 4 -------------------------- Papa Bill Papa Jai Poco Pelo Baby Trevor Tornado Gargamel Geezer Minuteman The array after position 3 -------------------------- Papa Bill Papa Jai Gargamel Tornado Poco Pelo Minuteman Baby Trevor Geezer The array after position 2 -------------------------- Baby Trevor Poco Pelo Geezer Minuteman Papa Bill Papa Jai Gargamel Tornado The array after position 1 -------------------------- Baby Trevor Papa Bill Papa Jai Gargamel Geezer Minuteman Poco Pelo Tornado The array after position 0 -------------------------- Baby Trevor Gargamel Geezer Minuteman Papa Bill Papa Jai Poco Pelo Tornado The array after sorting ----------------------- Baby Trevor Gargamel Geezer Minuteman Papa Bill Papa Jai Poco Pelo Tornado BUILD SUCCESSFUL (total time: 1 second)