I am working on a test program to develop an implementation of bucket sort for personal development. The examples that I have seen online do not match the sort of implementation that I am trying to accomplish.

My attempt

import java.util.*;

public class BucketSort {
    private static int t = 10;
    public static void main(String args[]) {
        int[] list = {331, 454, 230, 34, 343, 45, 59, 453, 345, 231, 9};
        for(int i = 0; i < list.length; i  ){
            System.out.print(list[i] " ");
        }
        bucketSort(list);
        for(int i = 0; i < list.length; i  ){
            System.out.print(list[i] " ");
        }
    }

    public static <E> void bucketSort(int[] list) {
        java.util.ArrayList<Integer>[] bucket = new java.util.ArrayList[t 1];// Distribute the elements from list to buckets
        for (int i = 0; i < list.length; i  ) {
            // Assume element has the getKey() method
            int key = list[i]; // list[i].getKey()
        if (bucket[(int) key] == null)
            bucket[(int) key] = new java.util.ArrayList<Integer>();
            bucket[(int) key].add(list[i]);
        }
        // Now move the elements from the buckets back to list
        int k = 0; // k is an index for list
        for (int i = 0; i < bucket.length; i  ) {
            if (bucket[i] != null) {
                for (int j = 0; j < bucket[i].size(); j  )
                    list[k  ] = (int)(bucket[i].get(j));
            }
        }
    }
}

Expected: a sorted list of integers

Actual:

java BucketSort 
331 454 230 34 343 45 59 453 345 231 9 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 331 out of bounds for length 11
        at BucketSort.bucketSort(BucketSort.java:21)
        at BucketSort.main(BucketSort.java:10)

Any help with this would be greatly appreciated. Thank you.

CodePudding user response：

I don't know what bucket sort is but as far as I look at your method, see bucket[(int) key] which may result in out of the index exception as happened in your output. Because in the first loop iteration of the for loop you get index 0 corresponding to list[0], that is, bucket[336]. However, your being passed array's size is 11.

If the array's max-valued element is not too high, you can find max element in the array and pass it as a value to the method to define the bucket arrays' size instead of t 1.

CodePudding user response：

Long Ago I have implemented bucketsort you can check my example below.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class BucketSort {

    int arr[];

    // Constructor
    public BucketSort(int arr[]) {
        this.arr = arr;
    }

    // Prints Array
    public void printArray() {
        int tmp = 0; /// This variable is used to print 20 element in one line and after that move to next line
        for (int i = 0; i < arr.length; i  ) {
            System.out.print(arr[i]   " ");
            tmp  ;
            if (tmp == 20) {
                System.out.println();
                tmp = 0;
            }
        }
    }

    // Prints Buckets
    public void printBucket(ArrayList<Integer>[] buckets) {
        for (int i = 0; i < buckets.length; i  ) {
            System.out.println("\nBucket#"   i   " :");
            for (int j = 0; j < buckets[i].size(); j  ) {
                System.out.print(buckets[i].get(j)   "  ");
            }
        }

    }

    // Sorting method
    public void bucketSort() {

        // Create sqrt# of buckets, so that the distribution is even
        int numberOfBuckets = (int) Math.ceil(Math.sqrt(arr.length));
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        // Find the min and max value from the array
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        // Create an array of buckets
        ArrayList<Integer>[] buckets = new ArrayList[numberOfBuckets];

        // initializing empty buckets
        for (int i = 0; i < buckets.length; i  ) {
            buckets[i] = new ArrayList<Integer>();
        }

        for (int value : arr) {
            int bucketNumber = (int) Math.ceil((value * numberOfBuckets) / maxValue);
            System.out.println("bucketNumber length: "   buckets.length);
            System.out.println("bucketNumber: "   bucketNumber);
            buckets[bucketNumber - 1].add(value);
        }

        System.out.println("\n\nPrinting buckets before Sorting...");
        printBucket(buckets);

        // Sort Buckets
        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }

        System.out.println("\n\nPrinting buckets after Sorting...");
        printBucket(buckets);

        // concatenate buckets
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            for (int value : bucket) {
                arr[index] = value;
                index  ;
            }
        }
    }// end of method

    public static void main(String[] args) {

        int arr[] = new int[100];

        // Generating 100 random numbers in the range of 0-100
        Random random = new Random();
        for (int i = 0; i < 100; i  ) {
            arr[i] = random.nextInt(100)   100;
        }

        // Passing this array to BucketSort method
        BucketSort bs = new BucketSort(arr);
        System.out.println("Array before Sorting: ");
        bs.printArray();
        bs.bucketSort();

        System.out.println("\n\nArray after Sorting: ");
        bs.printArray();

    }
}