Java Bucket Сортировка по строкам

Question

Я не могу понять, как лучше использовать Bucket Sort для сортировки списка строк, которые всегда будут одинаковой длины.

Алгоритм будет выглядеть так:

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

Я пишу в Java, и я использую arraylist для основного списка, который хранит несортированные строки.Строки будут состоять из пяти символов каждая.

Это то, что я начал.Он просто резко останавливается во втором цикле for, потому что я не знаю, что делать дальше, или я правильно сделал первую часть.

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Индекс вне диапазона: 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 (подсказка: for ( char ch = 'A'; ch <= 'Z'; ch++ )) и сбрасывая содержимое соответствующего блока обратно в ваш опустошен) список.

Answer 2

Проверено это в небольшом списке; да, я также должен был сделать это для домашней работы и для вашего удобства оставил комментарии, чтобы вы могли понять, что происходит, а не просто скопировать и вставить его (ваш 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);
            }
        }
    }

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

Если вы не собираетесь использовать Map, вы можете использовать ту же логику, как описано в @ JacobM , но вместо этого иметь массив List. Итак, вы создаете List<String>[] buckets = new List<String>[26].