In this tutorial you will learn about the C Program to implement Bucket sort Algorithm and its application with practical example.
C Program to implement Bucket sort Algorithm
In this tutorial, we will learn to create a C program that will do Bucket sort using C programming.
Prerequisites
Before starting with this tutorial we assume that you are best aware of the following C programming topics:
- Operators in C Programming.
- Basic Input and Output function in C Programming.
- Basic C programming.
- For loop in C Programming.
- Creating and Using the user-defined function in C programming.
What is Bucket Sort?
In every programming language, the sorting of data is a very important factor. In C Language. Many different techniques for sorting are available to work with but in this tutorial, we will focus on the BucketSort Technique.
In this technique, we will create multiple small groups containing a range of elements. Then these groups are back joint again and the sorted array is formed.
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 |
Bucket Sort(A[]) 1. Let B[0....n-1] be a new array 2. n=length[A] 3. for i=0 to n-1 4. make B[i] an empty list 5. for i=1 to n 6. do insert A[i] into list B[n a[i]] 7. for i=0 to n-1 8. do sort list B[i] with insertion-sort 9. Concatenate lists B[0], B[1],........, B[n-1] together in order End |
Program For Bucket Sort
|
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 |
#include <stdio.h> int getMax(int x[], int no) // function for getting maximum element from the given array { int max = x[0]; for (int i = 1; i < no; i++) if (x[i] > max) max = x[i]; return max; } void bucket(int x[], int no) // function for implementing bucket sort { int max = getMax(x, no); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i] = 0; } for (int i = 0; i < no; i++) { bucket[x[i]]++; } for (int i = 0, j = 0; i <= max; i++) { while (bucket[i] > 0) { x[j++] = i; bucket[i]--; } } } void printArr(int x[], int no) // function for printing array elements { for (int i = 0; i < no; ++i) printf("%d ", x[i]); } int main() { int x[] = { 79, 99, 12, 66, 3, 8 }; int no = sizeof(x) / sizeof(x[0]); // nois the size of array printf("Elenemts of array before sorting are - \n"); printArr(x, no); bucket(x, no); printf("\nElenemts of array after sorting are - \n"); printArr(x, no); } |
Output:-
In the above program, we have first declared and initialized a set of variables required in the program.
- n = it will hold the size of the array.
- x[]= it will hold the elements in an array.
- i = it will control the for loop for the array.
Function to print array:-
Function for getting the max number.
Bucket sort function.
Main function body.
