LSDRadixSorter.cs

usingSystem;
usingSystem.Collections.Generic;

namespaceAlgorithms.Sorting
{
/// <summary>
/// LSD (Least Significat Digit) Radix Sort.
///
/// Sorts ASCII-encoded strings.
/// Implemented as a static class of extension methods.
/// </summary>
publicstaticclassLSDRadixSorter
{
/// <summary>
/// Extension method for sorting strings.
/// </summary>
publicstaticstringLSDRadixSort(thisstringsource)
{
if(string.IsNullOrEmpty(source)||source.Length<=1)
returnsource;

// LSD Radix Sort the character arrapy representation of the string
varcharArray=source.ToCharArray();
charArray.LSDRadixSort();

returnnewString(charArray);
}


/// <summary>
/// Extension method for sorting character arrays, in place.
/// </summary>
publicstaticvoidLSDRadixSort(thischar[]source)
{
if(source==null||source.Length<=1)
return;

// extend ASCII alphabet size
intasciiSize=256;

intlength=source.Length;
char[]auxiliary=newchar[length];

// compute frequency counts
int[]count=newint[asciiSize+1];

for(inti=0;i<length;i++)
count[source[i]+1]++;

// compute cumulates
for(intr=0;r<asciiSize;r++)
count[r+1]+=count[r];

// move data
for(inti=0;i<length;i++)
auxiliary[count[source[i]]++]=source[i];

// copy back
for(inti=0;i<length;i++)
source[i]=auxiliary[i];
}


/// <summary>
/// Extension method for sorting collections of strings of the same width, in place.
/// </summary>
publicstaticvoidLSDRadixSort(thisIList<String>collection,intstringFixedWidth)
{
// Validate input
if(collection==null||collection.Count<=1)
return;
for(inti=0;i<collection.Count;++i)
if(collection[i]==null||collection[i].Length!=stringFixedWidth)
thrownewInvalidOperationException("Not all strings have the same width");

// extend ASCII alphabet size
intasciiSize=256;

intstringsCount=collection.Count;
string[]auxiliary=newstring[stringsCount];

for(intd=stringFixedWidth-1;d>=0;d--)
{
// compute frequency counts
int[]count=newint[asciiSize+1];

for(inti=0;i<stringsCount;i++)
count[collection[i][d]+1]++;

// compute cumulates
for(intr=0;r<asciiSize;r++)
count[r+1]+=count[r];

// move data
for(inti=0;i<stringsCount;i++)
auxiliary[count[collection[i][d]]++]=collection[i];

// copy back
for(inti=0;i<stringsCount;i++)
collection[i]=auxiliary[i];
}
}
}
}