Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
72 lines (62 sloc) 2.27 KB
using SortExtravaganza.Common;
using System;
using System.Linq;
namespace RadixSort
{
class RadixSort
{
public static void Main()
{
int[] array = { 330, 8, 27, 4419, 55, 816, 419, 77, 622, 1234, 6, 9, 241, 1, 35, 7733, 4, 69 };
int length = array.Length;
Console.WriteLine("Radix Sort");
CommonFunctions.PrintInitial(array);
int max = array.Max();
for (int exp = 1; max / exp > 0; exp *= 10)
{
CountingSort(array, length, exp);
}
CommonFunctions.PrintFinal(array);
Console.ReadLine();
}
//This is a modified version of Counting Sort from an earlier post
//We need to do Counting Sort against each group of integers,
//where the groups are made based on the position of significant digits.
//So, we use Counting Sort on the least-significant digit, then the next-least, etc.
//After that, we concatenate the groups together to form the final array.
public static void CountingSort(int[] array, int length, int exponent)
{
//Create a new "output" array
int[] output = new int[length]; // output array
int i;
//Create a new "counting" array which stores the count of each unique number
int[] count = new int[10];
for (i = 0; i < 10; i++)
{
count[i] = 0;
}
for (i = 0; i < length; i++)
{
count[(array[i] / exponent) % 10]++;
}
//Change count[i] so that count[i] now contains actual position of
//this character in the output array.
for (i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
//Build the output array.
//This is the tricky part.
for (i = length - 1; i >= 0; i--)
{
output[count[(array[i] / exponent) % 10] - 1] = array[i];
count[(array[i] / exponent) % 10]--;
}
//Copy the output array to the final array.
for (i = 0; i < length; i++)
{
array[i] = output[i];
}
}
}
}
You can’t perform that action at this time.