Skip to content

Instantly share code, notes, and snippets.

@KristupasSavickas
Created May 30, 2017 16:01
Show Gist options
  • Save KristupasSavickas/8dc31c932cec98fb875c5199dead70a1 to your computer and use it in GitHub Desktop.
Save KristupasSavickas/8dc31c932cec98fb875c5199dead70a1 to your computer and use it in GitHub Desktop.
Radix sort for a linked list in C#
static LinkedList<int> RadixSort(LinkedList<int> linkedList)
{
bool isFinished = false;
int digitPosition = 0;
var buckets = new List<Queue<int>>();
InitializeBuckets(buckets);
while (!isFinished)
{
isFinished = true;
foreach (int value in linkedList)
{
int bucketNumber = GetBucketNumber(value, digitPosition);
if (bucketNumber > 0)
{
isFinished = false;
}
buckets[bucketNumber].Enqueue(value);
}
var walk = linkedList.First;
foreach (var bucket in buckets)
{
while (bucket.Count > 0 && walk != null)
{
walk.Value = bucket.Dequeue();
walk = walk.Next;
}
}
digitPosition++;
}
return linkedList;
}
static int GetBucketNumber(int value, int digitPosition)
{
int bucketNumber = (value / (int)Math.Pow(10, digitPosition)) % 10;
return bucketNumber;
}
static void InitializeBuckets(List<Queue<int>> buckets)
{
for (int i = 0; i < 10; i++)
{
var q = new Queue<int>();
buckets.Add(q);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment