How to get BucketSort algorithm working?

Question

I am trying to create a bucketsort algorithm in C++, but it is not working at all. Every run, it adds many new numbers, often very large, such as in the billions, into the array. Does anyone know why this is? Here is the code - (Note that I am passing in an array of size 100, with random numbers from 0 to ~37000, and that the insertion sort function is fully functional and tested multiple times)

It would be greatly appreciated if someone could point out what's wrong.

void bucketSort(int* n, int k) 
{
    int c = int(floor(k/10)), s = *n, l = *n;
    for(int i = 0; i < k; i++) {
        if(s > *(n + i)) s = *(n + i);
        else if(l < *(n + i)) l = *(n + i);
    }
    int bucket[c][k + 1];
    for(int i = 0; i < c; i++) {
        bucket[i][k] = 0;
    }

    for(int i = 0; i < k; i++) {
        for(int j = 0; j < c; j++) {
            if(*(n + i) >= (l - s)*j/c) {
                continue;
            } else {
                bucket[j][bucket[j][k]++] = *(n + i);
                break;
            }
        }
    }

    for(int i = 0; i < c; i++) {
        insertionSort(&bucket[i][0], k);
    }
}

Answer 1

This line does not compile. int bucket[c][k + 1];

I think the problem is with you bucket indices. This part here

for(int j = 0; j < c; j++) {
   if(*(n + i) >= (l - s)*j/c) {
        continue;
   } else {
        bucket[j][bucket[j][k]++] = *(n + i);
        break;
   }
}

does not do the equivalent of:

  insert n[i] into bucket[ bucketIndexFor( n[i]) ]

First it gets the index off by one. Because of that it also misses the break for the numbers for the last bucket. There is also a small error introduced because the index calculation uses the range [0,l-s] instead of [s,l], which are only the same if s equals 0.

When I write bucketIndex as:

int bucketIndex( int n, int c, int s, int l )
{
    for(int j = 1; j <= c; j++) {
        if(n > s + (l-s)*j/c) {
            continue;
        } else {
            return j-1;
        }
    }
    return c-1;
}

and rewrite the main part of your algorithm as:

std::vector< std::vector<int> > bucket( c );

for(int i = 0; i < k; i++) {
    bucket[ bucketIndex( n[i], c, s, l ) ].push_back( n[i] );
}

I get the items properly inserted into their buckets.