Bucket Sort in C

Problem Description

Write a program to implement Bucket Sort in C.

What is Bucket Sort?

In the bucket sort algorithm, we will create multiple small groups containing a range of elements (called buckets). Then these groups are back joined again and the sorted array is formed. This method is also known as the “scatter and gather algorithm“.

Bucket Sort Procedure:

Basic Ideology behind bucket sort is:

1. Partition the range into number of buckets.
2. Put each element into its corresponding bucket.
3. Sort each bucket individually by applying a sorting algorithm(most probably insertion sort).
4. Merge all sorted buckets to get the sorted array.

Bucket Sort Algorithm:

bucket_sort(a[],n)
    Create buckets
    Initializing all buckets to zero i.e  Empty buckets
    For each element in array[]:
         Add them to their corresponding bucket.
    Sort all buckets individually using any sorting algorithm.
    Merge the sorted buckets together.

Bucket Sort Example:

How do you sort a bucket?

advertisement
advertisement

Suppose, let an array to be sorted is [4 8 2 12 16 19 13 6 7 11] and no of buckets be 4.

   Let range of bucket 1 be: 0-5
   Let range of bucket 2 be: 5-10
   Let range of bucket 3 be: 10-15
   Let range of bucket 4 be: 15-20

After traversing the whole array, buckets will be as follows:

Note: Join free Sanfoundry classes at Telegram or Youtube
   Bucket 1 :   [4,2]
   Bucket 2 :   [8,6,7]
   Bucket 3 :   [12,13,11]
   Bucket 4 :   [16,19]

Sorting each bucket with any of the sorting algorithm (Insertion sort most probably), so buckets are as follows:

   Bucket 1 :   [2,4]
   Bucket 2 :   [6,7,8]
   Bucket 3 :   [11,12,13]
   Bucket 4 :   [16,19]

Now Merging the buckets together:

Sorted Array : [2,4,6,7,8,11,12,13,16,19]
Program/Source Code

Here is the source code of the C program to display sorted array using Bucket sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
  1. /*
  2.  * C Program to Implement Bucket Sort
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include<limits.h>
  7.  
  8. //Function to find maximum element of the array
  9. int max_element(int array[], int size) 
  10. {  
  11.     // Initializing max variable to minimum value so that it can be updated
  12.     // when we encounter any element which is greater than it.
  13.     int max = INT_MIN;  
  14.     for (int i = 0; i < size; i++)
  15.     {
  16.         //Updating max when array[i] is greater than max
  17.         if (array[i] > max)  
  18.         max = array[i];  
  19.     }
  20.     //return the max element
  21.     return max;  
  22. }
  23.  
  24. //Implementing bucket sort 
  25. void Bucket_Sort(int array[], int size) 
  26. {  
  27.     //Finding max element of array which we will use to create buckets
  28.     int max = max_element(array, size); 
  29.  
  30.     // Creating buckets 
  31.     int bucket[max+1];  
  32.  
  33.     //Initializing buckets to zero
  34.     for (int i = 0; i <= max; i++)  
  35.     bucket[i] = 0;  
  36.  
  37.     // Pushing elements in their corresponding buckets
  38.     for (int i = 0; i < size; i++)  
  39.     bucket[array[i]]++;
  40.  
  41.     // Merging buckets effectively
  42.     int j=0;   // j is a variable which points at the index we are updating
  43.     for (int i = 0; i <= max; i++)  
  44.     { 
  45.         // Running while loop until there is an element in the bucket
  46.         while (bucket[i] > 0)  
  47.         {  
  48.             // Updating array and increment j          
  49.             array[j++] = i;  
  50.  
  51.             // Decreasing count of bucket element
  52.             bucket[i]--;   
  53.         }  
  54.     }  
  55. }  
  56.  
  57. /* The main() begins */
  58. int main()
  59. {
  60.     int array[100], i, num; 
  61.  
  62.     printf("Enter the size of array: ");   
  63.     scanf("%d", &num);   
  64.     printf("Enter the %d elements to be sorted:\n",num); 
  65.     for (i = 0; i < num; i++)
  66.         scanf("%d", &array[i]); 
  67.     printf("\nThe array of elements before sorting: \n");
  68.     for (i = 0; i < num; i++)
  69.         printf("%d ", array[i]);  
  70.     printf("\nThe array of elements after sorting: \n"); 
  71.  
  72.     // Calling bucket sort function 
  73.     Bucket_Sort(array, num); 
  74.     for (i = 0; i < num; i++)
  75.         printf("%d ", array[i]);   
  76.     printf("\n");     
  77.     return 0;
  78. }
Program Explanation

1. First input the size of the array.
2. Create an array of given size and input the element of the array.
3. Create a bucket sort function, in that function create a bucket of size m (where m is max element of the bucket).
4. Store the element in their corresponding bucket and then gather them to get a sorted array.

Time Complexity:

Best Case: O(n+k)
It occurs when an array is sorted and no sorting is required. O(n) is complexity of making buckets and O(k) is complexity of sorting buckets (Linear complexity as array is already sorted). So overall complexity of bucket sort in C is O(n+k).

advertisement

Average Case: O(n+k)
It occurs when an array is jumbled(neither in ascending nor in descending order). O(n) is the complexity of making buckets and O(k) is the complexity of sorting buckets. So overall complexity of bucket sort is O(n+k).

Worst Case: O(n*2)
This is the case when all elements are placed in the same bucket. So O(n) is the complexity of making buckets and O(n) is used for sorting them. So overall complexity is O(n*n).

Space Complexity: O(n*k)
Creating ‘n’ buckets and storing elements will take space of order of n*k, So space complexity of bucket sort in C is O(n*k).

Program Output
 
Enter the size of array: 10
Enter the 10 elements to be sorted:
4 5 2 1 3 6 7 9 8 0
The array of elements before sorting: 
4 5 2 1 3 6 7 9 8 0 
The array of elements after sorting: 
0 1 2 3 4 5 6 7 8 9

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.