In this chapter we shall learn about below topics:
10.1 Steps for performing Bucket Sort
10.2 Implementation of Bucket Sort in C
10.3 Output of the program
10.1 Steps for performing Bucket Sort
1. The general idea is to divide the data based on buckets based on some criteria.
2. Then sort the buckets individually.
3. Concatenate those buckets.
The elements will be sorted.
The Number of buckets created is dependent on the programmer. In the below algorithm we divide into 3 buckets.
10.2 Implementation of Bucket Sort in C
#include <stdio.h>
#include <stdlib.h>
struct bucket
{
int count;
int* values;
};
int compareIntegers(const void* first, const void* second)
{
int a = *((int*)first), b = *((int*)second);
if (a == b)
{
return 0;
}
else if (a < b)
{
return -1;
}
else
{
return 1;
}
}
void bucketSort(int array[],int n)
{
struct bucket buckets[3];
int i, j, k;
for (i = 0; i < 3; i++)
{
buckets[i].count = 0;
buckets[i].values = (int*)malloc(sizeof(int) * n);
}
// Divide the unsorted elements among 3 buckets
// < 0 : first
// 0 - 10 : second
// > 10 : third
for (i = 0; i < n; i++)
{
if (array[i] < 0)
{
buckets[0].values[buckets[0].count++] = array[i];
}
else if (array[i] > 10)
{
buckets[2].values[buckets[2].count++] = array[i];
}
else
{
buckets[1].values[buckets[1].count++] = array[i];
}
}
for (k = 0, i = 0; i < 3; i++)
{
// Use Quicksort to sort each bucket individually
qsort(buckets[i].values, buckets[i].count, sizeof(int), &compareIntegers);
for (j = 0; j < buckets[i].count; j++)
{
array[k + j] = buckets[i].values[j];
}
k += buckets[i].count;
free(buckets[i].values);
}
}
int main() {
int array[100] = { -5, -9, 1000, 1, -10, 0, 2, 3, 5, 4, 1234, 7 };
int n = 12;
int k = 0;
bucketSort(array, n);
for (k = 0; k<n; k++)
printf("%d \n", array[k]);
return 0;
}
10.3 Output of the program
-10
-9
-5
0
1
2
3
4
5
7
1000
1234