Kabarcık Sıralama - Bubble Sort

     Bu yazımızda kabarcık sıralama (Bubble Sort) algoritmasını inceleyeceğiz.Öncelikle kabarcık sıralama algoritması hakkında bilgi verelim.Adına kabarcık sıralaması denmesinin nedeni büyük olan sayıların aynı suyun altındaki bir kabarcık gibi dizinin üstüne doğru ilerlemesidir.

Algoritmanın çalışma mantığı şu şekildedir.
     Kabarcık sıralaması dizinin başından başlar ve dizi elemanlarını sırayla seçer. Seçilen dizi elemanı kendinden sonra gelen elemandan büyükse bu iki elemanın yerleri değiştirilir. Bu işlem sonucunda dizinin en büyük elemanı dizi sonuna yerleştirildiğinden bir sonraki adımda arama sınırı bir eleman geri çekilir. Bu işlem, dizinin sonundaki elemanın karşılaştırılmasına kadar yinelenerek sürdürülür.

Algoritmanın karmaşıklığı
     Kabarcık sıralama algoritmasının ortalama ve en kötü durumdaki karmaşıklığı {O}(n^2)'dir. Algoritma ortalama ve en kötü durumda (n^2) / 2 adet karşılaştırma ve yer değiştirme gerçekleştirir.

Algoritmanın işleyişi
     İçeriği "5 1 4 2 8" olan bir dizi kabarcık sıralaması ile en küçükten en büyüğe doğru aşağıdaki biçimde sıralanır. Her adımda dizinin kalın olarak işaretlenmiş elemenları karşılaştırılan elemanlardır.

Birinci Geçiş:
( 5 1 4 2 8 ) \to ( 1 5 4 2 8 ) İlk iki elemanı karşılaştırır ve yerlerini değiştirir.
( 1 5 4 2 8 ) \to ( 1 4 5 2 8 )
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ) Elemanlar zaten sıralı olduğu için algoritma yerlerini değiştirmez.
İkinci Geçiş:
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Artık dizi sıralıdır ancak algoritma işlemin bittiğini bilmemektedir. 
Algoritmanın dizinin sıralandığını anlaması için bütün dizinin üzerinden hiçbir değişiklik yapmadan tam bir geçiş yapması gerekir.
Üçüncü Geçiş:
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Sonuç olarak dizi sıralanmıştır ve algoritma sonlanır.

Kabarcık sıralama algoritması java kodları

public static void KabarcikSiralama(int[] dizi) {
  int temp;   // Yer değiştirmede kullanılacak geçici değişken
  
  for (int i = 1; i < dizi.length; i++) {
   for (int j = 0; j < dizi.length - i; j++) {
    
    //Önce gelen elaman bir sonrakinden büyükse ikisi yer değiştiriyor
    if (dizi[j] > dizi[j + 1]) {
     temp = dizi[j];
     dizi[j] = dizi[j + 1];
     dizi[j + 1] = temp;
    }
    
   }
  }
  
 }
  

Kodlara ulaşmak için github adresine gidin