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:

Sıralanmamış sayılarımız:170, 45, 75, 90, 2, 24, 802, 66
İ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ı.
Sıradaki hane olan 10′lar hanesine göre sıralanmış hali:2, 802, 24, 45, 66, 170, 75, 90
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.

« Doğrusal Arama (Linear Search) | Taşınabilir imgeharitası (PGM, PNM, PPM, PBM) »

Yorumlar

Toplam 3 yorum var.

Cem Yazar | 05 Apr 2009, 20:21
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?
Şadi Evren ŞEKER | 05 Apr 2009, 20:28
yazının sonundaki O(3n) ve O(n), master teoremindeki en kötü durum analizi yapmaya yarayan sembollerdir ve big-oh olarak isimlendirilirler
daha detaylı bilgi için En kötü durum analizi başlıklı yazıyı okuyabilirsiniz.
Şadi Evren ŞEKER | 06 Apr 2009, 23:14
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

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Taban Sıralaması (Radix Sort)' isimli yazı 09 Nov 2008 tarihinde, saat: 20:36 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1751 defa okunmuştur.

Benzer yazıları algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar