8. Taban Sıralama (Radix Sort)

1. RADIX SORT  

Sırasız verilen dizileri küçükten büyüğe sıralamanın bir yolu da radix sort yani taban sıralamasını kullanmaktır. Gerçek hayatta pek de kullanımı olmamakla beraber algoritma yeteneğinizi geliştirebilmek ve diğer algoritmalarla kıyas yapabilmek adına bu yazımda radix sort’tan bahsedicem.

  Radix sort yani taban sıralaması isminden de anlaşılacağı üzere sayıları digitlerine yani basamaklarına göre sıralar. İlk geçişte sadece 1’ler basamağına bakarak bir sıralama yapar, ikinci geçişte 10’lar basamağına bakarak sıralama yapar, 3. geçişte 100ler… bu şekilde gider. Aşağıda radix sort’un çalışması bir örnek üzerinden step step açıklanmıştır.

                        170 , 45 , 75 , 90, 2, 24, 802 , 66  şeklinde sırasız bir dizimiz olsun.

          –  ilk geçişte sadece ve sadece 1’ler basamağına göre sıralama yapılacaktır. 1’ler basamağı eşit olan sayılarda var olan sıra korunacaktır. Aşağıda 2,802 ve 45,75 dizilimi sırasını dizinin orjinalinden almış olup buna örnek teşkil eder.

                           170 , 90 , 2 , 802 , 24 , 45 , 75 , 66

           –  İkinci geçişte sadece ve sadece 10’lar basamağına göre sıralama yapılacak olup 1’ler basamağını göz önünde bulundurma hakkımız yoktur.

                          02 , 802 , 24 , 45 , 66 , 170 , 75 , 90

          –  Üçüncü geçişte sadece 100’ler basamağına bakılır ki bu da dizimizdeki elemanların maksimum digiti olduğundan son bakış olacaktır.

                         002, 024 , 045 , 066 , 075 , 090 , 170 , 802

Buraya kadarki kısım Radix sort’un çalışma mantığıydı. Ancak değinilmesi gereken bir nokta var , radix sort’un yaptığı iş sıralamaktan ziyade , her seferinde hangi digiti baz alarak sıralama yapmamız gerektiğini bize söylemek. İş sıralama aksiyonuna geldiğinde ise başka bir sıralama algoritması kullanmamız gerekir ki bu genelde bucket sort ya da counting sort‘tur. Bucket sort genelde dinamik veri yapıları kullanıldığı zaman kullanılır. Yaptığı iş her bir digit değerlendirmesi için liste oluşturmaktır. Örneğin 3 ile bitenler için L3 linked list’i , 4 ile bitenler için L4 linked list’i ve her listi kendi arasında sıralamak gibi. Daha çok kullanılanı ise counting sort’tur.

2. RADIX SORT’UN C# ile IMPLEMENTASYONU

public static double getMax(List<double> arr, int n)
 {
    double mx = arr[0];
    for (int i = 1; i < n; i++)
    if (arr[i] > mx)
    mx = arr[i];
    return mx;
 }

public static void countSort(List<double> arr, int n, double exp)
 {
       List<double> output = new List<double>();
       int i;
       List<int> count = new List<int>();

       for (int m = 0; m < count.Count; m++)
       {
        count[m] = 0;
       }

       for (i = 1; i < n; i++)
       count[Convert.ToInt32(Math.Ceiling((arr[i] / exp) % 10))]++;

       for(i = 1; i < 10; i++)
       count[i] += count[i - 1];


       for (i = n - 1; i >= 0; i--)
       {
        output[count[Convert.ToInt32((arr[i] / exp) % 10)] - 1] = arr[i];
        count[Convert.ToInt32((arr[i] / exp) % 10)]--;
       }
 
       for(i = 0; i < n; i++)
       arr[i] = output[i];
  }

   public static void radixsort(List<double> arr, int n)
   {
       double m = getMax(arr, n);

       for(int exp = 1; m / exp > 0; exp *= 10)
       countSort(arr, n+1, exp);
   }