JavaGian java tutorial and java interview question and answer

JavaGian , Free Online Tutorials, JavaGian provides tutorials and interview questions of all technology like java tutorial, android, java frameworks, javascript, ajax, core java, sql, python, php, c language etc. for beginners and professionals.

What is Bucket Sort?

Bucket Sort

Bucket sort is also known as bin sort. It works by distributing the element into the array also called buckets. Buckets are sorted individually by using different sorting algorithm.

Complexity of Bucket Sort

AlgorithmComplexity
SpaceO(1)
Worst CaseO(n2)
Best CaseΩ(n+k)
Average Caseθ(n+k)

Algorithm

  • Step 1 START
  • Step 2 Set up an array of initially empty "buckets".
  • Step 3 Scatter: Go over the original array, putting each object in its bucket.
  • Step 4 Sort each non-empty bucket.
  • Step 5 Gather: Visit the buckets in order and put all elements back into the original array.
  • Step 6 STOP
Program
  1. #include <stdio.h>  
  2. void Bucket_Sort(int array[], int n)  
  3. {    
  4.     int i, j;    
  5.     int count[n];   
  6.     for (i = 0; i < n; i++)  
  7.         count[i] = 0;  
  8.    
  9.     for (i = 0; i < n; i++)  
  10.         (count[array[i]])++;  
  11.    
  12.     for (i = 0, j = 0; i < n; i++)    
  13.         for(; count[i] > 0; (count[i])--)  
  14.             array[j++] = i;  
  15. }     
  16. /* End of Bucket_Sort() */  
  17.    
  18. /* The main() begins */  
  19. int main()  
  20. {  
  21.     int array[100], i, num;   
  22.    
  23.     printf("Enter the size of array : ");     
  24.     scanf("%d", &num);     
  25.     printf("Enter the %d elements to be sorted:\n",num);   
  26.     for (i = 0; i < num; i++)  
  27.         scanf("%d", &array[i]);   
  28.     printf("\nThe array of elements before sorting : \n");  
  29.     for (i = 0; i < num; i++)  
  30.         printf("%d ", array[i]);    
  31.     printf("\nThe array of elements after sorting : \n");   
  32.     Bucket_Sort(array, num);   
  33.     for (i = 0; i < num; i++)  
  34.         printf("%d ", array[i]);     
  35.     printf("\n");       
  36.     return 0;  
  37. }  

.