Bubble Sort Nasıl Çalışır? Kabarcık Sıralaması Adım Adım Örnek

Bubble Sort, yani kabarcık sıralaması, dizide yan yana duran elemanları soldan sağa karşılaştırır ve soldaki değer daha büyükse bu iki elemanın yerini değiştirir. Her tur tamamlandığında, o turda karşılaşılan en büyük değer dizinin sağ tarafına doğru ilerleyerek doğru konumuna yaklaşır.

Bu hareket, su içindeki büyük bir kabarcığın yukarı çıkmasına benzetilebilir. [5, 1, 4, 2, 8] dizisinde ilk karşılaştırmada 5 ve 1 ele alınır, 5 büyük olduğu için dizi [1, 5, 4, 2, 8] hâline gelir. Ardından 5 ve 4 karşılaştırılır, sonra 5 ve 2 karşılaştırılır. Böylece 5 sağa doğru ilerler ve ilk turun sonunda dizi [1, 4, 2, 5, 8] olur.

Bubble Sort yan yana elemanları karşılaştırarak nasıl çalışır?

Bubble Sort, her adımda yalnızca yan yana bulunan iki elemanı karşılaştırır. Soldaki değer sağdakinden büyükse iki değer yer değiştirir; soldaki değer küçük ya da eşitse karşılaştırma değişiklik yapılmadan tamamlanır.

Örneğin başlangıç dizisi [5, 1, 4, 2, 8] olsun. Algoritma soldan başlar ve şu sırayla ilerler:

1. 5 ile 1 karşılaştırılır. 5 büyük olduğu için yer değiştirir ve dizi [1, 5, 4, 2, 8] olur.
2. 5 ile 4 karşılaştırılır. 5 büyük olduğu için dizi [1, 4, 5, 2, 8] hâline gelir.
3. 5 ile 2 karşılaştırılır. Yer değiştirme sonucunda dizi [1, 4, 2, 5, 8] olur.
4. 5 ile 8 karşılaştırılır. Soldaki değer küçük olduğu için değişiklik yapılmaz.

Bu turun sonunda dizinin sağ tarafında bulunan 8 zaten en büyük değer olduğu için yerini korur. 5 ise karşılaştırmalar sırasında sağa doğru ilerleyerek kendisine uygun konuma taşınır. Sonraki turlarda aynı işlem kalan bölüm üzerinde sürdürülür.

Beş elemanlı dizi üzerinde Bubble Sort turları nasıl ilerler?

[5, 1, 4, 2, 8] dizisinde her tur, yan yana elemanların karşılaştırılması ve gerektiğinde değiştirilmesiyle ilerler. Tur sonunda sağ tarafta doğru konuma ulaşmış değerler bulunduğu için sonraki tur daha kısa bir bölümde çalışır.

Bayraksız Bubble Sort, dizi 3. tur sonunda sıralanmış olsa bile planlanan 4. turu da çalıştırır. Bayraklı sürüm ise 3. turda hiç yer değiştirme yapılmadığını fark ederek dizinin sıralı olduğunu anlar ve sonraki turu başlatmadan durur.

Python’da Bubble Sort iç içe döngülerle nasıl yazılır?

Bubble Sort, dış döngüyle sıralama turlarını, iç döngüyle de yan yana duran elemanların karşılaştırılmasını yürütür. Soldaki eleman sağdakinden büyükse iki değer yer değiştirir ve her tur sonunda büyük değerlerden biri dizinin sağ tarafına ilerler.

def bubble_sort(dizi):
    n = len(dizi)

    for i in range(n - 1):
        for j in range(n - i - 1):
            if dizi[j] > dizi[j + 1]:
                dizi[j], dizi[j + 1] = dizi[j + 1], dizi[j]

    return dizi

