Bucket sort in C#

Bucket sort - overview

Bucket sort is a good example of a distribution sort algorithm. It is closely related to Radix sort and counting sort.

Description of the bucket sort algorithm

Bucket sort is a sorting algorithm that distributes all values in an array into a number of so called buckets. Then each bucket is sorted by a different algorithm or by applying the same algorithm recursively. Finally the separate buckets are concatenated to get the final sorted array.

The algorithm works like this:

1. Initialize a list of empty buckets.
2. Loop through the input array and put each object in a corresponding bucket. This step is called "scattering".
3. Sort all buckets
4. Go through the sorted buckets in order and put the elements back into the original array. This step is called "gathering".

Computational complexity

Bucket sort has has a worst case performance of O(n²). In average it runs in O(n + k) time.

Example of an implementation of bucket sort in C#

    private void SortArrayWithBucketSort()
    {
        double[] array = { 0.37, 0.25, 0.86, 0.23, 0.09, 0.21, 0.17, 0.71 };
        double[] sortedArray = BucketSort(array);

        // PrintResult(sortedArray);
    }

    public double[] BucketSort(double[] array)
    {
        List<List<double>> buckets = new List<List<double>>();
        InitializeBuckets(buckets);

        Scatter(array, buckets);

        int i = 0;
        foreach (List<double> bucket in buckets)
        {
            double[] arr = bucket.ToArray();
            InsertionSort(arr);

            foreach (double d in arr)
            {
                array[i++] = d;
            }
        }

        return array;
    }

    private void Scatter(double[] array, List<List<double>> buckets)
    {
        foreach (double value in array)
        {
            int bucketNumber = GetBucketNumber(value);
            buckets[bucketNumber].Add(value);
        }
    }

    private void InsertionSort(double[] array)
    {
        int j;
        double temp;

        for (int i = 1; i < array.Length; i++)
        {
            j = i;
            while (j > 0 && array[j] < array[j - 1])
            {
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                j--;
            }
        }
    }

    private int GetBucketNumber(double value)
    {
        double val = value * 10;
        int bucketNumber = (int)Math.Floor(val);
        return bucketNumber;
    }

    private static void InitializeBuckets(List<List<double>> buckets)
    {
        for (int i = 0; i < 10; i++)
        {
            List<double> a  = new List<double>();
            buckets.Add(a);
        }
    }