...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.
631 views
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?
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.
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
hocam asimtotik notasyonlar hakkında linkiniz var mı?
elbette,aşağıdaki yazılar ilginizi çekebilir :
http://www.bilgisayarkavramlari.com/2010/09/24/algoritma-analizi-analysis-of-algorithms/
http://www.bilgisayarkavramlari.com/2009/06/02/ozyinelilerde-ana-teorem-master-theorem/
http://www.bilgisayarkavramlari.com/2010/06/17/karmasiklik-siniflari-complexity-classes/