Sorting is one of the most common tasks in programming, and it’s essential for organizing and managing data efficiently. Whether you are developing a small student grading system or handling complex numerical data, sorting ensures that information can be accessed quickly and easily. In C programming, there are many sorting algorithms available, each with its own logic and performance level. One of the most interesting and efficient algorithms for sorting numbers, especially those that are uniformly distributed, is the Bucket Sort algorithm.
with hands-on learning.
get the skills and confidence to land your next move.
Bucket Sort works by dividing elements into several groups called buckets. Each bucket is sorted individually, either using another sorting algorithm or by sorting it directly. Once all buckets are sorted, the elements are combined to form a final sorted array. This approach is inspired by how we might sort real-world items like coins — placing them in separate trays based on value and then ordering them neatly within each tray. Bucket Sort is a perfect example of how logical thinking can make a complex problem easier to handle.
Program 1: Basic Implementation of Bucket Sort Using Loops
The first program demonstrates a simple way to implement Bucket Sort using loops. It takes an array of floating-point numbers between 0 and 1 and sorts them efficiently.
#include <stdio.h>
#include <stdlib.h>
void bucketSort(float arr[], int n) {
float buckets[10][10];
int bucketCount[10];
for (int i = 0; i < 10; i++)
bucketCount[i] = 0;
for (int i = 0; i < n; i++) {
int bucketIndex = arr[i] * 10;
buckets[bucketIndex][bucketCount[bucketIndex]++] = arr[i];
}
for (int i = 0; i < 10; i++) {
for (int j = 1; j < bucketCount[i]; j++) {
float temp = buckets[i][j];
int k = j - 1;
while (k >= 0 && buckets[i][k] > temp) {
buckets[i][k + 1] = buckets[i][k];
k--;
}
buckets[i][k + 1] = temp;
}
}
int index = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < bucketCount[i]; j++) {
arr[index++] = buckets[i][j];
}
}
}
int main() {
float arr[] = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%f ", arr[i]);
printf("\n");
bucketSort(arr, n);
printf("\nSorted array:\n");
for (int i = 0; i < n; i++)
printf("%f ", arr[i]);
printf("\n");
return 0;
}In this code, the array elements are first distributed into buckets depending on their range. Each bucket is then sorted using a simple insertion sort. Finally, all the sorted buckets are combined to form the final sorted list. The logic is simple yet powerful, and beginners can easily understand how sorting in parts can make the whole process faster.
Program 2: Bucket Sort Using Recursion
In this second approach, we’ll use recursion to perform the sorting of elements inside each bucket. This version shows how recursive logic can replace loops to make the algorithm more elegant and modular.
#include <stdio.h>
#include <stdlib.h>
void recursiveInsertionSort(float arr[], int n) {
if (n <= 1)
return;
recursiveInsertionSort(arr, n - 1);
float last = arr[n - 1];
int j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
void bucketSortRecursive(float arr[], int n) {
float buckets[10][10];
int bucketCount[10] = {0};
for (int i = 0; i < n; i++) {
int index = arr[i] * 10;
buckets[index][bucketCount[index]++] = arr[i];
}
for (int i = 0; i < 10; i++) {
recursiveInsertionSort(buckets[i], bucketCount[i]);
}
int index = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < bucketCount[i]; j++) {
arr[index++] = buckets[i][j];
}
}
}
int main() {
float arr[] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%f ", arr[i]);
printf("\n");
bucketSortRecursive(arr, n);
printf("\nSorted array:\n");
for (int i = 0; i < n; i++)
printf("%f ", arr[i]);
printf("\n");
return 0;
}In this recursive version, instead of using loops to sort each bucket, the program calls a recursive function that sorts the elements one by one. This approach is especially helpful for students learning recursion in C programming because it shows how recursion can replace repetitive loop structures. The main logic of Bucket Sort remains the same, making it easy to connect both versions conceptually.
Program 3: Bucket Sort with User Input
For learners who want to make their program interactive, here’s a version that allows users to enter the elements themselves. It’s a practical way to apply what you’ve learned and make your program more dynamic.
#include <stdio.h>
#include <stdlib.h>
void bucketSort(float arr[], int n) {
float buckets[10][10];
int bucketCount[10] = {0};
for (int i = 0; i < n; i++) {
int index = arr[i] * 10;
buckets[index][bucketCount[index]++] = arr[i];
}
for (int i = 0; i < 10; i++) {
for (int j = 1; j < bucketCount[i]; j++) {
float temp = buckets[i][j];
int k = j - 1;
while (k >= 0 && buckets[i][k] > temp) {
buckets[i][k + 1] = buckets[i][k];
k--;
}
buckets[i][k + 1] = temp;
}
}
int index = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < bucketCount[i]; j++) {
arr[index++] = buckets[i][j];
}
}
}
int main() {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
float arr[n];
printf("Enter %d elements (values between 0 and 1):\n", n);
for (int i = 0; i < n; i++)
scanf("%f", &arr[i]);
bucketSort(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%f ", arr[i]);
printf("\n");
return 0;
}This user-input version helps learners understand how to handle real-time data and sort it effectively. The logic remains the same: distribute numbers into buckets, sort each one, and then merge the results. By taking user input, this version becomes interactive and practical, showing how sorting algorithms can be applied in real-world scenarios.
Program 4: Bucket Sort for Integers
This program demonstrates how to implement Bucket Sort for integer arrays. Instead of using floating-point buckets between 0 and 1, it dynamically creates buckets based on the range of the integers. This is useful for arrays with a wide range of positive integers.
#include <stdio.h>
#include <stdlib.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void bucketSortIntegers(int arr[], int n) {
if (n <= 0)
return;
// Find the maximum value to determine bucket size
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
int bucketCount = max / 10 + 1; // Adjust bucket size as needed
int **buckets = (int **) malloc(bucketCount * sizeof(int *));
int *bucketSizes = (int *) malloc(bucketCount * sizeof(int));
for (int i = 0; i < bucketCount; i++) {
buckets[i] = (int *) malloc(n * sizeof(int)); // Maximum possible size
bucketSizes[i] = 0;
}
// Distribute array elements into buckets
for (int i = 0; i < n; i++) {
int index = arr[i] / 10; // Assign bucket based on range
buckets[index][bucketSizes[index]++] = arr[i];
}
// Sort individual buckets using insertion sort
for (int i = 0; i < bucketCount; i++)
insertionSort(buckets[i], bucketSizes[i]);
// Merge all buckets back into original array
int index = 0;
for (int i = 0; i < bucketCount; i++)
for (int j = 0; j < bucketSizes[i]; j++)
arr[index++] = buckets[i][j];
// Free allocated memory
for (int i = 0; i < bucketCount; i++)
free(buckets[i]);
free(buckets);
free(bucketSizes);
}
int main() {
int arr[] = {42, 32, 23, 52, 25, 47, 51, 12, 37};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
bucketSortIntegers(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}In this integer version, we first determine the maximum value to decide how many buckets we need. Each integer is then placed in the appropriate bucket based on its range. Individual buckets are sorted using Insertion Sort, and finally, all buckets are merged to form the sorted array.
This approach works for arrays of positive integers of varying ranges and is highly educational for beginners learning to adapt algorithms to different types of data. It also shows how dynamic memory allocation in C can be used to manage buckets efficiently.
Frequently Asked Questions (FAQ)
In this section, we’ll clear up some common questions beginners often have about the Bucket Sort algorithm.
What is the main idea behind Bucket Sort?
The main concept of Bucket Sort is to divide elements into smaller groups or buckets based on their range, sort each bucket individually, and then combine them to get the final sorted list.
When should I use Bucket Sort?
Bucket Sort works best when the input data is uniformly distributed over a range, such as floating-point numbers between 0 and 1.
Is Bucket Sort faster than Quick Sort or Merge Sort?
In some cases, yes. When the data is uniformly distributed and not too large, Bucket Sort can outperform Quick Sort and Merge Sort. However, for large datasets, the latter may still be faster.
Conclusion
Bucket Sort is an elegant sorting algorithm that divides and conquers the sorting problem by grouping similar data together. For beginners learning C programming, it’s a great example of how mathematical logic and structured thinking can lead to efficient solutions.
Whether you use loops or recursion, understanding how Bucket Sort works will deepen your knowledge of algorithm design and data management. With practice, you’ll be able to adapt this technique for a wide range of applications — from simple school projects to complex data processing systems. So, open your C compiler, type the code, and start sorting your way to mastery.
