1. BUBBLE SORT
Dizi elemanlarını sıralarken sanki eleman diğerlerinin üzerinden bir baloncuk gibi kayıyor gibi düşünüldüğünden bu isim verilmiştir. Bubble sortun mantığı dizinin üzerinde gezerek her seferinde elemanları ikili ikili sıralar. Her bir iterasyonda en büyük elemanı en sona taşır. Dolayısıyla n kez iterasyon yapması gerekmektedir.
5,7,2,9,6,1,3
DİZİNİN ÜZERİNDEN İLK GEÇİŞTE
ilk iki elemana bakar 5 ? 7 . Sıkıntı yok devam
5,7,2,9,6,1,3
bir kayar ve diğer iki elemana bakar 7 ? 2 . Gerekli yer değiştirmeyi yapar.
5,2,7,9,6,1,3
bir kayar ve diğer iki elemana bakar 7 ? 9 . Sıkıntı yok devam.
5,2,7,9,6,1,3
bir kayar ve diğer iki elemana bakar 9 ?6 . Gerekli yer değiştirmeyi yapar.
5,2,7,6,9,1,3
bir kayar ve diğer iki elemana bakar 9?1 . Gerekli yer değiştirmeyi yapar.
5,2,7,6,1,9,3
bir kayar ve diğer iki elemana bakar 9?3 . Gerekli yer değiştirmeyi yapar.
5,2,7,6,1,3,9
- Bu işlemi n kadar tekrar ettiğinde yani aslında bir azalarak tekrar ettiğinde diziyi sıralamış oluyor. Bir azalarak dememizin sebebi her seferinde en büyük elemanı sona atıyor.
2. ALGORITMA ANALIZI
COMPLEXITY n^2
worst case : n , n-1 , n-2 .. n*(n+1)/2 : n^2 lik karmaşıklık.
best case : sıralı dizi. Hiç bir elemanın yerini değiştirmiyorsak dizi sıralı verilmiştir. Sıralımı kontrol yap bir kere geçip sıralı olduğunu farkederse n
Kıyaslama : insertion ve selection ile karmaşıklığı aynı çok büyük bir üstünlük sağlamaz.
iyileştirme : her geçişte son harici son 2 haricine bakmak gibi
3. BUBBLE SORT C# IMPLEMENTASYONU
public static void bubble_sort(List<double> dizi) { for (int i = 0; i < dizi.Count - 1; i++) { for (int j = 1; j < dizi.Count - i; j++) { if (dizi[j] < dizi[j - 1]) { double gecici = dizi[j - 1]; dizi[j - 1] = dizi[j]; dizi[j] = gecici; } } } }