Bucket sort program in C#

Bucket sort is a comparison-based sorting algorithm that works by partitioning an array into a finite number of "buckets" or subranges, and then individually sorting each bucket using another sorting algorithm or recursively applying bucket sort. It is often used when the input data is uniformly distributed over a range. Bucket sort has an average-case time complexity of O(n + k), where n is the number of elements and k is the number of buckets or subranges.

Here's an explanation of the bucket sort algorithm step by step:

1. Determine the number of buckets: Decide on the number of buckets to use. The number of buckets can be determined based on the range of the input elements and the desired distribution.
2. Partition the elements into buckets: Iterate through the input array and distribute each element into its respective bucket based on a hashing or mapping function. The mapping function should evenly distribute the elements across the buckets.
3. Sort each bucket: Apply a sorting algorithm to sort each bucket individually. This can be done recursively by applying bucket sort to each non-empty bucket, or you can use another sorting algorithm such as insertion sort, quicksort, or mergesort to sort each bucket.
4. Concatenate the sorted buckets: After sorting each bucket, concatenate them back into a single sorted array.

Here's an example implementation of bucket sort in C#:

using System;
using System.Collections.Generic;

public class BucketSort
{
    public static void Main()
    {
        double[] arr = { 0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51 };

        Console.WriteLine("Original array:");
        PrintArray(arr);

        Sort(arr);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }

    public static void Sort(double[] arr)
    {
        int n = arr.Length;

        // Create an array of empty buckets
        List[] buckets = new List[n];

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

        // Distribute elements into buckets
        for (int i = 0; i < n; i++)
        {
            int bucketIndex = (int)(n * arr[i]);
            buckets[bucketIndex].Add(arr[i]);
        }

        // Sort each bucket using insertion sort
        for (int i = 0; i < n; i++)
        {
            buckets[i].Sort();
        }

        // Concatenate the sorted buckets
        int index = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < buckets[i].Count; j++)
            {
                arr[index++] = buckets[i][j];
            }
        }
    }

    public static void PrintArray(double[] arr)
    {
        foreach (double num in arr)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

In this example, the Sort method implements the bucket sort algorithm. The Main method initializes an array of double values, calls the Sort method to sort the array, and then prints both the original and sorted arrays using the PrintArray method.

Original array:
0.42 0.32 0.33 0.52 0.37 0.47 0.51 
Sorted array:
0.32 0.33 0.37 0.42 0.47 0.51 0.52 

The program demonstrates the step-by-step execution of the bucket sort algorithm on the given array and outputs the sorted array.

Bucket sort is efficient when the input elements are uniformly distributed over a range and the number of elements in each bucket is small. It is often used as a subroutine in radix sort algorithms or as a preprocessing step in other sorting algorithms.