String Radix Sort - StringIndexOutOfBoundsEception

Question

I am writing my own Radix Sort method to sort the words in a String (the big black cat sat on the  beautiful brown mat would be sorted as beautiful big black brown cat mat on sat the the). The method takes in a List (my own List interface) of the individual words and reorders the list in place.

Here is my method so far:

public static void stringRadixSort(List<String> list, int letters) {
    List<String>[] buckets = (List<String>[]) Array.newInstance(List.class, 26);

    int letterNumber = 1; //Sorts list by 1st letter of each word, then 2nd etc.
    for (int i = 0; i < letters; i++) {
        while (!list.isEmpty()) {
            String word = list.remove(list.first());
            if (word.length() > letters) throw new UnsortableException("The list contains a word that holds more letters than the given maximum number of letters."
                    + "\nMax Letters: " + letters + "\nWord: " + word);
            String letter = word.substring(letterNumber - 1, letterNumber); //EXCEPTION THROWN
            char ch = letter.charAt(0);
            int index = ch - 'a';    //gets index of each letter ('a' = buckets[0], 'z' = buckets[25]
            if (buckets[index] == null) {
                buckets[index] = new LinkedList<String>();
            }
            buckets[index].insertLast(word);
        }

        for (int j = 0; j < buckets.length; j++) {
            if (buckets[j] != null) {
                while (!buckets[j].isEmpty()) {
                    list.insertLast(buckets[j].remove(buckets[j].first()));
                }
            }
        }
        letterNumber++;
    }
}

The (only, I hope) problem with my method is that when I am reading each character of the word, I create a single letter substring of the word. As the outer for loop runs through letters times (where letters is the maximum length of a word in the List), the exception is thrown when this loop is on an iteration greater than the length of the current word - i.e. letterNumber > word.length() - and so it is attempting to create a substring using String Indexes which are greater than the String's length.

How can I adjust my method so that it only creates substrings of each word until letterNumber == word.length(), and also then be able to apply the sorting algorithm to these shorter words - "a" would become before "aa".

Answer 1

Throughout all my attempts, I had been sorting the words by most significant letter first (1st letter of each word), then the next significant, and so on. Of course, Radix sort relies on sorting the least significant digit/letter (the last digit/letter of the number/word). So, instead of iterating through my outer for loop starting by focusing on letterNumber = 1 and incrementing this after each iteration, I instead began with letterNumber = maxWordLength, and then decremented this after each iteration, so that each iteration compares the next most significant letter.

@SuppressWarnings("unchecked")
public static void stringRadixSort(List<String> list) {
    List<String>[] buckets = (List<String>[]) Array.newInstance(List.class, 27);

    //Find longest word in list
    int maxWordLength = 0;
    for (String word : list) {
        if (word.length() > maxWordLength) {
            maxWordLength = word.length();
        }
    }

    //Sorts list based on least significant letter (last letter of word) to most significant
    int letterNumber = maxWordLength;
    for (int i = 0; i < maxWordLength; i++) {
        while (!list.isEmpty()) {
            String word = list.remove(list.first());
            int index = 0;
            if(word.length() >= letterNumber) {
                char ch = word.charAt(letterNumber - 1);
                index = ch - 'a' + 1;    //gets index of each letter ('a' = buckets[1], 'z' = buckets[26], buckets[0] is for words shorter than 'letterNumber')
            }
            if (buckets[index] == null) {
                buckets[index] = new LinkedList<String>();
            }
            buckets[index].insertLast(word);
        }

        for (int j = 0; j < buckets.length; j++) {
            if (buckets[j] != null) {
                while (!buckets[j].isEmpty()) {
                    list.insertLast(buckets[j].remove(buckets[j].first()));
                }
            }
        }
        letterNumber--;
    }
}