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.

Dinamik Programlama'da Hatırlama Metodu

Dinamik Programlama'da Hatırlama Metodu

Dinamik programlama bize her hangi bir problemin çözümünde klasik olarak kullandığımız algoritmalardan daha etkili algoritmalar oluşturmamızı sağlar.Memorize,Bottom-Up gibi bir çok yöntemle algoritmalarımızı geliştirebiliriz.Ben bu anlatımda Hatırlama* (Remember) yöntemini kullanarak fibonacci sayılarının nasıl daha etkili hesaplanabileceğini anlatacağım.

Öncelikkle bazı temel mantık öğelerini ve klasik algoritmamızın çalışma zamanından başlayalım;

F(1)=F(2) = 1

F(n) = F(n-1) + F(n-2) bu formüller fibonacci serisinin formülleştirilmiş halidir.

T(n) ise T (n-1)+ T(n-2) + O(1) e eşittir.Klasik impelementasonumuza bakarsak

Fib(n):

if n<=2 : f =1

else : f = fib(n-1) + fib(n-2)

return f

Yukarıdaki çözüm recursive şeklinde fibonacci sayılarının hesaplanmasını sağlayan algoritma.Biz bu algoritmayı çalıştırdığımızda programımız aşşağıdaki ağacın kollarındaki tüm elemanları hesaplayarak kökde duran sonucu bulmaya çalışıyor.

Görev ağacına baktığımızda aslında bazı değeri zaten önceden hesapladığınızı üst seviyeye geçerken boş yere aynı değeri hesapladığımızı görmüşsünüzdür hatta kökün sağındaki koldaki n-2 değerinin diğer sol kolun bir alt seviyesinde hesaplandığını görülüyor ,o halde bizim komple o sağ kolu hesaplamamız gereksiz.Peki bundan nasıl kurtulacağız ? Hatırlayarak ! . Her hesapladığımız değeri bir key-value sisteminde(programlama dillerine göre değişir) saklayarak boş hesaplamalardan kurtuluyoruz.Örneklemek gerekirse aşşağıdaki kodla ;

memo = {}

Fib(n):

   if n in memo return memo[n]

   if n<=2 : f=1

   else : f = Fib(n-1) + Fib(n-2)

   memo[n] = f

   return f

Peki bu çözümümüzün T(n)'ı kaça eşit derseniz .

Zaman = parçalanmış çözümler * zaman/parçalanmış çözümler zaman = zaman ? Yani yukarıdaki T(n-1)+T(n-2)+O(n) ? Tabikide hayır. Zaman/Parçalanmış çözümler kısmını biz hatırlama yöntemini kullanarak O(1) olarak hesaplıyoruz parçalanmış çözümlerde n e eşit olduğundan T(n) = O(n) oluyor.

*Farklı kaynaklarda Memorize,Remember,memoize şeklinde geçebilir bu kavram.

En Yakın Komşu Problemi Ve K-d Ağacı

En Yakın Komşu Problemi Ve K-d Ağacı

x ve y kordinatları düzleminde tüm noktalar x ve y olmak üzere iki kordinat değerine sahiptir.Birinci noktanın kordinatları x1,y1 ikinci noktanınkiler ise x2,y2 olmak üzere iki nokta arasındaki en yakın uzunluk kök içerisinde (x1-x2)^2 + (y1-y2)^2 olarak hesaplanır.K-d ağaçları sayesinde tüm noktaların aradığımız noktaya olan uzaklıklarını bu formülle hesaplayıp sıralama derdinden kurtulmuş oluyoruz.K-d ağacında x ve y kordinat değerlerine göre alandaki noktaları parçalara bölerek bir ağaç oluşturuyoruz.

Peki nedir bu k-d ağacı ve nasıl oluşturulup nasıl kullanacağız.K-d ağacı öncellikle bir BST(binary search tree,ikili arama ağacı)dir.Oluştururken yararlanacağımız kurala gelecek olursak;normal bst'lerde sayısal değer olarak büyüklük küçüklük durumuna bakardık burda da kordinatların değerine bakarak ağacı oluşturacağız ancak bir seviyede x kordinatını bir seviyede ise y kordinatını dikkate alacağız.Kök(root) seviyede x kordinatına bakılarak oluşturma işlemine başlarız bir örnek yapacak olursak.;

