String Radix Sort - StringIndexOutOfBoundsEception

Question

私は自分の基数ソート方法を使って文字列内の単語をソートしています（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()です。文字列の長さよりも大きい文字列インデックスを使用して部分文字列を作成しようとしています。

letterNumber == word.length()まで各単語の部分文字列を作成し、これらの短い単語にソートアルゴリズムを適用できるようにメソッドを調整するにはどうすればよいですか？ "a"は "aa"の前になります。

Answer 1

、私は、次の重要な、（各単語の最初の文字）最初の最も重要な文字で単語を並べ替えていました、等々。もちろん、基数ソートは、最下位の数字/文字（数字/単語の最後の数字/文字）のソートに依存しています。したがって、私の外側の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

は、なぜあなたは、直接あなたにcharを与える

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

で

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

に代わるものではありません。しかし、これは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(); 
      } 
     } 
    } 
}