Writing bucket sort in c++
Here's a bucket sort based on the info in the OP question.
void b_sort(int sarray[], int array_size) {
const int max = array_size;
// use bucket[x][max] to hold the current count
int bucket[10][max+1];
// init bucket counters
for(var x=0;x<10;x++) bucket[x][max] = 0;
// main loop for each digit position
for(int digit = 1; digit <= 1000000000; digit *= 10) {
// array to bucket
for(int i = 0; i < max; i++) {
// get the digit 0-9
int dig = (sarray[i] / digit) % 10;
// add to bucket and increment count
bucket[dig][bucket[dig][max]++] = sarray[i];
}
// bucket to array
int idx = 0;
for(var x = 0; x < 10; x++) {
for(var y = 0; y < bucket[x][max]; y++) {
sarray[idx++] = bucket[x][y];
}
// reset the internal bucket counters
bucket[x][max] = 0;
}
}
}
Notes Using a 2d array for the bucket wastes a lot of space... an array of queues/lists usually makes more sense.
I don't normally program in C++ and the above code was written inside the web browser, so syntax errors may exist.