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

In bucket sort algorithm the array elements are distributed into a number of buckets. Then each bucket sorted individually either using any other sorting algorithm or by recursively applying bucket sort.

Take example shown in below image.

Elements are distributed among buckets

Then, elements are sorted within each bucket

Below is the program to implement this algorithm. In this program it is assumed that the array elements are between 0 to 10.

## Program for Bucket Sort in C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#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 Sort in C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#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 *

Youneswhat does it mean ++buckets[a[i]]; !?

RAHUL KUMARthere is mistake in c++ program which is value is SIZE is not given

123SIZE is a preprocessor directive

birjeshohh…hello it’s not bucket sort ,your coding is almost like counting sort……….u r making a fool of us …..first learn what bucket sort is okk

M G NkwenkwatThis is not working at all. I changed the values in the array and no sorting takes place

k2This is not Bucket Sort but Counting Sort – the difference is that in Counting Sort you count how much times the number appears in array (like in your code) which is good for integers but bad for floats. Bucket Sort works with floats – it creates “buckets” – array of lists, divide elements by liknking them to appropriate lists (that every element in list a[i-1] are lower than element in list a[i], every elements in list a[i] are lower than every element in list a[i+1] etc.) next you sort elements in lists using whatever you want (there are few elements than this can be Insertion Sort – will be fast) and then you rewrite sorted elements form lists back to array.

VivekThis is counting sort, brthr!!

If you are saying it bucket_sort, the how can you say a bucket can have only 1 element.

Plzz do post only you are fully sure!!!

MaricrisHey? Can I ask something? What is the code when the users enter 10 numbers by using bucket sort in html? Thankyouuu in advance.