rendered paste bodyimport java.util.LinkedList;
public class BucketSort {
public static void main(String[] args) {
int[] numbers = {34,56,32,123,45,54,76,63,7,321,432,67,8,321,456,234,5,432,3,21,43,2};
int[] output = bucketSort(numbers, 10);
for(int i = 0; i < output.length; i++)
System.out.print(output[i] + " ");
}
/**
* Sort using a Bucket Sort Algorithm
*/
public static int[] bucketSort(int[] toSort, int N) {
LinkedList[] buckets = new LinkedList[N];
// Initialize the Empty buckets
for(int i = 0; i < N; i++) {
buckets[i] = new LinkedList();
}
int len = toSort.length;
int max = 0;
for(int i = 0; i < len; i++)
if(toSort[i] > max)
max = toSort[i];
//if (max == 0) return null;
System.out.println("Max " + max);
int hashValue = max / N;
System.out.println("Len " + len);
System.out.println("Hash " + hashValue);
for(int i = 0; i < len; i++) {
int key;
if (hashValue == 0) {
key = 0;
} else {
key = toSort[i] / hashValue;
}
//System.out.println("Len " + len + " I " + i + " Sort Num: " + toSort[i] + " key: " + key);
if (key >= N) key = N - 1;
buckets[key].add(new Integer(toSort[i]));
//buckets[0].add(new Integer(0));//toSort[0]));
}
int[] sortedArray = new int[len];
int spot = 0;
for(int i = 0; i < N; i++) {
//System.out.println("I: " + i + " buckets.length " + buckets.length);
Object[] tmpCurrentBucket = buckets[i].toArray();
int[] currentBucket = new int[tmpCurrentBucket.length];
for(int j = 0; j < currentBucket.length; j++){
//System.out.println("J " + j);
currentBucket[j] = ((Integer)tmpCurrentBucket[j]).intValue();
//if (N > 1) N = N / 2;
if(currentBucket.length > 2)
currentBucket = bucketSort(currentBucket, N);
for(int k = 0; j < currentBucket.length; k++) {
sortedArray[spot++] = currentBucket[k];
}
}
}
return sortedArray;
}
}