Bucket Sort with Linked List

Question

This is my implentation of Bucket Sort, but I see myself using way too many for loops, is this necessary?

 public static void bucketSort(Student[] students) {
 final String[] courses = { "IB", "IG", "IN", "IS", "IT" };
 final int amountOfBuckets = courses.length;
 final int n = students.length;
 if (n == 0) return;
 LinkedList<LinkedList<Student>> buckets = new LinkedList<>(); //create buckets
 for (int i = 0; i < amountOfBuckets; i++) {
 buckets.add(new LinkedList<>()); //fill bucketlist with buckets
 }
 for (int i = 0; i < courses.length; i++) {
 for (Student student : students) {
 if (student.getClassNumber().startsWith(courses[i])) {
 buckets.get(i).add(student);
 }
 }
 }
 for (int i = 0; i < amountOfBuckets; i++) {
 LinkedList<Student> studentLinkedList = buckets.get(i);
 Student[] s = studentLinkedList.toArray(new Student[studentLinkedList.size()]);
 insertionSortByClass(s);
 studentLinkedList = new LinkedList<>(Arrays.asList(s));
 buckets.set(i, studentLinkedList);
 }
 LinkedList<Student> result = new LinkedList<>();
 for (LinkedList<Student> bucket : buckets) {
 result.addAll(bucket);
 }
 for (int i = 0; i < result.size(); i++) {
 students[i] = result.get(i);
 }
}

As requested:

 public static void insertionSortByClass(Student[] student) {
 Student temp;
 for (int i = 1; i < student.length; i++) {
 for (int j = i; j > 0; j--) {
 if (student[j].compareTo(student[j - 1]) < 0) {
 temp = student[j];
 student[j] = student[j - 1];
 student[j - 1] = temp;
 }
 }
 }
}

• rolfl: Your question should describe the problem you are actually trying to solve. I looked at this, and wondered what the purpose of this code is, I gave up.
• TheCoffeeCup: Where is insertionSortByClass()?
• Ethan Bierlein: I have rolled back your previous edit. Please don't invalidate answers by changing your code.
• Simon Forsberg: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .

Answer 1

This code seems to be a specific BucketSort made for a specific program. I would instead create a more generic BucketSort:

public static <E extends Comparable<E>> void bucketSort(E[] array) {
 // ...
}
public static <E> void bucketSort(E[] array, Comparator<E> comparator) {
 // ...
}

Note there is two methods; one is for a class that implements the Comparator interface, and one to allow a Comparator to be passed as the Comparator for the class, where there is no comparator, or if you want to compare it in a different way.

Then the only problem is that you don't know the bounds for the buckets; the simple way would be to use bounds provided by the calling method:

public static <E extends Comparable<E>> void bucketSort(E[] array, E[] separators) {
}
public static <E> void bucketSort(E[] array, E[] separators, Comparator<E> comparator) {
}

The separators will be the upper limit of the bucket right before it; and the uppermost bucket will catch everything that is larger than the largest bound.

Now for the actual code:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
public class BucketSort {
 public static <E extends Comparable<E>> List<E> bucketSort(E[] array,
 E[] separators) {
 Comparator<E> comparator = new Comparator<E>() {
 @Override
 public int compare(E element1, E element2) {
 return element1.compareTo(element2);
 }
 };
 return bucketSort(array, separators, comparator);
 }
 public static <E> List<E> bucketSort(E[] array, E[] separators,
 Comparator<E> comparator) {
 final int numOfBuckets = separators.length + 1;
 // Create Buckets
 // Used ArrayList because we don't need the functions of a LinkedList
 List<Bucket<E>> buckets = new ArrayList<Bucket<E>>(numOfBuckets);
 for (int i = 0; i < numOfBuckets; i++) {
 buckets.add(new Bucket<E>());
 }
 // Sort into Buckets
 for (E element : array) {
 // Use binary search
 buckets.get(bucketNumber(element, separators, comparator)).getItems().add(element);
 }
 // Sort buckets
 for (Bucket<E> bucket : buckets) {
 bucket.getItems().sort(comparator);
 }
 // Combine Buckets and return
 for (int i = 1; i < numOfBuckets; i++) {
 buckets.get(0).getItems().addAll(buckets.get(i).getItems());
 }
 return buckets.get(0).getItems();
 }
 private static <E> int bucketNumber(E element, E[] separators,
 Comparator<E> comparator) {
 return bucketNumber(element, separators, 0, separators.length,
 comparator);
 }
 private static <E> int bucketNumber(E element, E[] separators, int low,
 int high, Comparator<E> comparator) {
 if (low + 1 == high) {
 return low;
 }
 int searchIndex = (high - low) / 2 + low;
 int compareResult = comparator
 .compare(element, separators[searchIndex - 1]);
 if (compareResult == 0) {
 return searchIndex;
 }
 return compareResult < 0 ? bucketNumber(element, separators, low,
 searchIndex, comparator) : bucketNumber(element, separators,
 searchIndex, high, comparator);
 }
}
class Bucket<E> {
 private List<E> elements;
 public Bucket() {
 this.elements = new LinkedList<E>();
 }
 public Bucket(Collection<E> elements) {
 this.elements = new LinkedList<E>(elements);
 }
 public List<E> getItems() {
 return elements;
 }
}

Yes, I know it looks 10x more complex than it need to be, but this can be used for further applications.

Since you asked for an explanation of the separators array...

The separator's array is there so that the method can know where to separate it into buckets. For example:

separator = [2, 5, 8, 11]
array = [1, 7, 2, 6, 4, 8, 12, 10, 13, 0, 5, 3, 9, 11]

Then the buckets would be:

buckets = [ [0, 1] , [2, 3, 4] , [5, 6, 7] , [8, 9, 10] , [11, 12, 13] ]

• Kevin S: I am sorry for the late reply, but thank you for your efforts. I have one question though, what is the use of the seperators array? I am trying to modify your version into a workable version for my needs..
• Kevin S: Let us continue this discussion in chat.