Skip to main content

The first improvement to the bucket sort algorithm, which was initializing buckets only when they are needed makes the algorithm a lot faster. The second improvement, which was using LinkedList instead of List gives only a slight improvement in speed, but an improvment nonetheless. Finally remember that Bucket Sort works based on an array of buckets. Meaning that the bucket sort algorithm is fastest when the range of values being sorted is small (since the array of buckets will be small).

//====================================================
//| Downloaded From                                  |
//| Visual C# Kicks - http://www.vcskicks.com/       |
//| License - http://www.vcskicks.com/license.html   |
//====================================================

using System;
using System.Collections.Generic;
using System.Text;

namespace BucketSort
{
    class BucketSort
    {
        public static void Sort(int[] integers)
        {
            // Verify input
            if (integers == null || integers.Length <= 1)
            {
                return;
            }

            // Find the maximum and minimum values in the array
            int maxValue = integers[0]; // start with first element
            int minValue = integers[0];

            // Note: start from index 1
            for (int i = 1; i < integers.Length; i++)
            {
                if (integers[i] > maxValue)
                {
                    maxValue = integers[i];
                }

                if (integers[i] < minValue)
                {
                    minValue = integers[i];
                }
            }

            // Create a temporary "bucket" to store the values in order
            // each value will be stored in its corresponding index
            // scooting everything over to the left as much as possible (minValue)
            // e.g. 34 => index at 34 - minValue
            LinkedList<int>[] bucket = new LinkedList<int>[maxValue - minValue + 1];

            // Move items to bucket
            for (int i = 0; i < integers.Length; i++)
            {
                if (bucket[integers[i] - minValue] == null)
                {
                    bucket[integers[i] - minValue] = new LinkedList<int>();
                }

                bucket[integers[i] - minValue].AddLast(integers[i]);
            }

            // Move items in the bucket back to the original array in order
            int k = 0; // index for original array
            for (int i = 0; i < bucket.Length; i++)
            {
                if (bucket[i] != null)
                {
                    // start add head of linked list
                    LinkedListNode<int> node = bucket[i].First;

                    while (node != null)
                    {
                        integers[k] = node.Value; // get value of current linked node
                        node = node.Next; // move to next linked node
                        k++;
                    }
                }
            }
        }
    }
}