Bubble Sort – Bilgisayar bilimlerinde ve yazılım geliştirmede, verileri belirli bir düzene göre sıralamak en temel ve en çok karşılaşılan problemlerden biridir. İster bir e-ticaret sitesinde ürünleri fiyata göre listeliyor olun, ister bir öğrenci bilgi sisteminde notları küçükten büyüğe diziyor olun, arka planda her zaman bir sıralama algoritması (sorting algorithm) çalışır. Bu algoritmalar arasında öğrenilmesi en kolay, mantığı en basit ve eğitim dünyasında en çok tercih edilen algoritma Bubble Sort, yani Türkçe adıyla Kabarcık Sıralaması‘dır.
Bu kapsamlı rehberde, bir diziyi küçükten büyüğe sıralamak için Bubble Sort algoritmasının nasıl çalıştığını, adım adım mantığını, zaman karmaşıklığını (time complexity), avantajlarını, dezavantajlarını ve farklı programlama dillerindeki kullanımlarını detaylıca inceleyeceğiz.
Bubble Sort (Kabarcık Sıralaması) Nedir?
Bubble Sort, adını suyun altındaki hava kabarcıklarının yüzeye doğru yükselme eğiliminden alır. Bu algoritmada, sıralanmak istenen dizideki (array) en büyük elemanlar, her bir geçişte (pass) dizinin en sonuna doğru tıpkı bir kabarcık gibi “yükselir”.
Algoritma, dizinin başından başlar ve yan yana duran iki elemanı sürekli olarak birbiriyle karşılaştırır. Eğer soldaki eleman sağdaki elemandan büyükse, bu iki elemanın yerini değiştirir (swap işlemi). Bu işlem dizinin sonuna kadar devam eder. İlk turun sonunda, dizideki en büyük eleman kesinlikle dizinin en sonuna yerleşmiş olur. Daha sonra aynı işlem, dizinin geri kalanı için (son eleman hariç tutularak) tekrar edilir. Dizi tamamen sıralanana kadar bu döngü sürer.
Adım Adım Bubble Sort Çalışma Mantığı
Bubble Sort algoritmasının nasıl çalıştığını daha iyi anlamak için somut bir örnek üzerinden gidelim. Elimizde rastgele sayılardan oluşan şu şekilde bir dizi olsun: [7, 3, 9, 2, 5]
Amacımız bu diziyi Bubble Sort kullanarak küçükten büyüğe doğru [2, 3, 5, 7, 9] haline getirmektir.
1. Geçiş (Pass 1)
Algoritma dizinin en başından (solundan) başlar ve yan yana olan elemanları karşılaştırır:
- [7, 3, 9, 2, 5] $\rightarrow$ 7 ve 3’ü karşılaştırır. 7, 3’ten büyük olduğu için yer değiştirirler. Yeni dizi: [3, 7, 9, 2, 5]
- [3, 7, 9, 2, 5] $\rightarrow$ 7 ve 9’u karşılaştırır. 7, 9’dan küçük olduğu için yer değiştirmezler.
- [3, 7, 9, 2, 5] $\rightarrow$ 9 ve 2’yi karşılaştırır. 9, 2’den büyük olduğu için yer değiştirirler. Yeni dizi: [3, 7, 2, 9, 5]
- [3, 7, 2, 9, 5] $\rightarrow$ 9 ve 5’i karşılaştırır. 9, 5’ten büyük olduğu için yer değiştirirler. Yeni dizi: [3, 7, 2, 5, 9]
Birinci geçişin sonucu: Gördüğünüz gibi dizideki en büyük sayı olan 9, su yüzeyine çıkan bir kabarcık gibi dizinin en sonuna yerleşti. Artık 9’un yeri garanti olduğu için sonraki geçişlerde onu kontrol etmemize gerek yok.
2. Geçiş (Pass 2)
Şimdi kalan elemanlar [3, 7, 2, 5] üzerinde aynı işlemi yapıyoruz:
- [3, 7, 2, 5, 9] $\rightarrow$ 3 ve 7’yi karşılaştırır. Yer değişimi olmaz.
- [3, 7, 2, 5, 9] $\rightarrow$ 7 ve 2’yi karşılaştırır. 7, 2’den büyük olduğu için yer değiştirirler. Yeni dizi: [3, 2, 7, 5, 9]
- [3, 2, 7, 5, 9] $\rightarrow$ 7 ve 5’i karşılaştırır. 7, 5’ten büyük olduğu için yer değiştirirler. Yeni dizi: [3, 2, 5, 7, 9]
İkinci geçişin sonucu: Kalanlar arasındaki en büyük sayı olan 7, sondan bir önceki sıraya yerleşti.
3. Geçiş (Pass 3)
Kalan elemanlar: [3, 2, 5]
- [3, 2, 5, 7, 9] $\rightarrow$ 3 ve 2’yi karşılaştırır. 3 büyük olduğu için yer değişirler. Yeni dizi: [2, 3, 5, 7, 9]
- [2, 3, 5, 7, 9] $\rightarrow$ 3 ve 5’i karşılaştırır. Yer değişimi olmaz.
4. Geçiş (Pass 4)
- [2, 3, 5, 7, 9] $\rightarrow$ 2 ve 3’ü karşılaştırır. Yer değişimi olmaz.
Algoritma tamamlandı. Dizi artık tamamen küçükten büyüğe sıralanmış durumdadır!
Bubble Sort Performansı ve Karmaşıklık Analizi (Complexity)
Sıralama algoritmalarını değerlendirirken en çok dikkat edilen metrikler zaman karmaşıklığı (Time Complexity) ve alan karmaşıklığıdır (Space Complexity).
Zaman Karmaşıklığı (Time Complexity)
- En Kötü Durum (Worst Case): $O(n^2)$Dizinin büyükten küçüğe ters sıralı olduğu durumdur. Her eleman için dizinin tamamının taranması ve sürekli yer değiştirme yapılması gerekir.
- Ortalama Durum (Average Case): $O(n^2)$Elemanların rastgele dağıldığı durumdur. İç içe iki döngü kullanıldığı için performans yine dizinin eleman sayısının karesiyle doğru orantılıdır.
- En İyi Durum (Best Case): $O(n)$Dizinin zaten küçükten büyüğe sıralı olduğu durumdur. “Optimize Edilmiş Bubble Sort” kullanıldığında, algoritma diziyi sadece bir kez tarar, hiçbir yer değiştirme yapılmadığını görür ve işlemi anında sonlandırır.
Alan Karmaşıklığı (Space Complexity)
- Alan Karmaşıklığı: $O(1)$Bubble Sort “yerinde” (in-place) bir sıralama algoritmasıdır. Sıralama işlemini gerçekleştirmek için dizinin kendisi haricinde ek bir bellek alanına (yeni bir diziye) ihtiyaç duymaz. Geçici bir değişken (temp) kullanılarak yer değiştirme işlemi yapılır. Bu bellek dostu olması açısından avantajlıdır.
Optimize Edilmiş Bubble Sort (Optimizasyon)
Standart Bubble Sort, dizi zaten sıralanmış olsa bile gereksiz yere karşılaştırma yapmaya devam eder. Bunu önlemek için koda bir “bayrak” (flag) ekleyebiliriz. Eğer bir tam tur boyunca dizide hiçbir eleman yer değiştirmediyse (swap işlemi olmadıysa), dizinin tamamen sıralandığını anlarız ve döngüyü erken kırarak işlemi bitiririz. Bu küçük hamle, performansı ciddi anlamda artırır.
Farklı Programlama Dillerinde Kod Örnekleri
Blog yazımızı teknik bir temele oturtmak adına, bu algoritmanın nasıl koda döküldüğünü popüler programlama dilleri üzerinden inceleyelim.
Python ile Bubble Sort
Python’un okunabilirliği sayesinde Bubble Sort mantığını anlamak çok kolaydır:
Python
def bubble_sort(dizi):
n = len(dizi)
# Dizinin her bir elemanı için döngü
for i in range(n):
swapped = False # Optimizasyon için bayrak
# Son i eleman zaten yerinde olduğu için n-i-1'e kadar gidiyoruz
for j in range(0, n-i-1):
if dizi[j] > dizi[j+1]:
# Yer değiştirme işlemi (Swap)
dizi[j], dizi[j+1] = dizi[j+1], dizi[j]
swapped = True
# Eğer bu turda hiç yer değişimi olmadıysa dizi sıralıdır, döngüyü bitir.
if not swapped:
break
return dizi
ornek_dizi = [64, 34, 25, 12, 22, 11, 90]
print("Sıralı Dizi:", bubble_sort(ornek_dizi))
JavaScript ile Bubble Sort
Web geliştiriciler için JavaScript’te kullanımı ise şöyledir:
JavaScript
function bubbleSort(dizi) {
let n = dizi.length;
let swapped;
do {
swapped = false;
for (let i = 0; i < n - 1; i++) {
if (dizi[i] > dizi[i + 1]) {
// Değişkenleri takas et
let temp = dizi[i];
dizi[i] = dizi[i + 1];
dizi[i + 1] = temp;
swapped = true;
}
}
n--; // Her geçişte en büyük eleman sona yerleştiği için kontrol alanını daralt
} while (swapped);
return dizi;
}
let sayilar = [5, 1, 4, 2, 8];
console.log("Sıralanmış hali:", bubbleSort(sayilar));
Bubble Sort Neden Kullanılır? (Avantajları ve Dezavantajları)
Avantajları:
- Öğrenmesi Çok Kolaydır: Yazılıma yeni başlayan öğrencilere algoritma mantığını, iç içe döngüleri (nested loops) ve karar yapılarını anlatmak için mükemmel bir araçtır.
- Ek Bellek Gerektirmez: $O(1)$ alan karmaşıklığı ile hafızayı yormaz.
- Kısa Kodludur: Sadece birkaç satırlık bir kod ile kolayca implemente edilebilir.
Dezavantajları:
- Düşük Performans: $O(n^2)$ zaman karmaşıklığı nedeniyle büyük veri setlerinde inanılmaz derecede yavaş çalışır. Örneğin, 100.000 elemanlı bir diziyi sıralamak dakikalar alabilir. (Bunun yerine genellikle Quick Sort veya Merge Sort tercih edilir.)
- Gerçek Hayat Projelerinde Yetersizdir: Günümüzdeki modern yazılım dillerinin kütüphanelerinde bulunan gömülü
sort()fonksiyonları (örneğin Python’daki Timsort), Bubble Sort’tan çok daha karmaşık ve kat kat daha hızlı algoritmalar kullanır.
Sonuç
Özetlemek gerekirse, diziyi küçükten büyüğe sıralama konusunda Bubble Sort algoritması harika bir giriş noktasıdır. Büyük verilerde hantal kalmasına rağmen, temel programlama mantığının oturması ve algoritmik düşünce becerisinin gelişmesi için her yazılımcının mutlaka bilmesi gereken bir konudur. Optimizasyon teknikleriyle algoritmanın en iyi durumdaki performansını $O(n)$ seviyesine çekmek de kodlama yeteneğinize büyük bir katkı sağlayacaktır.
Konuyla ilgili daha derin ve akademik bir okuma yapmak isterseniz algoritmanın evrensel standartlarını inceleyebileceğiniz kaynaklara göz atabilirsiniz:
incelemek için tıklayın: Wikipedia Bubble Sort (İngilizce)
Daha fazla bilgiye ulaşmak için sitemizi ziyaret etmeyi unutmayın !
Java Fibonacci Hesaplamayı öğrenmek için tıklayın !
