RadixSort.cs

using System;
using System.Collections.Generic;


namespace random
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = { 23, 2, 5, 101, 50, 55 };
            Console.WriteLine("Преди сортиране:");
            Console.WriteLine(string.Join(", ", input));
            RadixSort(input);
            Console.WriteLine("След сортиране:");
            Console.WriteLine(string.Join(", ", input));
        }
        // Примерен вход масив { 23, 2, 5, 101, 50, 55 }
        // Примерен изход (същия) масив { 2 , 5, 23, 50, 55, 101 }
        /*
         * Обяснение:
         *   Radix сортирането, като counting и bucket сортирането,
         *   е алгоритъм за сортиране на цели числа. На теория
         *   radix сортирането е най-бързото, то се различава с това че,
         *   създава кофи за всяка цифра на дадено число от масив,
         *   с което наподобява на bucket алгоритъма.
         *   Всяка кофа трябва да е нарастващ лист,
         *   който може да поставя дадено число на различни индекси.
         *   
         *  Времетраене:
         *    Случай: Най-добър | Среден | Най-лош
         *             O(k * n)  O(k * n)  O(k * n)
         *    Където k е дължината на най-голямото число,
         *    а n е големината на масива
         *   
         */
        private static void RadixSort(IList<int> array)
        {
            // 10 кофи за всяка цифра от 0 до 9
            const int radix = 10;

            // Създаване на лист съдържащ 10 кофи
            // изглежда така List {кофа 0, кофа 1...кофа 9}
            // като всяка кофа може да съдържа в себе си N брой числа
            List<int>[] bucket = new List<int>[radix];
            for (int i = 0; i < bucket.Length; i++)
            {
                bucket[i] = new List<int>();
            }

            bool maxLength = false;
            int placement = 1;

            while (!maxLength)
            {
                maxLength = true;
                // Сортиране
                foreach (int number in array)
                {
                    // Слага текущото число number
                    // в кофа с позиция temp % radix
                    // пример: 23 % 10(radix) = 3
                    // 23 отива в кофа с номер(индекс) 3 от листа с кофите
                    int temp = number / placement;
                    bucket[temp % radix].Add(number);

                    if (maxLength && temp > 0)
                    {
                        maxLength = false;
                    }
                }
                // Слага съдържанието на листовете в array
                // и изчиства листовете
                int a = 0;
                for (int b = 0; b < radix; b++)
                {
                    foreach (var i in bucket[b])
                    {
                        // Елемент на позиция а от array приема
                        // съдържанието на кофа с индекс b
                        // като на всеки цикъл а се увеличава с 1
                        array[a++] = i;
                    }
                    // Чистене
                    bucket[b].Clear();
                }
                // placement = placement * 10(radix)
                placement *= radix;
            }
        }
    }
}