String Radix Sort - StringIndexOutOfBoundsEception

Question

Я пишу свой собственный метод сортировки Radix для сортировки слов в строке (the big black cat sat on the  beautiful brown mat будет сортироваться как beautiful big black brown cat mat on sat the the). Метод принимает в List (собственный интерфейс List) отдельных слов и переупорядочивает список на месте.

Вот мой метод до сих пор:

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++; 
    } 
} 

(единственная, я надеюсь) проблема с моим методом является то, что, когда я читаю каждый символ слова, создать единое письмо подстроку слова , Поскольку внешний цикл for проходит через letters раз (где letters - это максимальная длина слова в Списке), исключение генерируется, когда этот цикл находится на итерации больше длины текущего слова - то есть letterNumber > word.length() - и поэтому пытается создать подстроку с использованием String Indexes, которые больше длины строки.

Как настроить мой метод так, чтобы он создавал подстроки каждого слова до letterNumber == word.length(), а также мог бы применять алгоритм сортировки для этих более коротких слов - «a» стал бы до «aa».

Answer 1

На протяжении всех моих попыток, я была сортировка слов по наиболее значительным письмом первый (первая буква каждого слова), то следующее существенное, и так далее. Разумеется, сортировка Radix основана на сортировке наименее значащей цифры/буквы (последней цифры/буквы номера/слова). Таким образом, вместо повторения через мой внешний цикл for, начиная с фокусировки на letterNumber = 1 и увеличивая это после каждой итерации, вместо этого я начинал с letterNumber = maxWordLength, а затем уменьшал это после каждой итерации, так что каждая итерация сравнивает следующую наиболее значимую букву.

@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--; 
    } 
} 

Answer 2

Почему вы не заменить

String letter = word.substring(letterNumber - 1, letterNumber); 
char ch = letter.charAt(0); 

с

char ch = word.charAt(letterNumber - 1); 

, который дает вам char непосредственно. Но это не решает проблему с IndexOutOfBoundException.

Вы должны, конечно, поймать исключение и обработать его. Может быть, полезно создать ведро для этого случая: когда слово слишком короткое для текущей итерации, оно сортируется в ведро. При объединении списка назад, сначала возьмите элементы этого ковша.

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

    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); 
      int index; 
      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 short words 
      } else { 
       index = 0; 
      } 
      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++; 
    } 
} 

Answer 3

Просто сгруппируйте элементы, которые короче длины строки в дополнительной группе. Также вам нужно сначала отсортировать наименее значимый (соответствующий) символ. Следующий код использует коллекции Java вместо того, чтобы все, что структура данных вы использовали:

public static void stringRadixSort(List<String> list, int letters) { 
    if (list.size() <= 1) { 
     return; 
    } 

    List<String>[] buckets = new List[27]; 
    for (int i = 0; i < buckets.length; i++) { 
     buckets[i] = new LinkedList<>(); 
    } 
    int largestLength = -1; 
    int secondLargestLength = 0; 
    for (String s : list) { 
     int length = s.length(); 
     if (length >= largestLength) { 
      secondLargestLength = largestLength; 
      largestLength = length; 
     } else if (secondLargestLength < length) { 
      secondLargestLength = length; 
     } 
    } 

    if (largestLength > letters) { 
     throw new IllegalArgumentException("one of the strings is too long"); 
    } 

    for (int i = secondLargestLength == largestLength ? secondLargestLength-1 : secondLargestLength; i >= 0; i--) { 
     for (String word : list) { 
      int index = (word.length() <= i) ? 0 : word.charAt(i) - ('a' - 1); 
      buckets[index].add(word); 
     } 

     list.clear(); 

     for (List<String> lst : buckets) { 
      if (lst != null) { 
       list.addAll(lst); 
       lst.clear(); 
      } 
     } 
    } 
}