Radix Sorter Algorithm
Radix sort can be apply to data that can be sorted lexicographically, be they integers, words, punch cards, playing cards, or the mail. It avoids comparison by make and distribute components into buckets according to their radix. radix sorting algorithms get into common purpose as a manner to sort punched cards as early as 1923.
The first memory-efficient computer algorithm was developed in 1954 at MIT by Harold H. Seward. The linear scan is closely associated to Seward's other algorithm — counting sort. computerize radix kinds had previously been dismissed as impractical because of the perceived need for variable allocation of buckets of unknown size.
namespace Algorithms.Sorters.Integer
{
/// <summary>
/// Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual
/// digits which share the same significant position and value. A positional notation is required, but because integers can represent
/// strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers.
/// </summary>
public class RadixSorter : IIntegerSorter
{
/// <summary>
/// Sorts array in ascending order.
/// </summary>
/// <param name="array">Array to sort.</param>
public void Sort(int[] array)
{
var bits = 4;
var b = new int[array.Length];
var rshift = 0;
for (var mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits)
{
var cntarray = new int[1 << bits];
foreach (var t in array)
{
var key = (t & mask) >> rshift;
++cntarray[key];
}
for (var i = 1; i < cntarray.Length; ++i)
{
cntarray[i] += cntarray[i - 1];
}
for (var p = array.Length - 1; p >= 0; --p)
{
var key = (array[p] & mask) >> rshift;
--cntarray[key];
b[cntarray[key]] = array[p];
}
var temp = b;
b = array;
array = temp;
}
}
}
}