Ağaça yerleştirme sıralamam B,A,C,D,E olarak oldu ancak bu keyfi bir sıralamaydı siz istediğiniz sırayla oluşturabilirsiniz gerekli şartları sağlamak üzere ancak x kordinatı olarak en ortadaki kordinatı bulup kök kabul etmek ağacın daha dengeli olmasını sağlayarak çalışma zamanını iyileştirebiliriz.K-d ağacında arama,ekleme,silme işlemleri avarege case (ortalama zamanda)'de log(n) olarak ,worst case(en kötü durumda)'de n olarak çalışır.Aşşağıda örnek bir k-d ağacı ;

Peki en yakın komşu problemini nasıl çözeceğiz.Bu problemi k-d ağaçlarını kullanırken çözerken kullanacağımız algoritma yinelemeli(recursively) bir algoritmadır.İlk kök node'unu şampiyon ilan ederek algoritmamıza başlarız.Ardından aramamızı devam ettirerek sağ'da veya solda yinelemeli yaparak şampiyonları değiştirip en sondaki şampiyonu bularak noktamızı belirlemiş oluruz peki o an belirlediğimiz şampiyonun sağına'mı soluna mı gideceğiz buna karar vermek için geometriden bir örnekle açıklamak istiyorum aşşağıdaki resim aydınlatıcı olacaktır.

Resimdekileri açıklayayım.İlk olarak B'yi biz şampiyon ilan ettik , ardından rastgele olarak bu ağacın sol kolunda araştırma yapmaya başladık .Normalde yenilemeli olarak algoritmayı tüm ağaca uygulayacağımız için bunu rastgele olarak yaptık.Ardından baktık'ki yeni noktamız olan A aradığımız noktaya daha yakın.Şekilde yeşil noktalarla çizilen çizgiler B 'nin X eksenine göre A nın Y eksenine göre çizilmiş uzantıları.Bunları çizmemizin nedeni ise eğer A , B den daha büyükse A dan daha yakın bir nokta varsa onunda maviyle karalanmış olan bölgede olacağını anlatmaktır.Demekki bu noktalar B'nin kesinlikle solunda(x kordinatı değeri B'den daha küçük) ise demekki B'nin ağaçtaki sağ kolunu aramamıza gerek kalmadığını gösterir.Bu işlemleri sonuna kadar yaptığımızda C'nin en son şampiyonumuz olduğu açığa çıkar ve algoritmamız başarıyla sonuçlanmış olur.

Hibbard Deletion

Hibbard Deletion

BST(Binary Search Tree)'lerde silme(Deletion) işlemi yapılırken eğer silinen elemanın tek çocuğu varsa silinen node'un yerine bu eleman yerleştirilerek ağaç düzenlenmiş olur.Ancak bu elemanın iki çocuğu varsa ne olur ? Bu tür durumlar için Hibbard Deletion adında bir yöntem uygulanır ki çok basit bir yöntemdir.Silinen elamanın sağındaki kolun en küçük elemanı bulunup o node'a yerleştirilir.

Örnek :

Örnek silinmek istenen node 67 bu elemanın sağında ki elemanları bir ağaç gibi farz edip o ağacın en küçük elemanı olan 79'u silinen node'un yerine yerleştiriyoruz ve ağacımız şu şekili alıyor ;

Heap Sort

Heap Sort

Heap Nedir ?

Heap Türkçeye geçmiş haliyle yığın ağacı demektir.Yığın ağaçları verileri dengeli bir ikili ağaçda saklayarak bir veri yapısı oluşturur.Bu yapıda node'lar aynen öncelikli kuyruk gibi öncelik özelliğene göre doldurulur.Aşşağıda basit bir yığın ağacı var.

Yukarıdaki ağaç dizidede [64 , 25 , 52,11,9,32] şeklinde tutulabilir.

Her bireyin üstündeki node kendisinden büyük şekilde sıralanmış gördüğünüz üzere.Bu ağacın bu hale gelmesi için en alt seviyedeki ebeveynden başlarayarak karşılaştırma ve değiştirme işlemleri yapılır.Ardından bir üst node geçilir.Bir eleman aşşağı doğru iniyorsa bir alttındaki elamanlarlada karşılaştırma ve değiştirme işlemleri uygulanır eğer karşılaştırma olumsuz sonuçlanmışsa diğer aynı seviyedeki diğer noda ,aynı seviyede node kalmamışsa üst seviyedeki node'a geçilir.Örnekle pekiştirelim.

En alt seviyenin bir üst seviyesinden ve soldan başlayarak başlıyoruz karşılaştırmaya.Alttaki node lardan varsa büyüğü veya ikiside büyükse en büyüğüyle değiştirme işlemi yapıyoruz.34 sayısının alt elemanları olduğu için karşılaştırmayı yaptık ancak diğer 2,3,4 diye numaralandırdığın nodeların alt elemanı olmadığı için karşılaştırma yapamıyoruz.Ardından bir üst seviyeye çıkıp aynı işlemleri tekrarlıyoruz .Root(kök) elemanada aynı işlemi yaptıktan sonra gördüğünüz üzere tüm ebevynler çocuklarından büyük durumdalar.

Heap sort ? Heap sortta ise en üstteki elemanı en alttaki ve en sağdaki node ile değiştiririz.Ve büyük elemanı heapdan çıkarırız.En üstteki elemana üstteki heap oluştururken yaptığımız aşşağıya doğru karşılaştırma ve değiştirme işlemlerini yaparız.Tekrardan en üstteki elemana aynı işlemleri yaparak heapı boşaltırız ve heap sort işlemi başarıyla tamamlanmış olur.Resim çizimim fazla iyi olmadığı için aşşağıdaki videyu örnek olarak vereceğim yukarıdaki resimlerin iğrençliklerinden dolayıda kusura bakmayın :)

