Fast Bucket Sort

vckicks 0 Tallied Votes 263 Views Share

A slightly modified version of Bucket Sort that uses LinkedLists and initializes buckets only when required. Results in massive speed improvements.

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)
        {
            LinkedListNode<int> node = bucket[i].First; //start add head of linked list

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