The Bucket Sort algorithm is used for sorting arrays that have values equally distributed inside a range. We create a few buckets for values, for instance one bucket holds the numbers from 0 to 4, the next from 5 to 9, then from 10 to 14. After inserting the corresponding elements inside, we must sort them. In the end we put all the buckets together, in a sorted manner.
// Bucket Sort
#include <iostream>
using namespace std;
struct bucket
{
int howMany;
int* value;
};
// Used for sorting
int compareIntegers(const void* first, const void* second)
{
int x = *((int*)first), y = *((int*)second);
if (x == y)
{
return 0;
}
else if (x < y)
{
return -1;
}
else
{
return 1;
}
}
void bucketSort(int arrayOfNumbers[],int numberOfElements, int numberOfBuckets)
{
//Create the buckets
struct bucket buckets[numberOfBuckets];
for (int i = 0; i < numberOfBuckets; i++)
{
buckets[i].howMany = 0;
buckets[i].value = (int*)malloc(sizeof(int) * numberOfElements);
}
// Add values to buckets
for (int i = 0; i < numberOfElements; i++)
{
if (arrayOfNumbers[i] < 10)
{
buckets[0].value[buckets[0].howMany++] = arrayOfNumbers[i];
}
else if (arrayOfNumbers[i] > 20)
{
buckets[2].value[buckets[2].howMany++] = arrayOfNumbers[i];
}
else
{
buckets[1].value[buckets[1].howMany++] = arrayOfNumbers[i];
}
}
// Sort the elements in a bucket
for (int k = 0, i = 0; i < numberOfBuckets; i++)
{
qsort(buckets[i].value, buckets[i].howMany, sizeof(int), &compareIntegers);
for (int j = 0; j < buckets[i].howMany; j++)
{
arrayOfNumbers[k + j] = buckets[i].value[j];
}
k += buckets[i].howMany;
free(buckets[i].value);
}
}
void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
for (int i = 0; i < numberOfElements; ++i)
{
cout << arrayOfNumbers[i] << " ";
}
cout << endl;
}
int main(void)
{
int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
int numberOfBuckets = 3;
bucketSort(arrayOfNumbers, numberOfElements, numberOfBuckets);
cout<<"The sorted array is: \n";
printElementsOfArray(arrayOfNumbers, numberOfElements);
}
Comments