Bucket Sorting with C-Sharp Example

Back to: Data Structure Tutorial

Bucket sort is a sorting algorithm that works by partitioning an array into a number of buckets, each of which is then sorted individually. The sorted buckets are then combined to give the final sorted array. Here’s an example implementation of bucket sort in C#:

public static void BucketSort(int[] arr, int numBuckets)
{
    // Create an array of buckets
    List<int>[] buckets = new List<int>[numBuckets];
    for (int i = 0; i < numBuckets; i++)
    {
        buckets[i] = new List<int>();
    }

    // Assign each element to a bucket
    for (int i = 0; i < arr.Length; i++)
    {
        int bucketIndex = (int)((float)arr[i] / arr.Length * numBuckets);
        buckets[bucketIndex].Add(arr[i]);
    }

    // Sort each bucket and combine into a final sorted array
    int index = 0;
    for (int i = 0; i < numBuckets; i++)
    {
        buckets[i].Sort();
        for (int j = 0; j < buckets[i].Count; j++)
        {
            arr[index++] = buckets[i][j];
        }
    }
}

In this implementation, we first create an array of buckets, each of which is a list. We then assign each element in the input array to a bucket based on its value, using the formula (int)((float)arr[i] / arr.Length * numBuckets) to map the value to a bucket index. We then sort each bucket individually using the List.Sort method, and combine the sorted buckets into the final sorted array.

The time complexity of bucket sort depends on the number of buckets used and the algorithm used to sort the individual buckets. In this implementation, we use a simple insertion sort to sort each bucket, which has a time complexity of O(n^2) in the worst case. However, if we use a more efficient sorting algorithm like quicksort or mergesort to sort the buckets, the overall time complexity of bucket sort can be reduced to O(n log n).