Bucket Sort

[cool dude]

what is wrong with this bucketsort method? i'm getting an array out of bounds error. i think i'm initializing my 2 dimensional array buckets incorrectly.

code:

public static void BucketSort (int array[], int digit)         {                 int divisor = 10;                 int bucketNumber;                 int elementNumber;                 int buckets[][] = new int[9][7];                                 for (int i = 1; i < digit; i++ )                 {                         divisor = divisor * 10;                 }                 for (int i = 0; i < array.length; i++)                 {                         bucketNumber = ((array[i] % divisor) - (array[i] % (divisor/10))) / (divisor/10);                         elementNumber = buckets[bucketNumber] [0] + 1;                         buckets[bucketNumber] [elementNumber] = array[i];                 }         }

[gsquare567]

couple things, may not solve your problem but might help.
firstly:

code:

divisor = divisor * 10;

its easier to use the *= operator, like so:

code:

divisor *= 10

secondly:
your code is very confusing, but it looks very easy to go out of bounds if you set the bounds as 7 and 9, so maybe try not setting them and see what you get.

[cool dude]

gsquare567 wrote:

couple things, may not solve your problem but might help.
firstly:

code:

divisor = divisor * 10;

its easier to use the *= operator, like so:

code:

divisor *= 10

secondly:
your code is very confusing, but it looks very easy to go out of bounds if you set the bounds as 7 and 9, so maybe try not setting them and see what you get.

1. i need to initialize my array so if i don't then i'll totally go out of bounds!

2. it really makes no difference between

code:

divisor = divisor * 10

and

code:

divisor *=10

It is more of somebodies preference. There is no where in any style written guide that says that is better

[wtd]

The Java code conventions published by Sun do not cover that specifically, however it is generally preferable, as "someVariable *= someNumber" provides less for the brain to have to digest than "someVariable = someVariable * someNumber".

[ericfourfour]

Well, I'm looking off Wikipedia here (I spaced it out so its readable):

code:

function bucket-sort (array, n) is     buckets ← new array of n empty lists     for i = 0 to (length (array) - 1) do         insert array [i] into buckets [msbits (array [i], k)]     for i = 0 to n - 1 do         next-sort (buckets [i])     return the concatenation of buckets [0], ..., buckets [n-1]

I am having trouble understanding this person's pseudo code but I think I get the gist of it.

In the first for loop you are supposed to place the numbers within different ranges in each bucket or is this what you are doing in the second loop? I just see you multiplying this divisor number by 10 which could be simplified by using

code:

Math.pow (10, digit)

I have no clue what I'm talking about when it comes to the bucket sort but the last point is actually helpful.

[wtd]

Note if you see "list" you may wish to translate this into one of Java's List classes.

[gsquare567]

ericfourfour wrote:

Well, I'm looking off Wikipedia here (I spaced it out so its readable):

code:

function bucket-sort (array, n) is     buckets ← new array of n empty lists     for i = 0 to (length (array) - 1) do         insert array [i] into buckets [msbits (array [i], k)]     for i = 0 to n - 1 do         next-sort (buckets [i])     return the concatenation of buckets [0], ..., buckets [n-1]

I am having trouble understanding this person's pseudo code but I think I get the gist of it.

In the first for loop you are supposed to place the numbers within different ranges in each bucket or is this what you are doing in the second loop? I just see you multiplying this divisor number by 10 which could be simplified by using

code:

Math.pow (10, digit)

I have no clue what I'm talking about when it comes to the bucket sort but the last point is actually helpful.

haha great idea with the math.pow, i shuda thot of that.

[Neville]

I'm not familiar with what a bucket sort is supposed to do, but it seems to me that you may be partially correct about setting your bounds. When doing your A%B operations, you can expect remainders up to B-1. The math, while I can't really follow it and make sense of it myself, seems to produce, no matter what you use for your "digit" argument, values from 0-9. So, your ArrayOutOfBounds happens when you give a number close to a multiple of 10 (say 999) with a low enough value for digit, which produces a bucketNumber of 9, which is out of bounds. Try:

code:

int buckets = new int[10][7];

.

Then you will see your real problem is that elementNumber is always 1, meaning your buckets array doesn't get populated much.

[cool dude]

the algorithm of my bucket sort is mostly wrong because i was given the pseudo code and i followed it. however the pseudo code given to me was incorrect. My teacher just cancelled this assignment, however i'm probably going to write the code from scratch just for fun. Thanks for everyones help.

[zylum]

very commonly the bucket sort sorts using individual bits rather than the digits in the number. its also commonly known as the radix sort..

heres a version i came up with:

Java:

static void bucketSort(int[] list, int bits) {                 int idx, mask = ((int) Math.pow(2, bits) - 1);         LinkedList[] buckets = new LinkedList[(int) Math.pow(2, bits)];         for (int i = 0; i < buckets.length; i++) buckets[i] = new LinkedList();                 for (int i = 0; i <= 32; i += bits)         {                 for (int j = 0; j < list.length; j++)                         buckets[(list[j] >> i) & mask].offer(new Integer(list[j]));                 idx = 0;                 for (int j = 0; j < buckets.length; j++)                         while (buckets[j].size() > 0)                                 list[idx++] = ((Integer) buckets[j].remove()).intValue();         }         }

list is obviously the numbers you want to sort. bits is the number of bits you want to examine per pass. the fewer the bits the less memory you use but more passes to do. it creates 2^bits buckets because there are that many different numbers with 'bits' bits. it uses bit masking to read each section of bits. if youre interested in the technique, you can read my bitwise operators tutorial in the turing tutorials. since an integer has 32 bits, a good number for bits is 8. this produces 128 buckets and only requires 4 passes so its a good compremise between speed and memory.