Algoritma ve Programlama Dünyası — Uygulama 5 (Bubble Sort)

Merhaba sevgili okurlar! Algoritma ve programlama dünyası serisinin bir önceki bölümünde, ‘Insertion Sort’ adlı bir sıralama algoritmasını ve Python dilinde bu algoritmanın nasıl uygulanacağını görmüştük. Bu bölümde, başka bir sıralama algoritması olan “Bubble Sort” üzerinde duracağız.

Bubble Sort Nedir?

Bubble Sort, sıralama algoritmalarının en basitlerinden biridir. Adını, dizi elemanlarının bir kabarcık gibi yüzeye çıkma şeklinden alır. Her adımda, yan yana olan iki eleman karşılaştırılır ve gerektiğinde yer değiştirilir. Bu işlem, tüm liste sıralanana kadar devam eder. Kod yazmaya gecmeden önce uyuglamayı daha iyi anlamak için pseudocode yazalım.

function bubble_sort(list) is
    n := length(list)
    for i from 0 to n do
        for j from 0 to n - i - 1 do
            if list[j] > list[j + 1] then
                swap list[j] with list[j + 1]
            end if
        end for
    end for
end function

Photo by Julia Taubitz on Unsplash

Python’da Bubble Sort Uygulaması

Bubble Sort algoritmasının Python’da uygulanması aşağıdaki gibidir:

def bubble_sort(liste):
    n = len(liste)
    for i in range(n):
        for j in range(0, n-i-1):
            if liste[j] > liste[j+1] :
                liste[j], liste[j+1] = liste[j+1], liste[j]

Bu kodda, dış döngü, geçiş sayısını kontrol eder. İç döngü ise her geçişte, yan yana olan elemanları karşılaştırır ve gerektiğinde yer değiştirir.

Şimdi bu algoritmayı bir örnekle test edelim:

liste = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(liste)
print(liste)

Çıktımız sıralanmış bir liste olacaktır: [11, 12, 22, 25, 34, 64, 90]

Bu çıktı, Bubble Sort algoritmasının doğru bir şekilde çalıştığını gösterir.

Algoritmanın Görsel Örneği

Bubble Sort’un adım adım uygulamasını göstermek için yukarıdaki diziyi sıralayalım.

Başlangıç listemiz [64, 34, 25, 12, 22, 11, 90] olsun.
1. Adım: [34, 64, 25, 12, 22, 11, 90]
2. Adım: [34, 25, 64, 12, 22, 11, 90]
3. Adım: [34, 25, 12, 64, 22, 11, 90]
4. Adım: [34, 25, 12, 22, 64, 11, 90]
5. Adım: [34, 25, 12, 22, 11, 64, 90]
6. Adım: [25, 34, 12, 22, 11, 64, 90]
7. Adım: [25, 12, 34, 22, 11, 64, 90]
8. Adım: [25, 12, 22, 34, 11, 64, 90]
9. Adım: [25, 12, 22, 11, 34, 64, 90]
10. Adım: [12, 25, 22, 11, 34, 64, 90]
11. Adım: [12, 22, 25, 11, 34, 64, 90]
12. Adım: [12, 22, 11, 25, 34, 64, 90]
13. Adım: [12, 11, 22, 25, 34, 64, 90]
14. Adım: [11, 12, 22, 25, 34, 64, 90]

Sonuç olarak, başlangıçtaki [64, 34, 25, 12, 22, 11, 90] listesi, Bubble Sort algoritması uygulandıktan sonra [11, 12, 22, 25, 34, 64, 90] şeklinde sıralanmıştır.

Her geçişte, en büyük sayı sanki bir kabarcık gibi yüzeye çıkar ve doğru konumuna yerleşir.

Algoritmanın Zaman ve Hafıza Karmaşıklığı

Kısaca, Bubble Sort, genellikle yavaş bir algoritma olarak bilinir. Zaman karmaşıklığı her durumda O(n²) olarak kabul edilir çünkü dizinin boyutuna bağlı olarak karesel sayıda işlem yapılır.

Hafıza karmaşıklığı ise O(1)’dir, çünkü ekstra bir hafıza alanı kullanılmaz. Bu, Bubble Sort’un ‘in-place’ bir algoritma olduğu anlamına gelir.

Zaman Karmaşıklığı:

1. En iyi durum: Eğer girdi dizisi zaten sıralanmışsa, Bubble Sort hiçbir değişiklik yapmadan tüm diziyi tarar. Bu durumda zaman karmaşıklığı O(n) olacaktır. Burada n, dizinin eleman sayısını temsil eder.
2. En kötü ve Ortalama durum: Eğer girdi dizisi ters sıralanmışsa ya da rastgele sıralanmışsa, Bubble Sort algoritması, her elemanın doğru pozisyona gelmesi için tüm elemanları tarayacaktır. Bu durumda, her elemanın karşılaştırılması ve gerekliyse yer değiştirilmesi işlemleri n*(n-1)/2 kez gerçekleştirilir. Bu durumda zaman karmaşıklığı O(n²) olacaktır.

Hafıza Karmaşıklığı:

Bubble Sort sıralama işlemi orijinal dizinin üzerinde gerçekleşir ve ekstra hafıza gerektirmez. Bu nedenle, hafıza karmaşıklığı O(1)’dir, bu da algoritmanın sabit bir hafıza alanı kullandığı anlamına gelir.

Ancak Bubble Sort algoritması, büyük veri setleri için özellikle verimsizdir çünkü zaman karmaşıklığı çok yüksektir. Bu nedenle, genellikle eğitim amaçlı olarak veya veri setinin çok küçük olduğu durumlardan başka kullanılmaz. Daha büyük veri setleri için genellikle daha verimli olan başka algoritmalar, örneğin Quick Sort, Merge Sort veya Heap Sort, kullanılır.

Sonuç

Bubble Sort, anlaşılması ve uygulanması kolay bir sıralama algoritmasıdır, ancak genellikle yavaştır ve büyük diziler üzerinde çalıştığında etkili değildir. Bununla birlikte, algoritma teorisi ve düşünce biçimini öğrenme konusunda önemli bir adımdır.

Bir sonraki bölümde yeni bir sıralama algoritması olan “Quick Sort”u inceleyeceğiz. Takipte kalın! Eğer bu yazıyı beğendiyseniz aşağıdaki alkışa istediğiniz kadar tıklayarak yazılarıma destek olabilirsiniz :)

Herhangi bir sorunuz olursa veya benimle iletişim kurmak isterseniz, tüm sosyal medya hesaplarım aşağıdaki linkte yer alıyor.

Turhan Can Kargin | Home

Ayrıca diğer blog yazılarımı aşağıda yer alan websitem üzerinden takip edebilirsiniz.

Turhan Can Kargın

Bir sonraki yazıda görüşmek üzere!