COP 3530
Section U03
Spring 2017


                  More Radix Sort
                  ===============


  I. The Program:
  ---------------

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");
    /*    
        // define a test array with strings of the same length
        String[] testArray = {"Bill", "Mark", "Mary", "John", "Paul", "Barb"};
        print("The array before sorting with radixSortA", testArray);
        radixSortA(testArray,4);
        print("The array after sorting with radixSortA", testArray);
    */    
        // an array with strings of different length
        String[] testArray2 = { "Papa Bill", "Poco Pelo", "Geezer",
            "Minuteman", "Tornado", "Gargamel", "Papa Jai", "Baby Trevor" };
        // find the length a longest string in testArray2
        int maxLen = 0;
        for (String s: testArray2)
            if (s.length() > maxLen)
                maxLen = s.length(); // update maxLen
    /*    // pad the array
        padStrings(testArray2, maxLen);
        print("The array before sorting with countingRadixSort", testArray2);
        countingRadixSort(testArray,maxLen);
        print("The array after sorting with countingRadixSort", testArray2);
    */    
        // the same as testArray2, but we do not pad it
        String[] testArray3 = { "Papa Bill", "Poco Pelo", "Geezer",
            "Minuteman", "Tornado", "Gargamel", "Papa Jai", "Baby Trevor" };

        print("The array before sorting with radixSort", testArray3);
        radixSort(testArray3,maxLen);
        print("The array after sorting with countingRadixSort", testArray2);
    } // end main
    
    // 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<String> [] 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<String> 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();
    }        
    
    // counting radix sort an array of Strings
    // assume all are all ASCII
    // asumme all have the same length
    // from Mark Weiss's book Data structures and
    // Algorithm Analysis in Java, 3rd Edition, pp 313
    public static void countingRadixSort(String[] arr, int stringLen)
    {
        final int BUCKETS = 256;
        
        int N = arr.length;
        String[] buffer = new String[N];
      
        String [] in = arr;
        String [] out = buffer;
        
        for (int pos = stringLen -1 ; pos >= 0; pos--)
        {
            // count[k] is how many items go in bucket k
            int[] count = new int [BUCKETS+1];
            
            // compute the counts
            // the counts go in count[1] to count[BUCKETS +1]
            for (int i = 0; i < N; i++)
                count[in[i].charAt(pos) + 1]++;
          
            
            for (int b = 1; b <= BUCKETS; b++)
            {    count[b] += count[b-1];
                 if (pos == stringLen - 1)
                     System.out.println("count[" + ((char) b ) + "] = " + count[b]);
            }     
            for (int i = 0; i < N; i++)
                out[count[in[i].charAt(pos)]++] = in[i];
            for (int i = 0; i < N; i++)
                System.out.println("out[" + i + "] = " + out[i]);
            
            // swap in and out roles
            String [] temp = in;
            in = out;
            out = temp;
            print("The array after position " + pos, arr);
            System.out.println();
        }  
        
        // if oddnumber of passes, in is buffer, out is arr, so copy back
        if (stringLen % 2 == 1)
            for(int i = 0; i < arr.length; i++)
                out[i] = in[i];
    }
    
    // radix sort for an array of strings
    // assume all are all ASCII
    // assume that all have length bounded by maxLen
    // the algorthm is from Weiss's book listed above, pp 314
    public static void radixSort(String[] arr, int maxLen)
    {
        final int BUCKETS = 256;
        ArrayList<String> [] wordsByLength = new ArrayList[maxLen +1];
        ArrayList<String> [] buckets = new ArrayList[BUCKETS];
        
        // initialize the words by length
        for (int i = 0; i < wordsByLength.length; i++)
            wordsByLength[i] = new ArrayList<>();

        
        for (int i = 0; i < BUCKETS; i++)
            buckets[i] = new ArrayList<>();

        // the words of length i are in wordsByLength[i]
        for (String s : arr)
            wordsByLength[s.length()].add(s);
        
        for (int i = 0; i < maxLen + 1; i++)
            System.out.println("wordsbyLength[" + i + "].size = " + wordsByLength[i].size());
        
        // print the array
        int idx = 0;
        for (ArrayList<String> wordList : wordsByLength)
            for (String s : wordList)
                arr[idx++] = s;
        
        // print arr
        print("the array sorted by length", arr);
        
        int startingIndex = arr.length;
        for (int pos = maxLen -1; pos >= 0; pos-- )
        {
            startingIndex -= wordsByLength[pos+1].size();
            System.out.println("pos = " + pos +", startingIndex = " + startingIndex);
            for( int i = startingIndex; i < arr.length; i++)
                buckets[arr[i].charAt(pos)].add(arr[i]);
            
            idx = startingIndex;
            for (ArrayList<String> thisBucket : buckets)
            {
                for (String s : thisBucket)
                    arr[idx++] = s;
                
               thisBucket.clear(); 
            }
        }    
    } // end method                
}

  II. The Output:
  ---------------


run:
Sorting an Array Using Bucket Sort
==================================


The array before sorting with radixSort
---------------------------------------
Papa Bill
Poco Pelo
Geezer
Minuteman
Tornado
Gargamel
Papa Jai
Baby Trevor

wordsbyLength[0].size = 0
wordsbyLength[1].size = 0
wordsbyLength[2].size = 0
wordsbyLength[3].size = 0
wordsbyLength[4].size = 0
wordsbyLength[5].size = 0
wordsbyLength[6].size = 1
wordsbyLength[7].size = 1
wordsbyLength[8].size = 2
wordsbyLength[9].size = 3
wordsbyLength[10].size = 0
wordsbyLength[11].size = 1
the array sorted by length
--------------------------
Geezer
Tornado
Gargamel
Papa Jai
Papa Bill
Poco Pelo
Minuteman
Baby Trevor

pos = 10, startingIndex = 7
pos = 9, startingIndex = 7
pos = 8, startingIndex = 4
pos = 7, startingIndex = 2
pos = 6, startingIndex = 1
pos = 5, startingIndex = 0
pos = 4, startingIndex = 0
pos = 3, startingIndex = 0
pos = 2, startingIndex = 0
pos = 1, startingIndex = 0
pos = 0, startingIndex = 0
The array after sorting with countingRadixSort
----------------------------------------------
Papa Bill
Poco Pelo
Geezer
Minuteman
Tornado
Gargamel
Papa Jai
Baby Trevor

BUILD SUCCESSFUL (total time: 0 seconds)