algoritma

Bubble Sort

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Bubble Sort algoritmasını anlatmaya çalışacağız.

Sıralama Nedir?

Verileri bilgisayarda tutarken veya işlerken bazı durumlarda sıralı olmasını isteriz. Bu nedenle mevcut olan sıralama algoritmalarından bize uygun olanını seçip kullanmalıyız.

Çoğul eki kullandım çünkü halihazırda kullanılan bolca sıralama algoritması mevcut.

 

Sıralama Algoritmaları Arasındaki Farklar

En temel fark algoritmanın zaman ve hafıza karmaşıklığı arasındaki farklardır. Verimli algoritmalar O(N log N) zamanda çalışırken verimsiz algoritmalar O(N^2) zamanında çalışır.

 

bubble sort

 

Bubble Sort Hakkında

Bugünkü dersimizde verimsiz olarak adlandırdığımız algoritmalardan Bubble Sort algoritmasını öğreneceğiz. Peki neden verimsiz algoritma öğreniyoruz diye soranlara hemen belirtmeliyim ki bu tarz algoritmalar anlaşılması daha kolay ve mantığı basittir. Algoritmalar konusunda temel oluşturmak için bunları öğrenmemiz bizim çok yararımıza olacaktır. Bu temeli oluşturduktan sonra ileride öğreneceğiniz zor algoritmaları daha rahat kavrayacaksınız.

Fazla uzatmadan hemen algoritmamıza geçelim:

 

 

Temel mantığımız her diziyi baştan sona gezdiğimizde bir elemanı doğru bir şekilde sıralamış olacağız. Yani her elemanı doğru sıralamak için diziyi uzunluğu kadar gezmemiz gerekmekte.

Yukarıdaki for döngümüz diziyi N defa yani uzunluğu kadar gezmemizi sağlıyor. İçindeki for döngüsü ise sondan başa gelerek küçük elemanı başa doğru getiriyor. if kontrolü sağdaki elemanın soldaki elemandan küçük olup olmadığını kontrol ediyor. Biz istiyoruz ki sağdaki eleman her zaman soldakinden büyük olması lazım. Çünkü bu örneğimizde algoritma diziyi küçükten büyüğe doğru sıralıyor.

Not: Büyükten küçüğe doğru sıralamak isteseydik if kontrolünün içindeki küçüktür işaretini büyüktür yapmamız yeterli olacaktır.

Örnek bir sayı dizisi üzerinde denersek sırayla alacağımız sonuç şöyle olacaktır:

Başlangıç
56 3 96 -2 1

1. döngü
-2 56 3 96 1

2. döngü
-2 1 56 3 96

3. döngü
-2 1 3 56 96

4. döngü
-2 1 3 56 96

5. döngü
-2 1 3 56 96

Her döngümüzün sonunda sağ tarafta kalan küçük bir eleman sol taraftaki yerine yerleştiriliyor. Ancak dikkat ettiyseniz 3. döngüden itibaren dizimiz sıralı olmasına rağmen bilgisayar hala daha sıralamaya çalışıyor.

Çünkü bu ve diğer bütün algoritmalar en kötü seneryoda dahi çalışması için tasarlanmıştır. Verdiğimiz sayı dizisi en kötü seneryo olmadığı için 5 kere döngü yapmasına gerek kalmadan 3 döngüde sıralama işlemini gerçekleştirmiştir.

Algoritmamızı iyileştirmek için dilersek her seferinde dizimizin sıralı olup olmadığını kontrol eden bir ifade yazabiliriz. Böylelikle sıralı olduğu anda işlemi durdurup çıkmamız algoritmayı daha verimli hale getirecektir.

Örnek:

Bubble Sort Analizi

Üstteki for döngümüz en kötü seneryoda N defa dönüyor. İçindeki for döngüsü ise en kötü seneryoda ilk başta N daha sonra N-1 en sonda da 1 kere döndüğü için bu algoritmanın karmaşıklığı N*(N-1) olacaktır. Bu ifadenin Büyük O notasyonunda gösterimi ise O(N^2)‘dir.
Farklı Dillerde Bubble Sort Kodları:

C/C++

Java

 

Python

Okuduğunuz için teşekkürler umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.

Tüm Algoritma Derslerimiz İçin tıklayınız.

Hasan Bal

Competitive Programmer

Web Developer

6 Yorum

    • Öncelikle sorunuz için teşekkür ederim.
      Bubble sort algoritmasında her seferinde bulunduğumuz elemanı ya bir sağımızdakiyle ya da bir solumuzdakiyle karşılaştırırız. Sizin bahsettiğiniz kodda bir sağımızla karşılaştırmışız. Ve en sondaki elemanın sağında eleman olmadığı için onu kontrol etmeye gerek yok. Bu nedenle n-1. elemana kadar gidiyoruz.

  • Merhaba,

    binary search ve bubble sort u online java IDE de denemeye çalıştım. Ancak doblar hata verdi. Daha doğrusu çalıştırılamadı. Buradaki kodlar yalnızca for döngüsünde nasıl yazıldığını göstermek için midir? tam çalıştırma kodu değil midir?

    • Merhaba,

      Simdi denedim calisti ancak bu bir fonksiyon oldugu icin icindeki kodlari main’e yazdim ve diziyi tanimladim. Bu degisiklikleri yapmayi unutmus olabilirsiniz.

Haftalık Bülten

Mobilhanem'de yayınlanan dersleri haftalık mail almak ister misiniz?