16 Kasım 2014 Pazar

Özel Algoritmalar 1 Bubble Sort Algorithm (Kabarcık Sıralama Algoritması)

Merhabalar herkese. Yeni bir konu anlatım serüveni ile bir yolculuğa başlıyoruz. Bu anlatımlar çerçevesinde küçük, büyük özel algoritmalardan bahsetmeye çalışacağım sizlere. İlk anlatımlarım sıralama algoritmaları ile başlayacak. Daha sonra tez konum olan Genetik Algoritmalara kadar gelecek ve ilerisine de geçeceğiz inşallah.

O zaman Bismillah diyelim ve ilk algoritmamız olan Bubble Sort algoritması ile işe koyulalım.

Sıralama algoritmalarının yazılımda önemli bir yere sahip olduğunu söyleyebiliriz. Çünkü karmaşıklığı önleyip istediğimiz verileri istediğimiz düzende sıralamamıza yardımcı olup daha iyi performanslar elde etmemizi sağladığı gibi doğru bir kullanım ile bellekte de az yer kaplama gibi özellikleri vardır.


Bugünkü konumuz olan ingilizce ismi bubble sort türkçe ismi kabarcık sıralama algortimaları yalın bir sıralama algoritmasıdır.

Neden kabarcık algoritması denmiş? Biraz vikipedilik bilgiler ile işe giriş yapalım.

Sebebi şu kıymetli dostlar. Çünkü dizi içinde büyük sayılar sanki suyun altında oluşan bir kabarcığın suyun yüzeyine ilerlediği gibi dizinin en büyük elemanı da dizinin sonuna doğru ilerleme eğilimde olduğundan bu algoritmayı bu şekilde isimlendirmişler.

Bir vikipedilik bilgi daha.

Kabarcık sıralama algoritmasının ortalama ve en kötü durumdaki karmaşıklığı O(n^2)'dir. Algoritma ortalama ve en kötü durumda (n^2 /2) adet karşılaştırma ve yer değiştirme gerçekleştirir.

Peki nasıl işler bu algoritmanın mantığı?

Elimizde bir dizi sayı kümesi olduğunu düşünelim. Algoritma bu dizi üzerinde ilerlerken her aşamada başlangıçtan başlayarak sadece iki sayı ile ilgilenir. Bu iki sayıyı karşılaştırır eğer ilk sıradaki sayı ikinci sayıdan büyükse bu algortima bu iki sayının dizideki yerini değiştirir. Döngüler sayesinde içinde gezme işlemi yaptığımız için her ikili inceleme döngünün tek adımına karşılık gelmektedir. Algoritma, herhangi bir değişiklik yapılmayıncaya kadar dizinin başına dönerek kendisini yineler.

Olaya şöyle küçük bir sayı dizisi örneği ile bakalım isterseniz.

Elimizde 

A= (5 3 8 9 7) şeklinde bir sayı dizimiz olsun.

Algoritma çalışmaya başladığında ilk sayı ile işe başlar. Elimizdeki ilk değer 5 bunu bir sonraki değer olan 3 ile karşılaştırmasını yapar. Eğer 5 değeri 3 değerinden büyük ise bu iki sayının yerlerini değiştirir. Yani büyük olan sayıyı bir adım ileri ötelemiş olur. Döngünün ilk adımı bu işlem sonunda bitmiştir. 

Yeni dizimizin haline bir bakalım.

A=(3 5 8 9 7) dizimiz bu hale geldi.  

Döngü ikinci adımda dizinin 2. ve 3. elemanlarının karşılaştırmasını yapar. Yani 5 değeri büyük mü 8 i araştırır. Sonuç false değerini döndürdüğü için dizi üzerinde bir değişiklik olmaz ve aynen böyle kalır. Bu şekilde en büyük sayı en sona gelene kadar bu işlem devam edecektir.

Olayın mantığına baktığımız bu işlemleri yaptırabilmek için bize iç içe iki for döngüsü gerekecektir.

En dıştaki for döngüsü dizinin tüm elemanları için tekrar edilmek zorunda olduğu için dizi elemanı sayısına eşit olacaktır. Yani n elemanlı bir dizi n kere for döngüsüne girmelidir.



Peki bir içindeki döngü kaç kere dönecek buna nasıl karar veriyoruz?

Aşağıdali örneğe bakarakta buna karar verelim.



Gördüğümüz gibi tüm karşılaştırma işlemi n-1 kadar olmaktadır. Demek ki içteki her defasında for n-1 tane dönmeli yargısına ulaşabilmekteyiz.

Algoritmamız aslında formal olmayan formatta böyleydi diyebiliriz. 

Anlattığım olayı birde Vikipediadan daha görsel bir halini görelim.



Şimdi bunun birde C# da yazılmış halini inceleyerek nasıl çalıştığına bir göz atalım.


Öncelikle formumuza bir göz atalım kısaca ne yapacağımızdan bahsedeyim.



Dizi değerleri diye belirtmiş olduğum bölümde dizinin kaç elemanlı olduğunu giriyoruz ve bu değeri gönder diyoruz. 

Tam burada işleyen kodlar şunlar.




Bu şekilde sayılarımızı oluşturmuş olduk.

Şimdi sıralı kısmında Bubble Sort butonuna tıkladığımızda çalışacak kodları görelim ve en sonda sonuca bakıp dersin sonuna gelmiş olalım.


Gerekli tüm açıklama kodlar içinde yapılmıştır.

Artık ne yaptığımızı görme vakti.




Gördüğümüz gibi kabarcık sıralama algoritmasını kullanarak dizi elemanlarımızı istediğimiz düzene koymuş olduk. İlk algoritmamız böyleydi umarım faydalı bir yazı olmuştur selametle vesselam.


Murat Bilginer



Hiç yorum yok:

Yorum Gönder