Skip to content

Instantly share code, notes, and snippets.

@gogsbread
Created January 2, 2013 23:08
Show Gist options
  • Save gogsbread/4439205 to your computer and use it in GitHub Desktop.
Save gogsbread/4439205 to your computer and use it in GitHub Desktop.
Rudimentary implementation of RadixSort. Academic and reference purpose
namespace dotNetPlayGround
{
using System;
using System.Collections.Generic;
using System.Linq;
/// <summary>
/// TODO: Update summary.
/// </summary>
public class RadixSort
{
static void Main()
{
//int[] unsorted = { 32, 1, 56, 1892, 0, 345 };
int[] A = new int[20];
for (int i = 0; i < 20; i++)
A[i] = i + 1;
int[] B = new int[20];
for (int i = 0; i < 20; i++)
B[i] = 20 - i;
int[] unsorted = new int[20];
for (int i = 0; i < 20; i++)
unsorted[i] = A[i] * B[i];
int[] sorted = RSort(unsorted);
foreach (int i in sorted)
Console.WriteLine(i);
}
static int[] RSort(int[] unsorted)
{
//determine the maxlength of key
// for each keylength
//initialize qu array for 10
// insert into q array for all unsorted
// pour the queue back to array.
int maxKeyLength = unsorted.Max().ToString().Length;
Queue<int>[] buckets = new Queue<int>[10];
for (int i = 0; i < buckets.Length; i++)
{
buckets[i] = new Queue<int>(unsorted.Length);
}
int place = 1;
for (int i = 0; i < maxKeyLength; i++)
{
for (int j = 0; j < unsorted.Length; j++)
{
int item = unsorted[j];
int key = Key(item,place);
if(buckets[key].Count > 0){
buckets[key].Enqueue(item);
}
else
buckets[key] = new Queue<int>(new List<int>(){item});
}
unsorted = PourQueue(buckets,unsorted.Length);
place *= 10;
}
return unsorted;
}
static int[] PourQueue(Queue<int>[] buckets,int length)
{
List<int> pour = new List<int>(length);
for (int i = 0; i < 10; i++)
{
if (buckets[i] != null)
{
Queue<int> bucket = buckets[i];
while (bucket.Count > 0)
{
pour.Add(bucket.Dequeue());
}
}
}
return pour.ToArray();
}
static int Key(int element, int keyUnit)
{
return (element / keyUnit) % 10;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment