자바 버킷 스트링 정렬

Question

버킷 정렬을 사용하여 항상 같은 길이가 될 문자열 목록을 정렬하는 가장 좋은 방법은 무엇인지 알 수 없습니다.

알고리즘은 다음과 같을 것이다 : 나는 자바에 쓰고 있어요 내가 정렬되지 않은 문자열을 저장하는 주요 목록에 대한 ArrayList를 사용하고

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 

. 문자열은 각각 5 자입니다.

이것은 내가 시작한 것입니다. 그것은 두 번째 for 루프 내에서 단지 abrubdly 멈 춥니 다. 왜냐하면 다음에 무엇을해야할지 또는 첫 번째 부분을 올바르게 수행했는지 모르기 때문입니다.

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) 
} 

미리 감사드립니다.

편집 : 이것은 내가 지금 가지고있는 것입니다. 나는 그것이 작동하지 않는다는 것을 안다. 하나 이상의 글자가 같은 글자로 시작하는 것보다 더 많이 날라지기 때문이다.하지만 나는 더 올바른 방향으로 나아가고 있다고 생각한다. 내가 그것을 실행할 때, 중복 문자가 없는지 확인하기 위해 단어를 넣었을지라도, 첫 번째 설정 라인에서 괴물이 나온다 : count.set(myList.get(j).charAt(i), myList.get(j)); "스레드"main "의 예외"java.lang.StringIndexOutOfBoundsException : String index out 범위의 : 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)); 
    } 

Answer 1

이 나에게 숙제처럼 보이는, 그래서 나는 코드 솔루션으로 응답하지 않습니다.

하지만 기본적으로 당신이 붙잡고있는 비트는 버킷을 설정하는 것입니다. 아마도 버킷이 Map<Character, List<String>> 일 것입니다. 즉, 각 문자 A ~ Z를 해당 문자와 ​​일치하는 단어 목록 (현재보고있는 위치의 목록)에 매핑하고자합니다. 그 단어 목록은 귀하의 양동이입니다.

그런 다음 내부 루프를 완료 한 후지도 (AZ : hint : for (char ch = 'A'; ch <= 'Z'; ch++))에서 다른 루프를 실행하고 해당 버킷의 내용을 다시 비울 때) 목록.

Answer 2

Map을 사용하지 않으려는 경우 @JacobM에 설명 된 것과 동일한 논리를 사용할 수 있지만 목록 대신 배열을 사용할 수 있습니다. 그래서 List<String>[] buckets = new List<String>[26]을 만듭니다.

Answer 3

public void bucketSort(String[] words) 
{ 

    int maxlength=0; 
    for(int i=0;i<words.length;i++) 
    { 
     words[i] = words[i].toUpperCase(); 
     if(maxlength<words[i].length()) 
      maxlength = words[i].length(); 

    } 

    for(int j=maxlength-1;j>=0;j--) 
    { 

     Vector<Vector<String>> map = new Vector<Vector<String>>(); 
     for(int i=0;i<27;i++) 
     { 
      map.add(null); 
     } 
     for(int i=0;i<words.length;i++)//Add words of of length j or greater to map(which is bucket here) 
     { 

      if(words[i].length()>j) 
      { 
       int val = (int)words[i].charAt(j) -65; 
       if(map.get(val)!= null) 
       { 
        map.get(val).add(words[i]); 
       } 
       else 
       { 
        Vector<String> vecot = new Vector<String>(); 
        vecot.add(words[i]); 
        map.add(val, vecot); 
       } 
      } 
      else///Add words of of length<j to bucket 0 
      { 
       if(map.get(0) != null) 
       { 
        map.get(0).add(words[i]); 
       } 
       else 
       { 
        Vector<String> vecot = new Vector<String>(); 
        vecot.add(words[i]); 
        map.add(0, vecot); 
       } 

      } 
     } 
     int count =0; 
     for(int i=0;i<map.size();i++) 
     { 

      if(map.get(i)!=null) 
      { 
       for(int k=0;k<map.get(i).size();k++) 
       { 
       words[count]=map.get(i).get(k); 
       count++; 
       } 
      } 
     } 
     System.out.println("Next set :"); 
     for(int i=0;i<words.length;i++) 
     { 
      System.out.println(words[i]); 
     } 

    } 




} 

Answer 4

작은 목록으로 테스트했습니다. 예, 숙제를 위해이 작업을 수행해야했으며, 편의를 위해 코멘트를 남겨 두었습니다. 무슨 일이 일어나고 있는지 이해할 수 있도록 붙여 넣기 만하면됩니다 (OV 점수는 100 %입니다!).

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