C Program: Bucket (or Bin) Sort

Given the below set of numbers

(6 2 6 10 3 6 3)

we will make use of the Bucket Sort algorithm to rearrange them in ascending order as follows

(2 3 3 6 6 6 10)

Two parameters need to be computed first:

• the size of the given array of numbers N, and
• the largest element in the array M

We make use of an auxiliary array called aux to temporarily store and count elements. It has the size upto the largest element in the array, plus 1, i.e., M+1.

Initially, all M+1 elements of the auxiliary array are initialized to 0. And then, there is an iteration through the given array of numbers such that each element equalling the index of an element in the auxiliary array has its value incremented by 1 everytime the element occurs.

And lastly, all the incremented elements in the auxiliary array are assigned back to the original array in order. We thus get our sorted array.

The below C program sorts the above given set of numbers (6 2 6 10 3 6 3) based on the Bucket Sort algorithm.

				
				#include <stdio.h>

				int main() {
					// N - the size of given array; M - the largest element of the array
					const unsigned short N = 7, M = 10;

					unsigned short int i, j;
					int numbers[] = {6,2,6,10,3,6,3}, aux[M+1];

					// initializing the auxiliary array elements to 0
					for(i = 0;i <= M;i++) {
						aux[i] = 0;
					}

					// filling the auxiliary array with elements of unsorted array
					for(i = 0; i < N;i++) {
						aux[numbers[i]]++;
					}

					// emptying the auxiliary array
					for(i = 0, j = 0;i <= M; i++) {
						for(; aux[i]>0; (aux[i])--) {
							numbers[j] = i;
							j++;
						}
					}

					// printing the sorted array
					for(i = 0; i < N;i++) {
						printf("%d ", numbers[i]);
					}

					printf("\n");

					return 0;
				}
				
			

On running the program, it prints out the numbers in a sorted order.

				
					$ ./a.out
					2 3 3 6 6 6 10