Bucket Sort in C with Example and Implementation

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?

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.

```
/*
```
```
 * C Program to Implement Bucket Sort
```
```
 */
```
```
 
```
```
#include <stdio.h>
```
```
#include<limits.h>
```
```
 
```

//Function to find maximum element of the array

```
int max_element(int array[], int size) 
```
```
{  
```

    // Initializing max variable to minimum value so that it can be updated

    // when we encounter any element which is greater than it.

```
    int max = INT_MIN;  
```
```
    for (int i = 0; i < size; i++)
```
```
    {
```

        //Updating max when array[i] is greater than max

```
        if (array[i] > max)  
```
```
        max = array[i];  
```
```
    }
```
```
    //return the max element
```
```
    return max;  
```
```
}
```
```
 
```
```
//Implementing bucket sort 
```

void Bucket_Sort(int array[], int size)

```
{  
```

    //Finding max element of array which we will use to create buckets

    int max = max_element(array, size);

```
 
```
```
    // Creating buckets 
```
```
    int bucket[max+1];  
```
```
 
```
```
    //Initializing buckets to zero
```
```
    for (int i = 0; i <= max; i++)  
```
```
    bucket[i] = 0;  
```
```
 
```

    // Pushing elements in their corresponding buckets

```
    for (int i = 0; i < size; i++)  
```
```
    bucket[array[i]]++;
```
```
 
```
```
    // Merging buckets effectively
```

    int j=0;   // j is a variable which points at the index we are updating

```
    for (int i = 0; i <= max; i++)  
```
```
    { 
```

        // Running while loop until there is an element in the bucket

```
        while (bucket[i] > 0)  
```
```
        {  
```

            // Updating array and increment j

```
            array[j++] = i;  
```
```
 
```

            // Decreasing count of bucket element

```
            bucket[i]--;   
```
```
        }  
```
```
    }  
```
```
}  
```
```
 
```
```
/* The main() begins */
```
```
int main()
```
```
{
```
```
    int array[100], i, num; 
```
```
 
```

    printf("Enter the size of array: ");

```
    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");

```
 
```
```
    // Calling bucket sort function 
```
```
    Bucket_Sort(array, num); 
```
```
    for (i = 0; i < num; i++)
```
```
        printf("%d ", array[i]);   
```
```
    printf("\n");     
```
```
    return 0;
```
```
}
```

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).

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”.

« Prev - C Program to Implement KMP Pattern Searching Algorithm

» Next - C Program to Implement Sequential and Binary Search on Same Array

Related Posts:

Bucket Sort Example:

Recommended Articles: