Taban Sıralaması (Radix Sort)

Yazan : Şadi Evren ŞEKER

Hane sıralaması, radiks sıralaması veya kök sıralaması isimleri de verilebilen sıralama algoritmasına göre sıralanacak olan değerler hanelerine (digits) göre sıralanır. En değersiz haneden (Least significant digit) en değerli haneye (most significant digit) doğru sıralama işlemi yapılır. Yani örneğin en fazla 4 haneli sayıların bulunduğu bir sayı kümesinde en değersiz hane 1’ler hanesi en değerli hane ise binler (1000) hanesidir.

Taban sıralama algoritmasının en basit hali (iyileştirilmiş (optimized) halleri ileride anlatılacaktır) aşağıdaki örnekte gösterilmektedir:

  1. Sıralanmamış sayılarımız:170, 45, 75, 90, 2, 24, 802, 66
  2. İlk haneye göre (1’ler hanesi) sıralanmış hali:170, 90, 2, 802, 24, 45, 75, 66Yukarıdaki sıralama ile ilgili önemli bir nokta aynı 1’ler değerine sahip olan sayıların ilk listedeki sıralarına göre kalmış olmalarıdır. Yani 1. adımdaki listede 802, 2’den önce geliyor olsaydı 2. adımda da bu sıralama korunacaktı.
  3. Sıradaki hane olan 10’lar hanesine göre sıralanmış hali:2, 802, 24, 45, 66, 170, 75, 90
  4. Son haneye (100’ler hanesine göre) sıralanmış hali :2, 24, 45, 66, 75, 90, 170, 802

Yukarıdaki bu sıralama işleminde her aşamada bütün sayı kümesi üzerinden bir kere geçilmesi gerekmektedir. (yani n sayılık bir küme için her aşam n adım gerektirir). Bu işlemin ilave bir hafıza kullanılması ile daha da hızlı çalışması mümkündür.

Örneğin 10’luk sayı tabanında her sayıdan birer tane bulunması halinde her hane için 10 ihtimal bulunur. Bu her ihtimalin ayrı bir hafıza bölümünde (örneğin bir dizi veya bağlı liste) tutulması durumunda sıralama işlemi en büyük hane sayısı * n olmaktadır.

Örneğin 3 haneli sayılar için O(3n) ~ O(n) olmaktadır. Bu değer zaman verimliliği (time efficiency) arttırırken hafıza verimliliğini (memory efficiency) azaltmaktadır.

Videoda da anlatılan C kodu :

#include 
#include 

int getMax(int arr[], int n)
{
    int mx = arr[0];
    for (int i = 1; i < n; i++) if (arr[i] > mx)
            mx = arr[i];
    return mx;
}
 
void countSort(int arr[], int n, int exp)
{
    int output[n]; // output array
    int i, count[10] = {0};
 
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%10 ]++;
 
    for (i = 1; i < 10; i++) count[i] += count[i - 1]; for (i = n - 1; i >= 0; i--)
    {
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
        count[ (arr[i]/exp)%10 ]--;
	printf("%d-->%d,",i,(arr[i]/exp)%10);
    }
	printf("\n");
    for (i = 0; i < n; i++) arr[i] = output[i]; } void radixsort(int arr[], int n) { int m = getMax(arr, n); for (int exp = 1; m/exp > 0; exp *= 10)
        countSort(arr, n, exp);
}
 
int main()
{
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr)/sizeof(arr[0]);
    radixsort(arr, n);
    for(int i = 0;i<n;i++)
	printf("%d ",arr[i]);
    return 0;
}

