Sorting is one of the most common tasks in programming, and Bucket Sort offers a unique approach compared to traditional algorithms like Bubble Sort or Quick Sort. Bucket Sort works by dividing the data into several “buckets”, sorting each bucket individually, and then combining the results to produce a sorted array. This approach is particularly effective when the input values are uniformly distributed, as it reduces the number of comparisons required.
with hands-on learning.
get the skills and confidence to land your next move.
Bucket Sort is widely used in scenarios such as data preprocessing, graphics rendering, and large-scale simulations, where efficiency matters. By implementing Bucket Sort in C#, beginners can learn about arrays, lists, and the concept of distributing data to simplify sorting, which provides a deeper understanding of sorting beyond simple comparison-based methods.
Program 1: Basic Bucket Sort Using Arrays
This program demonstrates a simple Bucket Sort for numbers between 0 and 1 using arrays. It divides numbers into buckets, sorts them, and merges the results.
using System;
using System.Collections.Generic;
class Program
{
static void BucketSort(float[] arr)
{
int n = arr.Length;
List<float>[] buckets = new List<float>[n];
for (int i = 0; i < n; i++)
buckets[i] = new List<float>();
for (int i = 0; i < n; i++)
{
int index = (int)(n * arr[i]);
buckets[index].Add(arr[i]);
}
for (int i = 0; i < n; i++)
buckets[i].Sort();
int k = 0;
for (int i = 0; i < n; i++)
foreach (float num in buckets[i])
arr[k++] = num;
}
static void Main()
{
float[] arr = { 0.78f, 0.17f, 0.39f, 0.26f, 0.72f, 0.94f, 0.21f, 0.12f, 0.23f, 0.68f };
BucketSort(arr);
Console.WriteLine("Sorted array:");
foreach (float num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}In this program, numbers are placed into buckets based on their value range. Each bucket is sorted using the built-in Sort() function, and the sorted buckets are merged. Beginners can see how dividing and conquering the array simplifies the sorting process.
Program 2: Bucket Sort With Integers
This version shows how to sort integer arrays by mapping numbers into buckets proportionally and using list sorting for each bucket.
using System;
using System.Collections.Generic;
class Program
{
static void BucketSort(int[] arr)
{
int n = arr.Length;
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max) max = arr[i];
List<int>[] buckets = new List<int>[n];
for (int i = 0; i < n; i++)
buckets[i] = new List<int>();
for (int i = 0; i < n; i++)
{
int index = (arr[i] * n) / (max + 1);
buckets[index].Add(arr[i]);
}
for (int i = 0; i < n; i++)
buckets[i].Sort();
int k = 0;
for (int i = 0; i < n; i++)
foreach (int num in buckets[i])
arr[k++] = num;
}
static void Main()
{
int[] arr = { 42, 32, 33, 52, 37, 47, 51 };
BucketSort(arr);
Console.WriteLine("Sorted integer array:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}Here, the algorithm scales integer values to appropriate bucket indices. This example helps beginners understand how Bucket Sort can adapt to different numeric types and why choosing the correct bucket size is important.
Program 3: Bucket Sort With Negative and Positive Numbers
Bucket Sort is extended to handle arrays containing both negative and positive numbers. We use separate buckets for negatives and positives.
using System;
using System.Collections.Generic;
class Program
{
static void BucketSort(int[] arr)
{
List<int> neg = new List<int>();
List<int> pos = new List<int>();
foreach (int num in arr)
if (num < 0) neg.Add(-num);
else pos.Add(num);
SortList(neg);
SortList(pos);
neg.Reverse();
int index = 0;
foreach (int num in neg) arr[index++] = -num;
foreach (int num in pos) arr[index++] = num;
}
static void SortList(List<int> list)
{
if (list.Count == 0) return;
int max = list[0];
foreach (int num in list)
if (num > max) max = num;
List<int>[] buckets = new List<int>[list.Count];
for (int i = 0; i < list.Count; i++) buckets[i] = new List<int>();
for (int i = 0; i < list.Count; i++)
{
int index = (list[i] * list.Count) / (max + 1);
buckets[index].Add(list[i]);
}
list.Clear();
for (int i = 0; i < buckets.Length; i++)
{
buckets[i].Sort();
list.AddRange(buckets[i]);
}
}
static void Main()
{
int[] arr = { -42, 32, -33, 52, -37, 47, 51 };
BucketSort(arr);
Console.WriteLine("Sorted array with negative numbers:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}This program demonstrates how splitting positive and negative numbers makes Bucket Sort versatile. Beginners can see that with small changes, the same algorithm can handle more complex input arrays.
Program 4: Bucket Sort Using Floating Numbers With Different Ranges
This program demonstrates sorting floating-point numbers that are not limited to 0–1, requiring dynamic bucket allocation based on the minimum and maximum values.
using System;
using System.Collections.Generic;
class Program
{
static void BucketSort(float[] arr)
{
int n = arr.Length;
float min = arr[0], max = arr[0];
foreach (float num in arr)
{
if (num < min) min = num;
if (num > max) max = num;
}
List<float>[] buckets = new List<float>[n];
for (int i = 0; i < n; i++) buckets[i] = new List<float>();
for (int i = 0; i < n; i++)
{
int index = (int)(((arr[i] - min) / (max - min + 1)) * n);
buckets[index].Add(arr[i]);
}
int k = 0;
for (int i = 0; i < n; i++)
{
buckets[i].Sort();
foreach (float num in buckets[i])
arr[k++] = num;
}
}
static void Main()
{
float[] arr = { 42.5f, 32.1f, 33.3f, 52.7f, 37.2f, 47.6f, 51.8f };
BucketSort(arr);
Console.WriteLine("Sorted floating-point array:");
foreach (float num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}By dynamically calculating bucket indices based on the data range, this variation makes Bucket Sort practical for real-world datasets, showing beginners the flexibility of the algorithm.
Frequently Asked Questions (FAQ)
Q1: What is Bucket Sort?
Bucket Sort is a distribution-based sorting algorithm that divides data into multiple buckets, sorts each bucket, and merges the results.
Q2: Can Bucket Sort handle negative numbers?
Yes, by separating negatives and positives and sorting them independently, Bucket Sort can manage arrays containing both.
Q3: Is Bucket Sort faster than Quick Sort?
Bucket Sort can be faster for uniformly distributed data because it reduces the number of comparisons, but it requires extra space for buckets.
Q4: Can Bucket Sort sort floating numbers?
Yes, by mapping the values proportionally to bucket indices, Bucket Sort can handle floating-point numbers in any range.
Q5: Is Bucket Sort stable?
Yes, if the sorting of individual buckets is stable, Bucket Sort preserves the relative order of equal elements.
Conclusion
Bucket Sort is a powerful and flexible sorting algorithm that works well for both integers and floating-point numbers. By distributing data into buckets and sorting them individually, it reduces the work needed for large datasets. Beginners can benefit from experimenting with different types of data, negative numbers, and floating-point ranges, which helps deepen understanding of arrays, lists, and sorting strategies. Practicing Bucket Sort in C# is a great way to strengthen programming skills and gain confidence with advanced sorting concepts.
