Radix Sort(Taban Sıralama) Yapısı, Algoritması ve Çalışma Zamanı

• 

Algoritması:

        public static int maxgetir(int[] dizi, int n)
        {
            int max = dizi[0];
            for (int i = 1; i < n; i++)
                if (dizi[i] > max)
                    max = dizi[i];
            return max;
        }

        public static void countSort(int[] dizi, int n, int exp)
        {
            int[] cıktı = new int[n]; // çıkış dizisi 
            int i;
            int[] sayac = new int[10];

            //tüm elemanların 0 degeri ile olş.
            for (i = 0; i < 10; i++)
                sayac[i] = 0;

             //sayac ıcerısınden oluşturulan degerler depolanıyor. 
            for (i = 0; i < n; i++)
                sayac[(dizi[i] / exp) % 10]++;

            // sayac dizisini değiştirerek gerçek değerler almasını saglıyoruz. 
            //  bu basamakta konumu 
            for (i = 1; i < 10; i++)
                sayac[i] += sayac[i - 1];

            // çıktı dizisi oluşturuyoruz 
            for (i = n - 1; i >= 0; i--)
            {
                cıktı[sayac[(dizi[i] / exp) % 10] - 1] = dizi[i];
                sayac[(dizi[i] / exp) % 10]--;
            }

           
            for (i = 0; i < n; i++)
                dizi[i] = cıktı[i];
        }

         
        public static void radixsort(int[] dizi, int n)//n bizim dizimizin boyutu
        {
            //max elemanı bulma işlemi 
            int m = maxgetir(dizi, n);

            
            for (int i = 1; m / i > 0; i *= 10)
                countSort(dizi, n, i);
        }
        static void Main(string[] args)
        {
            int []A = { 45,98,1,543,75465,0, 12, 36, 5,48 };

            radixsort(A, A.Length);.77
            for (int i = 0; i < A.Length; i++)
            {
                Console.WriteLine(A[i]);
            }

            Console.WriteLine("-----------------------------------------------------");


           
            Console.ReadLine();

        }

Çalışma Zamanı: En kötü ve ortalama durum:O(k/d*n)

En iyi durum mevcut değildir.

Kaynakça:

Erkan Tanyıldızı Algortima Analizi Ders Notları

http://sorting.at/