Yorumlar

  1. Cem Yazar

    yazınız için çok teşekkürler. ancak kafama takılan bir nokta var şu son paragrafta bahsettiğiniz O(3n) ve O(n) ne olmaktadır açıklayabilir misiniz?

  2. Şadi Evren ŞEKER Article Author

    Hayır saniye cinsine çevrilemez. Basitçe programın büyüme fonksiyonudur. Yani örneğin bir ağaç (tree) üzerinde arama işlemi O(logn) zamanda olur bir dizi üzerinde arama işlemi ise O(n) zamanda olur. Bu ikisi arasında yorum yapılacak olursa 100 elemanlı bir veri kümesini dizi üzerinden aramak için en kötü ihtimalle 100 adım gerekir (aranan sayının dizinin sonunda bulunması durumu).
    Ağaç üzerinden ararken de en fazla 7 adım gerekir (log100 ~= 7 olduğu için). Bu değerleri zamana çevirmek istiyorsanız bir birim işlemin ne kadar zaman aldığı ile çarpabilirsiniz.

    Örneğin hafızdaki (RAM) bir değere bakmak 5ns ise dizideki değeri bulmak 500ns alırken ağaçta bu durum 35ns zaman alır. Ancak genelde algoritma analizleri big-oh diye geçen O notasyonu olarak bırakılır ve bu bizim algoritmaları karşılaştırmamız için yeterlidir.

    Zaman verimliliği yerine hafıza verimliliği için kullanılması durumunda da bu değer zamana benzer şekilde bir algoritmanın hafızada nasıl büyüdüğünü gösterir. Örneğin n elemanlı bir diziyi sıralamak için hafıza verimliliği (memory efficiency) θ(n) olan bir algoritma ile θ(2n) olan bir algoritma karşılaştırıldığında 2n olan algoritma, n olanına göre iki misli hafızada yer kaplar demektir.

    Bu değerler ( Yani big-oh , big-theta ve big-omega değerleri ve small-o ve small-omega değerlerinin tamamı master theorem adı verilen bir teoremden çıkmaktadır. )

    Şayet bu konuda daha detaylı bilgi edinmek istiyorsanız, seviyenizi bilmiyorum ama Cormen’in Introduction to Algorithms kitabı veya sippser’ın Introduction to Theory of Computation kitabı oldukça iyi kaynaklardır.

    Umarım yardımcı olur.

    Başarılar

    Şadi Evren ŞEKER

  3. ferandro

    hocam bunun kodu nasıl olur C# yardımcı olabilirmisiniz

    Design and code a recursive sorting algorithm which sorts positive integers(32 bit unsigned
    integers) in increasing order according to the following approach using C#:
    Here is an example of 8-bit integers:
    Think about the integers 132, 14, 2 and 9.
    The binary representation of these integers are:
    132 = 10000100
    14 = 00001100
    2 = 00000010
    9 = 00001001
    7. bit (the most significant bit)
    6.bit 5.bit 4.bit 3.bit 2.bit 1.bit 0.bit (the leas significant bit)

    132 1 0 0 0 0 1 0 0
    14 0 0 0 0 1 1 1 0
    2 0 0 0 0 0 0 1 0
    9 0 0 0 0 1 0 0 1
    Starting from the most significant bit, the algorithm changes the positions of the integers in
    the array as the following table represents:
    132 14 2 9
    Beginnig: 10000100 00001110 00000010 00001001
    After 7.bit placement 00001001 00001110 00000010 10000100
    After 6.bit placement 00001001 00001110 00000010 10000100
    After 5.bit placement 00001001 00001110 00000010 10000100
    After 4.bit placement 00001001 00001110 00000010 10000100
    After 3.bit placement 00000010 00001110 00001001 10000100
    After 2.bit placement 00000010 00001001 00001110 10000100
    After 1.bit placement 00000010 00001001 00001110 10000100
    After 0.bit placement 00000010 00001001 00001110 10000100
    Result: 2 9 14 132

    public void Our_sort(UInt32[] array, int p, int q, int digit)
    Here;

    array = the array which will be sorted by Our_sort.
    p = starting index
    q = last index

  4. Şadi Evren ŞEKER Article Author

    Sanırım bu bir ödev. Sanırım şu şekilde yarıdımcı olmamın bir sakıncası olmaz. Aslında C# kodundan ziyade herhangi bir dilde en kolay nasıl yazılacağını tartışmak daha yerinde olur çünkü problem dilden bağımsız. Size tavsiyem XOR (exclusive or) operatörünü dikkate almanız. Aslında bu soruyu çözmeden önce şunu düşünmenizde yarar var:

    iki değişkenin içindeki değeri, üçüncü bir değişken kullanmadan nasıl değiştirebiliriz?

    Oldukça klasik bir problemdir ve XOR operatörü sayesinde çözülebilir. Ardından aynı çözümü bu probleme uygulayabilirsiniz. Çünkü problemde detaylıca açıklandığı üzere 4 sayı için sadece 4 adet ikilik tabanda (binary) sayı tutulmuş.

    Başarılar

  5. ferandro

    evet hocam odevdi ama yapamdım bugün 23:50 de upload etmemiz lazımdı keşke kodu yazsaydınız ben biraz ilerledim ama sonucu gelmiyor..

    public UInt32 bit(UInt32 number, int sayi)
    {
    UInt32 temp = number;
    for (int i = 0; i < sayi; i++)
    {
    temp = temp / 2;

    }
    return temp % 2;
    }

    public void Our_sort(UInt32[] array, int p, int q, int digit)
    {

    int left = p;
    int right = q;
    int x = q;

    while (bit(array[left], digit) == 1)
    {

    if (bit(array[right], digit) == 0)
    {
    UInt32 temp;
    temp = array[left];
    array[left] = array[right];
    array[right] = temp;

    left++;

    }
    right–;

  6. Oğuzhan

    Hocam digit kavramına açıklık getirir misiniz ya. Bu radix sort’daki sıralama kısmını counting sortla yapıyolar boylece zaman karmaşıklığı O(n) de bitiyor. Fakat bu O(n)’i yukarı çekmemek adına tam hatırlamıyorum ama counting sortu az çalıştırarak sanırım bu zaman karmaşıklığını koruyorlardı. Bu yüzden belli digitlere bölüyorlardı sayıyı. Böylece daha efficient oluyormuş sanırım bu konuya net bir açıklık getirseniz? Yada yeni bir article hazırlasanız sırf bu konu için?

  7. Şadi Evren ŞEKER Article Author

    Anlayabildiğim kadarıyla şundan bahsediyorunuz.

    Counting sort (sayarak sıralama)
    algoritmasına göre sıralanacak elemanların alabileceği değerler arasında bir dizi oluşturulur ve bu dizi içerisinde elemanların kaç kere tekrar ettiği sayılır.

    Örneğin 1,2,3,1,2 gibi bir sayı grubunu sıralamak için 3 elemanlı bir dizi oluşturulur ve hangi elemana denk gelinirse o değer arttırılır. Sonra bu değerler sıra ile okunur ve sıralanmış değerler bulunur.

    Şimdi sayı aralığı birbirine yakın sayılar için sorun yok ama mesela elimizdeki sayılar 1,2,16556,3,3342 gibi aralıklı sayılar ise o zaman oluşturulacak olan dizide boşluklar oluşacaktır (sparse array). Bunu engellemek için tabanlara göre yakın değerler tutulur.

    Burada çok alternatif var mesela bir yöntem, sayıları önce son hanelerine göre bir diziye yerleştirme ardından çakışma oldukça diziyi genişletmektir.

    Bahsettiğiniz konu bu mu? Buysa boş bir zamanda bir örnek üzerinden açıklama eklemeye çalışırım siteye.

    1. Gurcan

      Hocam iyi gunler, radix algoritması sadece binary sayılar üzerinde mi yapılabilir? Decimal bir sayı dizisinde sayının birler basamağındaki sayıyı alsak ve onun üzerinden devam etsek olmaz mı? Bir sonraki adımda sayıyı 10’a böleriz.

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir