Created
May 30, 2017 16:01
-
-
Save KristupasSavickas/8dc31c932cec98fb875c5199dead70a1 to your computer and use it in GitHub Desktop.
Radix sort for a linked list in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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