Java Bucket Sort program for Strings

Question

The main issue I am having is figuring out how to pass the specific Strings to the bucket class to separate each string into their respective buckets. This is for an assignment and I have been stuck. I do not need the solution just some help to point me in the right direction.

NOTE: I have to use the bucket arraylist and linkedlist in the bucket class

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

What I can understand from your code is that you want to read to words from a file and add them to the LinkedList list for respective buckets. is that correct? — Punit Mittal, Jul 09 '18 at 06:39
You could make a method for each bucket, that receives a word/string, [iterates from char min to char max](https://stackoverflow.com/questions/2047228/auto-increment-alphabet-in-java) and checks if the first letter of the word/string matches the current char. — Michael Hufnagel, Jul 09 '18 at 07:03
Yes, Punit, that's what I have to do but I'm not exactly sure how to. I was thinking a method for the bucket that adds only the words that fall from the range of the bucket and adds them on there — Maikel Jimenez, Jul 09 '18 at 16:39

Punit Mittal · Answer 1 · 2018-07-09T07:18:09.800

0

If you're using Java 8, you can do something like below to add words to respective bucket:

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

edited Jul 09 '18 at 07:18

answered Jul 09 '18 at 07:10

Punit Mittal

96
5

score 0 · Answer 2 · answered Jul 09 '18 at 07:22

0

I would not advise mixing letters in the buckets. You should not do any sorting like you did:

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

trivial algorithm:
1. find the length of longest String (O(n))
2. starting from the above length and going back, in each iteration put Strings in buckets (like bucket sort on numbers) (O(Length * n))

I'm not putting any code here as this is for an assignment

answered Jul 09 '18 at 07:22

Ofer Skulsky

685
4
10

there is a note message in OP's post: "_NOTE: I have to use the bucket arraylist and linkedlist in the bucket class_". Probably the course is about comprehending the bucket list mechanism (useful for eg using hashmaps) – KarelG Jul 09 '18 at 07:26

Java Bucket Sort program for Strings

2 Answers2