Java Bucket Sort on Strings

Question

I can't figure out what would be the best way to use Bucket Sort to sort a list of strings that will always be the same length.

An algorithm would look like this:

For the last character position down to the first:
    For each word in the list:
        Place the word into the appropriate bucket by current character
    For each of the 26 buckets(arraylists)
        Copy every word back to the list

I'm writing in java and I'm using an arraylist for the main list that stores the unsorted strings. The strings will be five characters long each.

This is what I started. It just abrubdly stops within the second for loop because I don't know what to do next or if I did the first part right.

ArrayList<String> count = new ArrayList<String>(26);

for (int i = wordlen; i > 0; i--) {
    for (int j = 0; i < myList.size(); i++)
        myList.get(j).charAt(i)
}

Thanks in advance.

EDIT: This is what I have now. I know it doesn't work because if there were more than one strings that started with the same letter than it would blow up, but I think I'm more in the right direction. When I run it, even with words that I put it in to make sure there are no duplicates letters, it freaks out on the first set line: count.set(myList.get(j).charAt(i), myList.get(j)); It's says "Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 5"

 public void BucketSort(int wordlen) {

   ArrayList<String> count = new ArrayList<String>(26);

     //Make it so count has a size
   for(int p = 0; p < 26; p++)
       count.add(null);

    for (int i = wordlen; i > 0; i--) { //for each letter
        for (int j = 0; j < myList.size(); j++) //for each word
               //Add the word to count based on the letter
            count.add((int)myList.get(j).charAt(i) - 65, myList.get(j));
}
     //Clear the main list so there aren't a bunch of unsorted words leftover
   myList.clear();

     //Add the words back in to the list based on their order in count
   for (int m = 0; m < 26; m++)
       myList.add(count.get(m));
  }

Solution 1

This looks like homework to me, so I won't respond with a code solution.

But basically, the bit you're stuck on is setting up your buckets. Probably you want your buckets to be a Map<Character, List<String>> -- that is, you want to map each letter A - Z to a list of words that match that letter (for the position you're currently looking at). That list of words is your bucket.

Then, after you finish the inner loop you've got there, you do another loop through the contents of the map, going from A-Z (hint: for ( char ch = 'A'; ch <= 'Z'; ch++ )) and dumping the contents of the corresponding bucket back into your (emptied) list.

Solution 2

Tested this on a small list; yes, I also had to do this for homework and for your convenience left comments so you can understand what is going on and not just copy paste it (your OV score will be 100% if you do!).

public static void sort(String[] array) {
        if (array.length == 0) return;  // empty check

        // Determine max length
        int max = 0;
        for (int i = 1; i < array.length; i++) {
            // update max length
            if (max < array[i].length()) max = array[i].length();
        }


        // Initialize buckets
        int bucketCount = 26;   // alphabet
        // buckets in maps
        HashMap<Character, Vector<String>> buckets = new HashMap<Character, Vector<String>>(bucketCount);
        // create the buckets
        char a = 'a';
        for (int i = 0; i <= bucketCount; i++, a++){
            buckets.put(a, new Vector<String>());
        }   

        // assign array values into buckets
        for (int i = 0; i < array.length; i++) {
            // get first letter of word
            String current = array[i];
            char letter = current.toLowerCase().charAt(0);
            buckets.get(letter).add(array[i]);
        }

        // Sort buckets and place back into input array
        int index = 0;  // keeps global array index
        for (char key = 'a'; key <= 'z'; key++) {
            // retrieve the bucker
            Vector<String> bucket = buckets.get(key);

            // do an insertion sort on bucket
            for (int i = 1; i < bucket.size(); i++){
                // i starts as 1, as a list of size 1 is already sorted

                // save the value at the index and remove it
                String temp = bucket.get(i);
                bucket.remove(i);

                // move all values one up, until we find the saved value's location
                int j;
                for(j = i-1; j >= 0 && 
                        bucket.get(j).compareToIgnoreCase(temp) > 0; j--){
                    // to "insert", we need to add and remove
                    bucket.add(j+1, bucket.get(j));
                    bucket.remove(j);
                }
                // place the saved value in the proper location
                bucket.add(j+1, temp);
            }


            // pile the current bucket back into array
            for (int j = 0; j < bucket.size(); j++) {
                array[index++] = bucket.get(j);
            }
        }
    }