C# Bucket Sort

last modified March 9, 2025

This tutorial dives into the bucket sort algorithm in C#. We’ll explore sorting numbers and text in ascending and descending order, and compare it with Quick Sort using benchmarks.

An algorithm is a structured set of steps to solve a problem or complete a task. It’s a cornerstone of programming and computer science.

Sorting organizes data into a specific sequence, like ascending or descending. It’s vital for efficient data handling and analysis in programs.

Common Sorting Algorithms

Here are some popular sorting algorithms:

• Bubble Sort

• Selection Sort

• Insertion Sort

• Merge Sort

• Quick Sort

• Bucket Sort

Bucket Sort Algorithm

Bucket sort is a distribution-based sorting method. It divides elements into “buckets,” sorts each bucket individually, and then combines them.

It shines when data is evenly spread across a range. Unlike comparison-based sorts, it relies on distributing data, making it fast for uniform distributions but less effective otherwise.

Bucket Sort Example: Numeric Data

Here’s a C# implementation of bucket sort for numbers in ascending order using top-level statements.

BucketSortNumeric.cs

// BucketSortNumeric.cs double[] BucketSort(double[] arr) { if (arr.Length == 0) return arr;

double maxVal = arr.Max();
double bucketSize = maxVal / arr.Length;
List<double>[] buckets = new List<double>[arr.Length];

for (int i = 0; i < buckets.Length; i++)
    buckets[i] = [];

foreach (double num in arr)
{
    int idx = (int)(num / bucketSize);
    if (idx >= arr.Length) idx = arr.Length - 1;
    buckets[idx].Add(num);
}

foreach (var bucket in buckets)
    bucket.Sort();

return buckets.SelectMany(bucket => bucket).ToArray();

}

double[] arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]; double[] sorted = BucketSort(arr); Console.WriteLine(“Sorted array: " + string.Join(” “, sorted));

This sorts an array of doubles using bucket sort. It uses List.Sort to sort each bucket.

Bucket Sort Example: Textual Data

Here’s an example sorting strings by length in descending order using bucket sort.

BucketSortTextual.cs

// BucketSortTextual.cs string[] BucketSortTextual(string[] arr) { if (arr.Length == 0) return arr;

int maxLen = arr.Max(s => s.Length);
List<string>[] buckets = new List<string>[maxLen + 1];

for (int i = 0; i < buckets.Length; i++)
    buckets[i] = [];

foreach (string s in arr)
    buckets[s.Length].Add(s);

foreach (var bucket in buckets)
    bucket.Sort((a, b) => b.CompareTo(a));

List<string> result = [];
for (int i = buckets.Length - 1; i >= 0; i--)
    result.AddRange(buckets[i]);

return result.ToArray();

}

string[] arr = [“apple”, “banana”, “kiwi”, “mango”, “pear”]; string[] sorted = BucketSortTextual(arr); Console.WriteLine(“Sorted array: " + string.Join(” “, sorted));

This sorts strings by length in descending order, with alphabetical reverse order within each bucket using a custom comparison.

Comparing Bucket Sort with Quick Sort

Bucket sort excels with uniformly distributed data, running in O(n + k) time where k is the number of buckets. Quick Sort, averaging O(n log n), is more versatile for general cases.

Benchmark Example

This compares bucket sort and Quick Sort performance on a large dataset.

Benchmark.cs

// Benchmark.cs using System.Diagnostics;

double[] BucketSort(double[] arr) { if (arr.Length == 0) return arr;

double maxVal = arr.Max();
double bucketSize = maxVal / arr.Length;
List<double>[] buckets = new List<double>[arr.Length];

for (int i = 0; i < buckets.Length; i++)
    buckets[i] = [];

foreach (double num in arr)
{
    int idx = (int)(num / bucketSize);
    if (idx >= arr.Length) idx = arr.Length - 1;
    buckets[idx].Add(num);
}

foreach (var bucket in buckets)
    bucket.Sort();

return buckets.SelectMany(bucket => bucket).ToArray();

}

double[] QuickSort(double[] arr) { if (arr.Length <= 1) return arr;

double pivot = arr[arr.Length / 2];
var left = new List<double>();
var middle = new List<double>();
var right = new List<double>();

foreach (double x in arr)
{
    if (x < pivot) left.Add(x);
    else if (x == pivot) middle.Add(x);
    else right.Add(x);
}

return [.. QuickSort(left.ToArray()), .. middle, .. QuickSort(right.ToArray())];

}

Random rand = new(Random.Shared.Next()); double[] arr = new double[10000]; for (int i = 0; i < arr.Length; i++) arr[i] = rand.NextDouble() * 1000;

double[] bucketData = arr.ToArray(); Stopwatch sw = Stopwatch.StartNew(); BucketSort(bucketData); double bucketTime = sw.Elapsed.TotalSeconds;

double[] quickData = arr.ToArray(); sw = Stopwatch.StartNew(); QuickSort(quickData); double quickTime = sw.Elapsed.TotalSeconds;

Console.WriteLine($“Bucket Sort Time: {bucketTime:F6} seconds”); Console.WriteLine($“Quick Sort Time: {quickTime:F6} seconds”);

This benchmarks both algorithms on 10,000 random doubles. Bucket sort may edge out on uniform data, but Quick Sort is more consistent overall.

Source

C# Array.Sort documentation

We’ve covered bucket sort in C# and compared it with Quick Sort. It’s great for uniform data, while Quick Sort is a robust all-purpose choice.

Author

My name is Jan Bodnar, and I am a passionate programmer with extensive programming experience. I have been writing programming articles since 2007. To date, I have authored over 1,400 articles and 8 e-books. I possess more than ten years of experience in teaching programming.

List all C# tutorials.