What is Bin/Bucket Sorting? explain with an example

Bin/Bucket sort

Sorting algorithms are fundamental in computer science, as they are used to rearrange elements in a list or array in a specific order. One such algorithm is the Bucket Sort, which is a simple and efficient method for sorting elements into different buckets, hence its name. This sorting algorithm is also known as Bin sort. In this article, we will delve into the details of the Bin/ Bucket Sort algorithm, including its steps, pseudo-code, implementation in C, advantages, disadvantages, and analysis of time and space complexities.

Sorting Algorithm Explained

Bin or Bucket Sort works by distributing the elements of an array into a number of buckets or bins. Each bucket is then sorted individually, either using another sorting algorithm or recursively applying the bucket sort itself. Finally, the sorted elements from all the buckets are concatenated together to obtain the sorted array.

Algorithm Steps

Create Buckets: Create an array of empty buckets. The number of buckets can vary based on the range of input elements or the specific requirements of the sorting problem.

Distribute Elements: Traverse the input array and distribute each element into its corresponding bucket based on some criteria. This criteria could be the value of the element or some function of the element.

Sort Buckets: Sort each individual bucket. This step can be accomplished using any sorting algorithm, such as insertion sort, merge sort, or quicksort. Alternatively, recursion can be employed to apply bucket sort to each bucket.

Concatenate Buckets: Concatenate all the sorted buckets together to obtain the final sorted array.

Source code example

 #include <stdio.h>

 #include <stdlib.h>

 /* Function to perform insertion sort */

 void

 InsertionSort (float arr[], int n)

 {

   for (int i = 1; i < n; i++)

   {

     float temp = arr[i];

     int j = i - 1;

     while (j >= 0 && arr[j] > temp)

     {

       arr[j + 1] = arr[j];

       j--;

     }

     arr[j + 1] = temp;

   }

 }

 /* Function to perform bucket sort */

 void

 BucketSort (float arr[], int n)

 {

   /* Create empty buckets */

   int bucketSize = n;

   float *buckets[bucketSize];

   int buckets_count[bucketSize];

   for (int i = 0; i < bucketSize; i++)

   {

     buckets[i] = NULL;

     buckets_count[i] = 0;

   }

   /* Scatter: Distribute elements into buckets */

   for (int i = 0; i < n; i++)

   {

     int index = bucketSize * arr[i];

     if (buckets[index] == NULL)

     buckets[index] = (float *) malloc (sizeof (float));

     buckets[index] =

     (float *) realloc (buckets[index], (index + 1) * sizeof (float));

     buckets[index][buckets_count[index]] = arr[i];

     buckets_count[index]++;

   }

   /* Sort each bucket using insertion sort */

   for (int i = 0; i < bucketSize; i++)

   {

     if (buckets[i] != NULL)

     {

       InsertionSort (buckets[i], buckets_count[i]);

     }

   }

   /* Gather: Concatenate sorted buckets */

   int index = 0;

   for (int i = 0; i < bucketSize; i++)

   {

     if (buckets[i] != NULL)

     {

       for (int j = 0; j < buckets_count[i]; j++)

       {

         arr[index++] = buckets[i][j];

       }

       free (buckets[i]);

     }

   }

 }

 int

 main ()

 {

   float arr[] = { 0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51 };

   int n = sizeof (arr) / sizeof (arr[0]);

   BucketSort (arr, n);

   printf ("Sorted array: ");

   for (int i = 0; i < n; i++)

   printf ("%.2f ", arr[i]);

   printf ("
");

   return 0;

 }

Advantages

Simple to understand and implement.

Efficient for uniformly distributed input data.

It can be faster than comparison-based sorting algorithms for certain types of data.

Disadvantages

Requires knowledge of the range of input values to allocate the appropriate number of buckets.

Not suitable for sorting large amounts of data or data with a non-uniform distribution.

Additional space complexity due to the need for extra storage for buckets.

Time Complexity:

The time complexity of Bin or Bucket Sort depends on the number of elements and the sorting algorithm used for each bucket. In the worst-case scenario, when all elements are placed in a single bucket, the time complexity is O(n^2). However, on average, when the input is uniformly distributed across buckets, the time complexity is O(n + k), where k is the number of buckets.

Space Complexity:

Bin or Bucket Sort has a space complexity of O(n + k), where n is the number of elements and k is the number of buckets.

Bin or Bucket Sort is a versatile algorithm that can be useful in scenarios where the range of input values is known and relatively small. By distributing elements into buckets and sorting them individually, Bin or Bucket Sort offers a straightforward approach to sorting that can be efficient under the right circumstances.