Bucket Sort

Bucket Sort: In the sorting algorithm, we create buckets and put elements into them. We can apply some sorting algorithm (insertion sort) to sort the elements in each bucket. Finally, we take the elements out and join them to get the sorted result.

The bucket sort assumes that the input is generated by a random process that distributes the elements uniformly over the interval (0,1).

The idea of ??bucket sort is to divide the interval 0 to 1 into “n” equal-sized sub-intervals or buckets, and then distribute the n input number to the bucket.

The bucket sort program requires an auxiliary array X [0, 1, 2, ...., n-1] of the linked list.

Complexity table of bucket sort

Complexity	Best case	Average case	Worst case
Time	O(n + k)	O(n + k)	O(n2)
Space			O(n)

Algorithm of bucket sort

Bucket Sort() 
Step 1: Create N buckets and each buckets is hold a range of values. 
Step 2: for i ? 1 to n     // initialize each bucket with 0 values. 
Step 3: for i ? 1 to n     put elements into buckets matching the range. 
Step 4: for i ? 1 to n     sort elements in each bucket.     gather elements from each bucket 
Step 5: exit

For example: Suppose we have the following array, which we have to sort.

11

8

6

1

25

2

Step 1: Create a new array, and this array size is 10. Every field of this array is used as a bucket.  

Step 2: Insert the array element into the new array bucket, and these elements will be added according to the range of the bucket.    

Step 3: Gather the element form each bucket.  

Bucket sort program in C language:

#include <stdio.h> 
 void Bucket_Sort(int array[], int n) 
 {       
 int i, j;    
    int count[n];   
    for (i = 0; i < n; i++)     
      count[i] = 0;       
 for (i = 0; i < n; i++)   
       (count[array[i]])++;   
      for (i = 0, j = 0; i < n; i++)   
         for(; count[i] > 0; (count[i])--)  
            array[j++] = i;   
} 
      int main() 
 {    
  int array[100], i, num;  
        printf("Enter the size of array : ");   
      scanf("%d", &num);  
       printf("Enter the %d elements to be sorted:\n",num); 
      for (i = 0; i < num; i++)  
        scanf("%d", &array[i]);  
     printf("\nThe array of elements before sorting : \n");  
    for (i = 0; i < num; i++)  
        printf("%d ", array[i]);  
      printf("\nThe array of elements after sorting : \n");  
     Bucket_Sort(array, num);   
    for (i = 0; i < num; i++)  
        printf("%d ", array[i]);   
      printf("\n");        
   return 0; 
 } 

Bucket sort program in java language:

import java.util.ArrayList; 
import java.util.Collections;  
 public class BucketSort 
{  
 public void bucketSort(float[] arr, int n)
 {     
if (n <= 0)       return;  
   @SuppressWarnings("unchecked")   
  ArrayList<Float>[] bucket = new ArrayList[n];       // Create empty buckets   
  for (int i = 0; i < n; i++)   
    bucket[i] = new ArrayList<Float>();       // Add elements into the buckets     
for (int i = 0; i < n; i++)
 {     
  int bucketIndex = (int) arr[i] * n;  
     bucket[bucketIndex].add(arr[i]);  
   }  
     // Sort the elements of each bucket     for (int i = 0; i < n; i++) 
{    
   Collections.sort((bucket[i]));   
  }    
   // Get the sorted array     int index = 0;    
 for (int i = 0; i < n; i++) 
{   
    for (int j = 0, size = bucket[i].size(); j < size; j++) 
{      
   arr[index++] = bucket[i].get(j); 
      }    
 }  
 }  
   // Driver code   public static void main(String[] args) 
{   
  BucketSort b = new BucketSort();   
  float[] arr = { (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47,         (float) 0.51 };   
  b.bucketSort(arr, 7); 
      for (float i : arr)       System.out.print(i + "  "); 
  } 
}