Write a program to demonstrate Radix sort
In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix.
Wikipedia
Solution:
using System;
using System.Linq;
namespace bucketsort
{
class Program
{
private static int inputDigit = 5;
public static void Main()
{
int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
var max = arr.Max();
for (var i = 1; max / i > 0; i *= inputDigit)
RadixSort(arr, i);
foreach (var t in arr)
Console.WriteLine(t);
Console.ReadLine();
}
public static void RadixSort(int[] arr, int exp)
{
var output = new int[arr.Length];
var count = new int[inputDigit];
for (var i = 0; i < inputDigit; i++)
count[i] = 0;
for (var i = 0; i < arr.Length; i++)
count[arr[i] / exp % inputDigit]++;
for (var i = 1; i < inputDigit; i++)
count[i] += count[i - 1];
for (var i = arr.Length - 1; i >= 0; i--)
{
output[count[arr[i] / exp % inputDigit] - 1] = arr[i];
count[arr[i] / exp % inputDigit]--;
}
for (var i = 0; i < arr.Length; i++)
arr[i] = output[i];
}
}
}