Bucket Sort using Linked Lists

Question

I'm trying to implement bucket sort in Java in order to sort an array of integers. I'm am trying to use Linked Lists as my buckets but am having some trouble understanding how to do so. Could anyone provide an implementation?

I've been provided this algorithm, but it doesn't make much sense to me:

Answer 1

Since you have no code to analyze, I will give a written out answer. Create a Bucket class which will contain of range between two numbers (0-9, 10-19, etc.), a insert method (which inserts in order), and contain an empty array. Then create a List of Buckets as so:

Loop through input list and insert each number into the appropriate Bucket inside the Bucket List. As you insert values, it will sort for you. Finally, get all Bucket's arrays and lump then together for the output list.

Here is a step by step process off of Wikipedia:

1. Set up an array of initially empty "buckets".
2. Scatter: Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Gather: Visit the buckets in order and put all elements back into the original array.

This is the algorithm you were provided:

This simple translates to:

1. A is the input array which you must sort
2. n is the length of the input array A
3. You must insert all elements of input array A into your list of Buckets B
4. Now order each Bucket in the Bucket's list B.
5. Create a new list/array to return which will be all ordered Bucket's lists.

NOTE: Step 4 can actually happen as you do step 3 based on your implementation.

This algorithm does not dive into the intricate details which you'll have to code. It is just a simple guide to help you get started.

Answer 2

You might start analyzing this: bucket example

Answer 3

Well , i don't know java but still i can give you algorithm .

The easiest way is to make buckets in form of array , where each array index points to a empty linked list .

for each integer :  
   integer goes to bucket i  // bucket number depends on your implementation 
   pointer = bucket[i]   

   while pointer is not NULL  
      pointer = pointer->next  

   allocate new node
   pointer points to this node
   pointer.data = integer  
   pointer.next = NULL 

Answer 4

You need some way of working out which bucket each element you are sorting needs to go into - you can create an interface that gives you some common method that you can call to do this:

public interface Indexable {
    public int getIndex();
}

Then you can implement a bucket sort algorithm something like this:

public static <T extends Indexable> LinkedList<T> BucketSort( ArrayList<T> listToSort )
{
    // work out how many buckets you need.
    int max = 0;
    for ( T listElement : listToSort )
        max = Math.max( max, listElement.getIndex() );

    // initialise the buckets.
    ArrayList<LinkedList<T>> buckets = new ArrayList<LinkedList<T>>( max );
    for ( int i = 0; i <= max; ++i )
        buckets.add( new LinkedList<T>() );

    // add items to the buckets.
    for ( T listElement : listToSort )
        buckets.get( listElement.getIndex() ).addLast( listElement );

    // concatenate the buckets into a single list.
    LinkedList<T> result = new LinkedList<T>();
    for ( LinkedList<T> bucket : buckets )
        result.addAll( bucket );

    return result;
}

Testing this using a implementation of the Indexable interface which stores an integer and assigns it to a bucket based on the unit digit:

public static class IndexableInteger implements Indexable {
    private final int value;

    public IndexableInteger( int value ) {
        this.value = value;
    }

    public int getIndex() {
        return value % 10;
    }

    public String toString(){
        return Integer.toString( value );
    }
}

Then this:

public static void main(String[] args) {
    ArrayList<IndexableInteger> ints = new ArrayList<IndexableInteger>();
    int[] values = { 45, 71, 16, 31, 0, 25, 6, 51, 40, 81 };
    for ( int v : values )
        ints.add( new IndexableInteger( v ) );

    LinkedList<IndexableInteger> sorted = BucketSort( ints );
    System.out.println( sorted );
}

Outputs this (the numbers are in order of last digit but if they have the same last digit then they are in the same order as the input):

[0, 40, 71, 31, 51, 81, 45, 25, 16, 6]

Note: you probably don't want to use LinkedList as its addAll() method runs in linear time rather than constant time but it's easy to use for a demonstration which is why I used it here.