Bucket Sort algorithm implementation in C

Bucket Sort:

Like as Quick sort and insertion sort, there is another sort called Bucket sort. Bucket sort assumes that the input is drawn from a uniform distribution. Bucket sort runs in linear time on the average which is 0(n). It assumes that the input is generated by a random process that distributes elements uniformly over the interval [0, 1].

Bucket sort works as follows:

•     Set up an array of initially empty buckets
•     Go over the original array, putting each object in its bucket.
•     Sort each non-empty bucket.
•     Visit the buckets in order and put all elements back into the original array.

Suppose we need to sort an array of positive integers.
A= {3,4,11,0,2,8,5,9,1,5,6,2,8,0,2,4,1,3,10,4,7,9}.
A bucket sort works as follows: create an array of size 11. Then, go through the input array and place integer 3 into a second array at index 3, integer 11 at index 11 and so on. We will end up with a sorted list in the second array.
We start with an array of 11 counters set to zero.

Array A:

Moving through the array we increment counters:

Array B:

Next, we simply read off the number of each occurrence :

0,0,1,1,2,2,2,3,3,4,4,4,5,5,6,7,8,8,9,9,10,11

The code of Bucket sort in C is given below:

#include<stdio.h> void Bucket_Sort(int array[], int n) { int i, j; int count[n]; for (i=0; i < n; i++) { count[i] = 0; } for (i=0; i < n; i++) { (count[array[i]])++; } for (i=0,j=0; i < n; i++) { for (; count[i]>0;(count[i])--) { array[j++] = i; } } } int main() { int array[100]; int num; int i; printf("Enter How many Numbers : "); scanf("%d",&num); printf("Enter the %d elements to be sorted:\n",num); for (i = 0; i < num; i++ ) { scanf("%d",&array[i]); } printf("\nThe array of elements before sorting : \n"); for (i = 0;i < num;i++) { printf("%d ", array[i]); } printf("\nThe array of elements after sorting : \n"); Bucket_Sort(array, num); for (i = 0;i < num;i++) { printf("%d ", array[i]); } printf("\n"); return 0; }

Output:

Output Screen

We can say Bucket sort is asymptotically fast (O(n) when distribution is uniform) . It is a simple to code and good for a rough sort.

Related post :

Radix sort algorithm                                                    Bubble sort in java 

Topological sort of directed graph in java                 Binary search  in C

Binary search in java                                                   Breadth First Search(BFS)

Depth First Search ( DFS )

For More Algorithm like Bucket Sort algorithm, click here.