n değişkeni dizinin eleman sayısını tutar. Dıştaki for i döngüsü sıralama turlarını başlatır. İçteki for j döngüsü, o turda karşılaştırılacak komşu çiftleri seçer. if koşulu soldaki değer büyük olduğunda çalışır. Python’daki dizi[j], dizi[j + 1] = dizi[j + 1], dizi[j] biçimi, iki değeri güvenli şekilde yer değiştirir. Tüm turlar tamamlandığında return dizi sıralanmış listeyi fonksiyondan döndürür.

Bayraklı sürümde swapped değişkeni, o tur içinde en az bir yer değiştirme yapılıp yapılmadığını izler. Hiçbir değişiklik gerçekleşmezse dizi sıralanmış kabul edilir ve break ile gereksiz turlar durdurulur.

def bubble_sort_flagli(dizi):
    n = len(dizi)

    for i in range(n - 1):
        swapped = False

        for j in range(n - i - 1):
            if dizi[j] > dizi[j + 1]:
                dizi[j], dizi[j + 1] = dizi[j + 1], dizi[j]
                swapped = True

        if not swapped:
            break

    return dizi

dizi = [5, 1, 4, 2, 8]

print(bubble_sort(dizi.copy()))
print(bubble_sort_flagli(dizi.copy()))

İki fonksiyonun da çıktısı [1, 2, 4, 5, 8] olur. copy() kullanılması, iki fonksiyonun başlangıç listesinin ayrı bir kopyası üzerinde çalışmasını sağlar.

İç döngü neden her turda bir eleman eksilir?

İç döngünün range(n - i - 1) biçiminde kurulmasının nedeni, her turun sonunda dizinin sağ tarafında bir elemanın doğru konumuna sabitlenmesidir. Bu elemanın yeniden karşılaştırılması gerekmediği için sonraki turun aralığı kısalır.

Beş elemanlı bir dizide ilk turda i = 0 olur ve j değerleri 0, 1, 2, 3 arasında ilerler. Böylece dizi[j] ile dizi[j + 1] çiftleri karşılaştırılır ve son erişim dizi[3] ile dizi[4] arasında yapılır. İkinci turda i = 1 olduğunda j değerleri 0, 1, 2 olur; sondaki eleman zaten yerleştiği için karşılaştırma sondan bir önceki konuma kadar sürer.

range(n - i) kullanılırsa ilk turda j değeri son olarak 4 olabilir. Bu durumda dizi[j + 1], yani dizi[5] okunmaya çalışılır. Listenin son geçerli indeksi 4 olduğu için bu erişim IndexError oluşturur.

Yer değiştirme sırasında bir değeri geçici olarak korumak gerekir. Aşağıdaki hatalı kodda ilk değer ezildiği için iki elemanın doğru biçimde değiştirilmesi mümkün olmaz:

dizi[j] = dizi[j + 1]
dizi[j + 1] = dizi[j]

Güvenli yöntem, geçici değişken kullanmaktır:

gecici = dizi[j]
dizi[j] = dizi[j + 1]
dizi[j + 1] = gecici

Python’daki çoklu atama biçimi aynı işlemi daha kısa ve güvenli şekilde yapar: dizi[j], dizi[j + 1] = dizi[j + 1], dizi[j].

Bayraklı Bubble Sort’un karmaşıklığı nasıl değerlendirilir?

Bayraksız Bubble Sort, dizi zaten sıralı olsa bile belirlenen tüm turları ve karşılaştırmaları sürdürür. Bu nedenle en kötü durumda olduğu gibi sıralı bir girişte de çalışma süresi O(n²) olarak değerlendirilir.

Bayraklı sürümde her dış döngü turunun başında swapped değişkeni False yapılır. Komşu iki elemanın yeri değişirse bu değer True olur. İç döngü tamamlandığında değer hâlâ False ise o turda hiçbir değişim yapılmamış demektir ve dizi sıralanmış kabul edilerek dış döngü durdurulur.

