Bucket Sort in C and C++

Here you will get the program for bucket sort in C and C++.

In bucket sort calculation the exhibit components are circulated into various buckets. At that point, each bucket sorted

exclusively either utilizing some other sorting calculation or by recursively applying bucket sort.

The following is the program to execute this calculation. In this program, it is expected that the exhibit components are between 0 to 10.

Program For Bucket in C

#include <stdio.h>
#include <stdlib.h>
 
struct bucket 
{
    int count;
    int* value;
};
 
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 array[],int n)
{
    struct bucket buckets[3];
    int i, j, k;
    for (i = 0; i < 3; i++)
    {
        buckets[i].count = 0;
        buckets[i].value = (int*)malloc(sizeof(int) * n);
    }
    
    for (i = 0; i < n; i++)
    {
        if (array[i] < 0)
        {
            buckets[0].value[buckets[0].count++] = array[i];
        }
        else if (array[i] > 10)
        {
            buckets[2].value[buckets[2].count++] = array[i];
        }
        else
        {
            buckets[1].value[buckets[1].count++] = array[i];
        }
    }
    for (k = 0, i = 0; i < 3; i++)
    {
        // now using quicksort to sort the elements of buckets
        qsort(buckets[i].value, buckets[i].count, sizeof(int), &compareIntegers);
        for (j = 0; j < buckets[i].count; j++)
        {
            array[k + j] = buckets[i].value[j];
        }
        k += buckets[i].count;
        free(buckets[i].value);
    }
}
 
int main(char *arg[]) {
 
    int array[100] = { 5, -34, 10, 1, -42, 123, 2, 395, 5, 4, 1234, 7 };
    int i = 12,j,k,n;
 
    n=i;
    printf("Before Sorting\n");
    for (j = 0; j<i; j++)
    {
        printf("%d ", array[j]);
    }
 
    bucketSort(array, n); 
    printf("\n After Sorting\n");
    for (k = 0; k<i; k++)
        printf("%d ", array[k]);   
 
 
    return 0;
}

Output

Before Sorting
5 -34 10 1 -42 123 2 395 5 4 1234 7
After Sorting
-42 -34 1 2 4 5 5 7 10 123 395 1234

Program For Bucket in C++

#include <iostream>
#include <algorithm>
#include <vector> //used for the sake of simplicity
using namespace std;
 
 
void bucketSort(float arr[], int n)
{
    vector<float> b[n];
    
    for (int i=0; i<n; i++)
    {
       int x = n*arr[i];
       b[x].push_back(arr[i]);
    }
 
    for (int i=0; i<n; i++)
       sort(b[i].begin(), b[i].end());
 
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
          arr[index++] = b[i][j];
}
 
int main()
{
    float arr[] = {0.235, 0.101, 0.476, 0.7645, 0.15, 0.142};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Before Sorting\n";
    for (int i=0; i<n; i++)
    cout << arr[i] << " ";
    
    bucketSort(arr, n);
    
    cout << "\nAfter Sorting \n";
    for (int i=0; i<n; i++)
       cout << arr[i] << " ";
    return 0;
}

Output

Before Sorting
0.235 0.101 0.476 0.7645 0.15 0.142
After Sorting
0.101 0.142 0.15 0.235 0.476 0.7645

Leave a Comment

error: Alert: Content is protected!!