RADİX SORT

RADİX SORT

Bilgisayar biliminde çok önemli bir yere sahiptir Radix Sort algoritması çünkü bilgisayar bilimi ikilik tabanda işlem yapmaktadır yani (0 ve 1) ile

Bunun için küçükten büyüğe doğru ya da büyükten küçüğe doğru sıraladığımızda durun karmaşası olarak  O(n) sahiptir  aşağıdaki java kodunda görmekteyiz karmaşıklığı bir tane döngü var ayrı ayrı ve karmaşıklığı O(n) olmaktadır

Çalışma mantığı gayet basittir en anlamsız yani LSB bitine göre sıralama yapıyor önce LSB  0 bir yere sonra 1 bir yerde barındırıyor daha sonra ise ikinci ağırlıklı :LSB bitinde bunun tekrarını yapıyor bu işlem taki MSB bitine doğru gittiğinde işlem bitmiş oluyor böyle yaptığında zaten sıralama bitmiş oluyor böylelikle küçükten büyüğe doğru sıralama yapmaktayız

Önce bunu 10 tabanınıda göstermek istiyorum;

57, 43, 24, 213, 44, 102, 70, 37, 111, 23 sayılarını verelim  Radix Sort algoritması ile sıralayalım

·         İlk geçişte sayılar birler basamağına göre artan yönde sıralanır. Birler hanesinde aynı değeri alan 43, 213, 23 gibi sayılar, başlangıç dizisindeki veriliş sırasıyla yazılırlar.

70, 111, 102, 43, 213, 23, 24, 44, 57, 37

·         İkinci geçişte, ilk geçişte elde edilen dizi onlar basamağındaki değerlerine göre sıralanır.    

102, 111, 213, 23, 24, 37, 43, 44, 57, 70

·         Üçüncü geçişte, ikinci geçişte elde edilen dizi yüzler basamağındaki değerlerine göre sıralanır.

 23, 24, 37, 43, 44, 57, 70, 102, 111, 213 

Aynı mantığı diğer tabanlar içinde yapabiliriz işlem sırası ve işlemleri aynıdır. Şimdi ise Java kodlarını yazalım:

public static int[] sort(int[] old) {
    for (int shift = Integer.SIZE - 1; shift > -1; shift--) {
        int[] tmp = new int[old.length];
        int j = 0;

        for (int i = 0; i < old.length; i++) {
            boolean move = old[i] << shift >= 0;

            if (shift == 0 ? !move : move) {
                tmp[j] = old[i];
                j++;
            } else {

                old[i - j] = old[i];
            }
        }
        for (int i = j; i < tmp.length; i++) {
            tmp[i] = old[i - j];
        }
        old = tmp;
    }

    return old;
}