C# Bucket Sorting

Bucket sorting in C# is an important sorting algorithm that can be used for faster, more powerful algorithms.

Bucket sort is a good sorting algorithm because it runs in linear time, for those familiar with Big-Oh notation, it runs O(n). Why is this good? Because any comparison-based sorting algorithm (which are most common) can run no faster than O(n log n).

Since bucket sort is not comparison-based, it is limited in the types of data it can sort. Basically it works on data that has some sort of numeric value attached to it. For argument sake, let’s sort integers which are themselves numeric values.

The overall algorithm is to create a “bucket” that will hold each value. Each value will simply be inserted into its appropriate index in the bucket. When the bucket is emptied, the values will come out in order.

So first thing you need is to find the maximum value from the elements to sort and make that the size of the bucket. Since this is simply scanning through the elements it runs in O(n) time.

Then you want to create a bucket. The bucket cannot simply be an array of integers, because then you couldn’t add duplicate elements into the same cell. Therefore the bucket has to be an array of lists. The lists can be anything you want (ArrayList, LinkedList, etc.). If necessary, initialize each list. This step runs in constant time.

Next, insert all the unsorted elements into the bucket, once again running in O(n).

Finally, empty out the bucket in order, ignoring empty cells. Which will once again run in O(n). Since none of the steps exceeded O(n) running time, the total running time of the algorithm is also O(n).

Facebook Comments

Show More

Leave a Reply

Back to top button