Программа Java Bucket Sort для строк

Основная проблема, с которой я сталкиваюсь, заключается в том, чтобы выяснить, как передать определенные строки в класс ведра, чтобы разделить каждую строку на соответствующие ведра. Это для задания, и я застрял. Мне не нужно решение, просто некоторая помощь, чтобы указать мне правильное направление.

ПРИМЕЧАНИЕ. Я должен использовать массив массивов и связанный список ведра в классе ведра.

import java.util.*;
import java.io.*;

public class Bucket {
    private char minInitial;
    private char maxInitial;
    private LinkedList<String> list;

    public Bucket (char min, char max) {

        minInitial = min;
        maxInitial = max;
        list = new LinkedList<String>();

    }

    public static void main (String args[]) {

        /* There are usually 8 for the entire alphabet because letters like c and s have more words for them than others */
        ArrayList<Bucket> buckets = new ArrayList<>(8);

        buckets.add(new Bucket('a', 'b'));
        buckets.add(new Bucket('c', 'c'));
        buckets.add(new Bucket('d', 'f'));
        buckets.add(new Bucket('g', 'k'));
        buckets.add(new Bucket('l', 'o'));
        buckets.add(new Bucket('p', 'r'));
        buckets.add(new Bucket('s', 's'));
        buckets.add(new Bucket('t', 'z'));


        File inFile;

        PrintWriter outFile;
        try {

            inFile = new File("input.txt");//input.txt file has the words sepepatated by comma "cat,dog,boy,bye"

            String path = inFile.getAbsolutePath();

            //outFile = new PrintWriter("output.txt");


            System.out.println("File Name:  "+ inFile +  "File Path: " + path);

            //System.out.println("File Name: " + outFile);

            Scanner fileScan = new Scanner(inFile);

            String inputFile="";

            while (fileScan.hasNext()) {

                inputFile = fileScan.next();
                System.out.println(inputFile);
            }


            String arrayString[] = inputFile.split(",");

            Arrays.sort(arrayString); //sorts the strings alphabetically

            for (int i =0; i<arrayString.length; i++) {
                System.out.println("List elem " + i + ": " +arrayString[i]);
                //traverses every element
            }

            System.out.println(Arrays.toString(arrayString));


            List listString = Arrays.asList(arrayString);

            System.out.println(listString);


        }
        catch (FileNotFoundException e) {
            System.out.println("! ! ! File Not Found ! ! !");
            e.printStackTrace();
        }
    }
}

java string bucket-sort
person Maikel Jimenez    schedule 09.07.2018    source источник
comment
Что я могу понять из вашего кода, так это то, что вы хотите прочитать слова из файла и добавить их в список LinkedList‹String› для соответствующих сегментов. это правильно?   -  person Punit Mittal    schedule 09.07.2018
comment
Вы можете создать метод для каждого сегмента, который получает слово/строку, итерирует от char min до char max и проверяет, соответствует ли первая буква слова/строки текущему char.   -  person Michael Hufnagel    schedule 09.07.2018
comment
Да, Пунит, это то, что я должен сделать, но я не совсем уверен, как это сделать. Я думал о методе для ведра, который добавляет только слова, выпадающие из диапазона ведра, и добавляет их туда.   -  person Maikel Jimenez    schedule 09.07.2018

Ответы (2)


arrow_upward
0
arrow_downward

Если вы используете Java 8, вы можете сделать что-то вроде ниже, чтобы добавить слова в соответствующее ведро:

Arrays.stream(arrayString)
.forEach(word -> buckets.stream()
    .filter(bucket -> bucket.minInitial <= word.charAt(0) && word.charAt(0) <= bucket.maxInitial)
    .findFirst().ifPresent(bucket -> bucket.list.add(word)));
person Punit Mittal    schedule 09.07.2018

arrow_upward
0
arrow_downward

Я бы не советовал смешивать буквы в ведрах. Вы не должны выполнять сортировку, как вы:

Массивы.sort (строка массива); //сортирует строки по алфавиту

тривиальный алгоритм:
1. найти длину самой длинной строки (O(n))
2. начиная с вышеуказанной длины и возвращаясь назад, на каждой итерации помещать строки в сегменты (например, сортировать числа по сегментам) (O (Длина * п))

Я не помещаю здесь код, так как это для задания

person Ofer Skulsky    schedule 09.07.2018
comment
в сообщении ОП есть примечание: ПРИМЕЧАНИЕ. Я должен использовать массив массивов и связанный список ведра в классе ведра. Вероятно, курс посвящен пониманию механизма списка сегментов (полезно, например, для использования хэш-карт). - person KarelG; 09.07.2018