Sayarak Sıralama

     Sayarak Sıralama

Adını sıkça duyduğum , ama ancak geçen hafta tanıştığım Sayarak(Counting) Sıralama algoritmasını size tanıtmak istiyorum.En iyi ihtimalle worst case O(n logn) çalışan heap sort merge sort gibi algoritmaların aksine counting sort linear time da yani O (n) de çalışır.Ancak counting sort'u kullanabilmemiz için bazı şartlar vardır.Bunlara gelirsek sıralanan elemanların hepsinin integer veri tipinde olması gerekir , ayrıca dizideki en büyük elemanıda bilmemiz gerekiyor ve en son olarak da eşitlik durumlarını umursamamız gerekir.Yani normalde x<=y veya x>=y gibi sınamalar yaparken burada sadece x<y veya x>y durumlarını umursayacağız.

Algoritmanın işleyiş biçimine gelirsek de ; iki tane extra dizi ye ihtiyacımız olacak bu algoritmayı kullanırken bunlardan output için kulllanılanına B geçici işler için kullanacağımıza C dizisi ,standart sıralanmak istenen diziye de A dizisi diyelim.B dizisi sıralamak istediğimiz dizinin boyutunda boş bir dizi olarak tanımlı olmalıdır C dizisi ise k = en büyük sayı boyutunda olan bir dizi olacakdır.Burdaki k ya sayma numarası (counting number)da denilir.C nin bütün elemanlarına varsayılan olarak 0 elemanı atanır ardından dizinin tüm indexleri sırayla gezilerek o index numarasından A dizisinde kaç kere bulunduğu sayılarak her elemana işlenir.

Ardından zurnanın zırt dediği yere geliyoruz.Burada ise C dizisinde bir değişiklik daha yapacağız.İndex numarasının kaçıncı indexe kadar B dizisine yazılacağanı temsil eden bir C dizisi oluşturuyoruz.

for i=0 to k

int C[i] = 0

for j = 1 to A.lenght

C[A[j]]=C[A[j]] + 1

//üstteki resimdeki işlemler yapıldı

for i=1 to k

C[i] = C[i]+C[i-1]

//bu adımda da o index numarasındaki sayıdan küçük o dizide kaç kere başka sayının olduğunun hesabını yapıp bu verileri C dizisine işliyoruz

En son ve basit olarak da tek tek sayıları bulundukları sayılar gereğince B dizisine yerleştirerek sıralamayı sonlandırmış oluyoruz.

Fibonacci Heap

                                                               Fibonacci Heap

             

          Standart binary heap bir çok işlem için worst case de en kötü o(lgn) bazılarında o(1) de çalışır ancak böyle iki heap'ı birleştirmeye(union) çalıştığımızda o(n) de çalışır.Tanımını ve özelliklerini anlatacağım fibonacci heap union işlemini amortized(ortalama) zaman da o(1) de ,decrase key'i normal binary heap o(lgn) de yaparken fibonacci heap o(1) de , yine binary heap insert işlemini o(lgn) yaparken fibonacci heap o(1) de yapar.

              Peki bu fibonacci heap neye benzer.Hem heap gibi hemde ağaçlı yapıya sahiptir bu tanım binary heapa benzese de fibonacci heap'ı binary heapdan ayıran double linked list yani karşılıklı göstergeler kullanan bir yapıda olmasıdır.Bu bağlantılı liste özelliği sayesinde yukarıda bahsettiğimiz gibi union,insert gibi işlemler o(1) de çalışmakdadır.

             Fibonacci heap'ın bazı özelliklerinden bahsedecek olursak; root olan en üstteki node'lar bir biriyle çember şeklinde bağlantılı şekildedir.

1 – Her seviye bir alt seviyedeki elemanlardan herhangi bir çoçuğu pointerle gösterir.

2-Bu çocuk ve diğer 1.basamakdaki çocuklar root'u gösteren göstergelere sahiptir.

3-Her elaman üstteki node'dan daha büyüktür.

4-Her seviyede aynen rootların olduğu seviyedeki gibi bir çember bağlılık söz konusudur.

5.Her eleman bir üst seviyeyi gösteren bir bağlantıya sahiptir.

Not : Çizgiler pointerları simgelemektedir.

Aşşağıdaki resimde 1 kırmızı 2 yeşil 5 mavi 4 turuncu ile açıklanmıştır.

B Ağaçları

B Ağaçları

         Standart BST(Binary Search Tree) ler sadece çalışma zamanı düşünülerek RAM(ramdom access memory) üzerinde veri kullanımı yapılıyormuş gibi hesaplanarak tasarlanmış bir veri yapısıdır.RAM üzerinde verilerin silinmesi işlenmesi çok hızlı gerçekleşir ancak biz daha büyük verilerle uğraşmaya başladığımızda ram ne yazikki yetersiz kalacaktır.Bundan dolayı hem hızı hem de hafızayı dikkate alınan iki arama ağaçlarının versiyonları olan bazı veri yapıları tasarlanmıştır.Bunlardan bir tanesi Kırmızı – Siyah ağaçlarıdır,bir diğeri ise B Ağaçlarıdır.İsmi hala tartışılsada B ağaçları günümüzde birçok alanda kullanılmaktadır telefon kayıt rehberleri gibi.B ağaçlarının en önemli özelliği dengeli bir arama ağacı olmasıdır.Aynen bst de olduğu gibi sağ kol her zaman daha büyük elemana yönlenir.B ağacının karakteristik özelliklerinden bazıları ;

-Her node'da n tane eleman saklanıyorsa ;

-n+1 tane key vardır.Bu keyler alt basamaktaki nodeları gösteren pointerlardır.

-Node ların sahip olabileceği key sayıları vardır.Buna k dersek bu k >= 2 olup minumum derece olarak adlandırılır.Kök haricinde tüm node'lar minumun k-1 maximum 2k-1 tane key içerebilir.Örneğin k = 2 olduğunda biz B ağaçlarının bir özel türü olan 2-3-4 ağaçlarını oluşturmuş oluyoruz.

-Her yaprak(leaves) aynı seviyede olmalıdır.Not : yaprak en alttaki node lar ki buda ağacın seviyesine eşit oluyor.

-Bu B ağaçlarının yüksekliği konusunda ise şöyle bir eşitlik var .Yüksekliğe y dersek ;

y <= logk({n+1}/{2} )  olur.

Ekleme , Silme ,Arama İşlemleri

           Ekleme işlemi için her node da bulunan keyler takip edilir son durağa gelindiğinde yukarıdaki şartlardan biri bozuluyor mu diye kontrol edilir eğer bir sorun yoksa oraya eklenir ancak bir sorun varsa sağa veya sola döndürme işlemleri denilen işlemler yapılarak denge tekrardan kurulur.

Silme işlemi içinde ekleme işlemindeki aynı prosedür işlenir.

           Arama işlemini yaparken standart bst lerdeki gibi işlem yapılır ancak node lardaki tüm elemanlar kontrol edilerek eğer iki node arasında kalınıyorsa aradaki key ile ,tüm elemanlardan büyükse sağdaki key ile küçükse soldaki key ile yola devam edilir.Örneğin K elamanı yukarıdaki ağaçta aranırken kırmızıyla işaretlenen keyler takip edilinir.