Explaning Bucket Sort Algorithm

BucketSort class

The BucketSort class implements the bucket sort algorithm, which distributes elements into buckets, sorts each bucket, and then concatenates the sorted buckets back into the original array. This method is efficient for uniformly distributed data but can degrade to quadratic time complexity in the worst case.

    public class BucketSort
    {
        public void Sort(int[] array)
        {
            int n = array.Length;
            if (n <= 0)
                return;

            // Find the maximum value in the array to determine the range
            int maxValue = array[0];
            for (int i = 1; i < n; i++)
            {
                if (array[i] > maxValue)
                    maxValue = array[i];
            }

            // Create empty buckets
            List<int>[] buckets = new List<int>[n];
            for (int i = 0; i < n; i++)
            {
                buckets[i] = new List<int>();
            }

            // Put array elements in different buckets
            for (int i = 0; i < n; i++)
            {
                int bucketIndex = (array[i] * n) / (maxValue + 1);
                buckets[bucketIndex].Add(array[i]);
            }

            // Sort individual buckets
            for (int i = 0; i < n; i++)
            {
                buckets[i].Sort();
            }

            // Concatenate all buckets into array
            int index = 0;
            for (int i = 0; i < n; i++)
            {
                foreach (var item in buckets[i])
                {
                    array[index++] = item;
                }
            }
        }

    }

Code Explanation

1. Initialization and Edge Case Handling

   int n = array.Length;
   if (n <= 0)
       return;
   

   • The method first checks the length of the array. If the array is empty, it returns immediately.

2. Finding the Maximum Value

   int maxValue = array[0];
   for (int i = 1; i < n; i++)
   {
       if (array[i] > maxValue)
           maxValue = array[i];
   }
   

   • This loop iterates through the array to find the maximum value, which is used to determine the range for bucket distribution.

3. Creating Empty Buckets

   List<int>[] buckets = new List<int>[n];
   for (int i = 0; i < n; i++)
   {
       buckets[i] = new List<int>();
   }
   

   • An array of lists (buckets) is created. Each bucket is initialized as an empty list.

4. Distributing Elements into Buckets

   for (int i = 0; i < n; i++)
   {
       int bucketIndex = (array[i] * n) / (maxValue + 1);
       buckets[bucketIndex].Add(array[i]);
   }
   

   • Each element in the array is placed into a bucket based on its value. The bucket index is calculated using the formula (array[i] * n) / (maxValue + 1).

5. Sorting Individual Buckets

   for (int i = 0; i < n; i++)
   {
       buckets[i].Sort();
   }
   

   • Each bucket is sorted individually using the Sort method, which typically uses an efficient sorting algorithm like QuickSort or Timsort.

6. Concatenating All Buckets

   int index = 0;
   for (int i = 0; i < n; i++)
   {
       foreach (var item in buckets[i])
       {
           array[index++] = item;
       }
   }
   

   • The sorted elements from all buckets are concatenated back into the original array.

Time Complexity Analysis

1. Finding the Maximum Value

   • Time complexity:
     O(n)O(n)

2. Creating Empty Buckets

   • Time complexity:
     O(n)O(n)

3. Distributing Elements into Buckets

   • Time complexity:
     O(n)O(n)

4. Sorting Individual Buckets

   • In the worst case, if all elements end up in one bucket, the time complexity is
     O(n^2)O(n2)
     due to insertion sort.
   • In the average case, assuming uniform distribution, the time complexity is
     O(n)O(n)

5. Concatenating All Buckets

   • Time complexity:
     O(n)O(n)

Output. Below is the output for i/p -> [42, 32, 23, 52, 23, 47, 51]

Summary of Time Complexity

• Worst Case
  O(n^2)
  (when all elements end up in a single bucket)
• Average Case
  O(n)
  (assuming uniform distribution of elements across buckets)
• Best Case
  O(n + k): (when elements are evenly distributed across buckets, with
  k: being the number of buckets)