A slightly modified version of Bucket Sort that uses LinkedLists and initializes buckets only when required. Results in massive speed improvements.
Fast Bucket Sort
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++;
}
}
}
}
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.