Bilgisayar bilimleri ve yazılım mühendisliğinde sıralama algoritmaları, veri yapılarının temel taşıdır. Karışık olarak verilmiş bir sayı veya metin listesini küçükten büyüğe (artan) ya da büyükten küçüğe (azalan) düzenlemek, arama algoritmalarının verimli çalışabilmesi için zorunlu bir ön adımdır. Sıralama algoritmaları dünyasına adım atan her öğrencinin ilk karşılaştığı ve çalışma mantığını en kolay görselleştirebildiği algoritma şüphesiz Bubble Sort (Kabarcık Sıralaması) algoritmasıdır. Bu kapsamlı rehberde, Bubble Sort'un bilimsel teorisinden zaman karmaşıklığına, adım adım dizi simülasyonundan C++ ve Python uygulamalarına kadar tüm inceliklerini keşfedeceksiniz.
1. Algoritmanın Amacı ve Günlük Hayat Analojisi
Bubble Sort algoritmasının adı, bir gazoz bardağındaki veya kaynayan sudaki hafif gaz kabarcıklarının yüzeye doğru yükselmesi metaforundan gelir. Dizideki büyük elemanlar, her geçişte komşusuyla karşılaştırılarak tıpkı bir kabarcık gibi listenin sonuna doğru adım adım "yükselir".
Temel Prensip:
Dizinin başından başlanır. Yan yana duran iki eleman karşılaştırılır:
2. Matematiksel Çalışma Prensibi ve Zaman Karmaşıklığı (Big-O Analizi)
Bir algoritmanın verimliliği, girdi boyutu olan $n$ sayısı arttıkça harcadığı işlemci zamanı (zaman karmaşıklığı) ve bellek miktarı (alan karmaşıklığı) ile ölçülür.
Big-O Performans Tablosu:
| Senaryo | Zaman Karmaşıklığı | Açıklama |
|---|---|---|
| En İyi Durum (Best Case) | $O(n)$ | Dizi zaten tam sıralıysa, tek bir kontrolde durur (Optimize edilmiş versiyonda). |
| Ortalama Durum (Average Case) | $O(n^2)$ | Elemanlar rastgele dağılmışsa iç içe iki döngü çalışır. |
| En Kötü Durum (Worst Case) | $O(n^2)$ | Dizi tamamen tersten sıralıysa maksimum sayıda swap işlemi yapılır. |
| Alan Karmaşıklığı (Space) | $O(1)$ | Ekstra bellek gerektirmez, sıralamayı mevcut dizinin üzerinde (In-place) yapar. |
Toplam karşılaştırma sayısı matematiksel olarak ardışık sayıların toplamı formülüyle hesaplanır:
$$\sum_{i=1}^{n-1} i = rac{n(n-1)}{2} = rac{n^2 - n}{2} pprox O(n^2)$$
Bu durum, Bubble Sort'un 1.000 elemanlık bir dizide yaklaşık 500.000 işlem yapacağı, ancak 1.000.000 elemanlık devasa veritabanlarında işlemcinin kilitlenmesine neden olacağı anlamına gelir. Bu yüzden büyük verilerde Quick Sort veya Merge Sort tercih edilirken, eğitimde mantığı kavramak için Bubble Sort rakipsizdir.
3. Adım Adım Dizi Simülasyonu
Algoritmanın iç mekanizmasını kavramak için şu 5 elemanlı karışık diziyi ele alalım: `[5, 1, 4, 2, 8]`
1. Geçiş (Pass 1):
*Sonuç:* En büyük sayı olan 8, dizinin en sonuna başarıyla yerleşti.
2. Geçiş (Pass 2):
*Sonuç:* İkinci büyük sayı olan 5, doğru yerine ulaştı.
3. Geçiş (Pass 3):
4. Algoritma Akış Şeması ve Mantıksal Adımları
Bir programcı olarak kodu yazmadan önce algoritmanın mantıksal akış şemasını zihnimizde kurmalıyız:
[BAŞLA] │ ▼
[Diziyi Oku (n Eleman)] │ ▼
[Dış Döngü: i = 0'dan n-1'e kadar] │ ▼
[takas_oldu = False] │ ▼
[İç Döngü: j = 0'dan n-i-1'e kadar] │ ├── [Dizi[j] > Dizi[j+1] mi?] ── EVET ──> [Swap(Dizi[j], Dizi[j+1])] ──> [takas_oldu = True] │ │ └── HAYIR ─────────────────────────────────────┘ │ ▼
[İç Döngü Bitti mi?] │ ├── HAYIR ──> [Sonraki j'ye geç] │ └── EVET ──> [takas_oldu == False mi?] ── EVET ──> [Döngüyü Kır (Break)] ──> [Sıralı Diziyi Yazdır] ──> [BİTİR] │ └── HAYIR ──> [Sonraki i'ye geç]5. Tam ve Çalışan Kodlar
Python ile Optimize Edilmiş Bubble Sort Uygulaması:
def bubble_sort(arr): n = len(arr) # Dış döngü: Her adımda en büyük eleman sona oturur for i in range(n): swapped = False # Son i eleman zaten sıralandığı için (n - i - 1) kadar bakılır for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: # Python'da pratik takas işlemi arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True # Eğer iç döngüde hiçbir takas olmadıysa dizi sıralıdır, çık! if not swapped: break return arr # Test Verisi
sayilar = [64, 34, 25, 12, 22, 11, 90]
print("Orijinal Dizi :", sayilar)
sirali = bubble_sort(sayilar)
print("Sıralı Dizi :", sirali)C++ ile Bubble Sort Uygulaması:
#include <iostream>
#include <vector> void bubbleSort(std::vector<int>& arr) { int n = arr.size(); bool swapped; for (int i = 0; i < n - 1; ++i) { swapped = false; for (int j = 0; j < n - i - 1; ++j) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) break; // Erken çıkış optimizasyonu }
} int main() { std::vector<int> data = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(data); std::cout << "Siralanmis C++ Dizisi: "; for (int x : data) std::cout << x << " "; std::cout << std::endl; return 0;
}6. Bubble Sort'un Güçlü ve Zayıf Yönleri
Avantajları:
Dezavantajları:
7. Kendini Geliştirme Görevi (Challenge): Kokteyl Sıralaması
Görev: Bubble Sort yalnızca soldan sağa doğru çalışır. Peki her geçişte bir kez soldan sağa, hemen ardından sağdan sola doğru çift yönlü tarama yaparsa ne olur? Bu algoritmaya Cocktail Shaker Sort (Kokteyl Sıralaması) denir. Yukarıdaki Python kodunu güncelleyerek çift yönlü çalışan bir kokteyl sıralayıcı yazmayı deneyin!
Sonuç
Bubble Sort, bilgisayar bilimleri tarihinin en klasik ve öğretici algoritmalarından biridir. Modern yüksek performanslı yazılımlarda yerini daha gelişmiş algoritmalara bıraksa da, sıralama mantığını, iç içe döngüleri ve optimizasyon kavramını öğrenmek için vazgeçilmez bir başlangıç noktasıdır. Sitemizdeki diğer [Algoritma Dersleri](/dersler) ve [Projeler](/projeler) ile kendinizi geliştirmeye devam edebilirsiniz!