Dizi baştan sona sıralıysa ilk turda yalnızca komşu elemanlar karşılaştırılır, hiçbiri yer değiştirmez ve algoritma durur. Bu özel en iyi durumda yaklaşık n - 1 karşılaştırma yapıldığı için bayraklı Bubble Sort O(n) davranır. Dizi ters sıralıysa her turda değişimler devam eder ve bayrak erken durmayı sağlayamaz. Bu yüzden bayrak eklenmiş olsa da en kötü durum çalışma süresi O(n²) olarak kalır.

Burada önemli ayrım, bayrağın her durumu hızlandırmamasıdır. Bayrak, özellikle sıralanmaya yakın veya zaten sıralı dizilerde gereksiz turları atlamayı sağlar. Big O gösteriminin nasıl yorumlandığını ayrıntılı biçimde incelemek için sitedeki Big O yazısına bakabilirsin.

Python’da sort() varken Bubble Sort neden öğrenilir?

Python’un hazır sıralama yöntemleri günlük kod yazımında pratik bir seçenek sunar. list.sort() mevcut listeyi yerinde sıralarken sorted() verilen iterable üzerinden yeni bir sıralı liste oluşturur. Bu iki yöntemin güncel davranışları Python resmî dokümantasyonunda açıklanır.

Bubble Sort’u elle yazmak ise sıralama işleminin arkasındaki adımları görünür hâle getirir. İç içe döngülerin nasıl birlikte çalıştığını, komşu elemanların hangi koşulda karşılaştırıldığını ve her turun sonunda hangi bölümün doğru konuma yerleştiğini doğrudan izleyebilirsin. swapped bayrağı da algoritmanın artık değişiklik yapmadığında neden durabildiğini anlamayı kolaylaştırır.

Bu nedenle Bubble Sort, büyük listeleri sıralamak için kullanılacak hazır bir araçtan çok, algoritma mantığını incelemek için anlaşılır bir çalışma örneğidir. Kendi kodunu kontrol ederken şu listeyi kullanabilirsin:

• Her adımda yan yana duran elemanlar mı karşılaştırılıyor?
• Elemanların yer değiştirmesi yalnızca sol taraftaki değer sağdakinden büyük olduğunda mı gerçekleşiyor?
• İç döngünün sınırı n - i - 1 olarak mı kuruluyor?
• Bir değişim gerçekleştiğinde swapped değeri doğru yerde True yapılıyor mu?
• Çalıştırma sonunda beklenen çıktı [1, 2, 4, 5, 8] oluyor mu?

Sık Sorulan Sorular

Bubble Sort sıralı bir dizide ne zaman O(n) çalışır?

Bubble Sort, swapped bayrağı kullanılan sürümde dizi zaten sıralıysa O(n) çalışır. İlk turda komşu elemanların hiçbiri yer değiştirmediği için algoritma ikinci bir tur başlatmadan durur. Bayraksız sürüm ise karşılaştırmaları sürdürdüğünden bu erken durma davranışına sahip değildir.

Bubble Sort iç döngüsünde neden n-i-1 kullanılır?

n - i - 1 sınırı, hem önceki turlarda doğru konuma taşınan elemanları tekrar kontrol etmemeyi hem de j + 1 indeksinin liste sınırları içinde kalmasını sağlar. Sınır yanlışlıkla daha ileri alınırsa son elemanla olmayan bir sonraki elemana erişilmeye çalışılabilir ve IndexError oluşabilir.

Python’da iki elemanı geçici değişken kullanarak nasıl güvenli biçimde yer değiştirebilirim?

İki elemanı güvenli biçimde değiştirmek için önce sol taraftaki değeri geçici bir değişkende tutup ardından iki atama yapabilirsin.

gecici = sayilar[j]
sayilar[j] = sayilar[j + 1]
sayilar[j + 1] = gecici

Bu yöntem, ilk değerin ikinci atama sırasında kaybolmasını önler ve Bubble Sort içindeki komşu eleman değişimini açıkça gösterir.

Bubble Sort’u adım adım çalıştırıp her turda hangi elemanların yer değiştirdiğini kontrol etmek, iç içe döngüleri ve erken durma mantığını birlikte kavramayı kolaylaştırır.