3-way partitioning

Quick-sort(hızlı sıralama) algoritmasının en büyük özelliklerinden birisi parçalama metodudur ki quicksort algoritması divide and conquer(parçala ve feth et) algoritmaları kategorisine girer.Normal parçalama işlemini yaparken eğer dizimizde birden fazla aynı değerden varsa(duplicate keys) algoritmamızı daha hızlı hale çevirmek için Djktra yeni bir yöntem geliştirmiştir.Bu duplicate değerleri dizinin ortasında toplayıp sağına ve soluna iki parça oluşturarak diziyi 3 parçaya bölme yöntemine 3-way partitioning yöntemi denir.Şu an pek lambanın parlamadığının farkındayım.Hemen nasıl yapıldığını öğrenerek lambanın parlaklığını arttıralım.

Buraya kadar bildiğimiz quicksort algoritmasındaki gibi değişimleri yaptık sadece seçtiğimiz en sağdaki duplicate key değerini atlayarak.

Ancak swap yaptığımız elemanlardan birisiseçtiğimiz duplicate değerlerden birisiyse değiştirdiğimiz yöndeki en uçtaki duplicate olmayan eleman ile yerlerini swap yapıyoruz.

Hatta iki duplitace eleman değişitirilse bile aynı işlemi onlarada uygulayarak yer değiştirebilecekleri en sağ ve en soldaki elemanlarla swap işlemi yapılır.

Görüldüğü gibi ortada çıplak gibi bir eleman kaldı bu eleman swap yapacak bir sevgili bulamayacağından artık yöntemin son basamağına geçeriz.En soldaki duplicate değerleri bu çıplak kalan elemanın soldaki elemanlarla tek tek swap yaparız en sağdaki duplicate değerleri de bu çıplak eleman dahil olmak üzere sağa doğru yönelerek değişimleri tamamlarız ve 3-way partioning yöntemimiz sonlanarak parçalama işlemimiz tamamlanmış oluyor.


sol taraftaki swaplar

sağ taraftaki son swaplar