Сортировка Java-корзины по строкам
Вопрос
Я не могу понять, какой был бы наилучший способ использовать 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:Индекс строки вне диапазона: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));
}
Решение
Для меня это выглядит как домашнее задание, поэтому я не буду отвечать кодовым решением.
Но в основном, то, на чем вы застряли, - это настройка ваших корзин.Вероятно, вы хотите, чтобы ваши ведра были Map<Character, List<String>>
-- то есть вы хотите сопоставить каждую букву A - Z со списком слов, которые соответствуют этой букве (для позиции, которую вы сейчас просматриваете).Этот список слов - ваше ведро.
Затем, после того как вы закончите внутренний цикл, который у вас есть, вы выполняете еще один цикл по содержимому карты, начиная с A-Z (подсказка: for ( char ch = 'A'; ch <= 'Z'; ch++ )
) и выгружаете содержимое соответствующей корзины обратно в ваш (очищенный) список.
Другие советы
Протестировал это на небольшом списке;да, я также должен был сделать это для домашнего задания и для вашего удобства оставил комментарии, чтобы вы могли понять, что происходит, а не просто скопировать и вставить это (ваш балл 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);
}
}
}
Если вы не собираетесь использовать Map
, вы можете использовать ту же логику , что описана @Якобм но вместо этого используйте массив List.Итак, вы создаете List<String>[] buckets = new List<String>[26]
.
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]);
}
}
}