Radix Sort

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];
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *