Kabarcık Sıralaması (Baloncuk sıralaması, Bubble Sort) - Java Örneği

Kabarcık Sıralaması, bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır. Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır.

Sıralanmak istenen verimiz:

5,7,2,9,6,1,3

olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Kabarcık sıralama algoritmasının çalışması adım adım gösterilmiştir:

1. adım : 5,2,7,6,1,3,9

2. adım: 2,5,6,1,3,7,9

3. adım: 2,5,1,3,6,7,9

4. adım: 2,1,3,5,6,7,9

5. adım:1,2,3,5,6,7,9

6. adım:1,2,3,5,6,7,9

Yukarıda her adımda yapılan işlemi gösteren baloncuk sıralamasında algoritmanın çalışması aşağıdaki şekilde anlatılabilir:

1. ilk iki sayıyı al

2. aldığın iki sayıyı karşılaştır

3. küçük olanı yaz diğerini aklında tut

4. dizinin sonuna geldiysen aklındaki sayıyı diziye yazarak bitir

5. dizinin sonu değilse yeni bir sayı al.

6. 2. adıma geri git.

Yukarıdaki algoritma kabarcık sıralamasının bir geçişini (pass) göstermektedir. Bu geçişin dizide bulunan eleman sayısının bir küçüğü kadar tekrar etmesi durumunda dizi sıralı olur.

Ancak bazı durumlarda dizinin sıralanması yukarıda geçen sayı (n elemanlı bir dizi için n geçiş) kadar tekrarı gerektirmez. Bu durum sadece dizi tersten sıralıysa gerekir. Ayrıca dizi zaten sıralı ise ilk geçişten sonra sıralamanın durmasını bekleriz.

Bir diğer iyileştirme ise yukarıdaki örneğe dikkatle bakıldığında fark edilebilir. Kabarcık sıralamasında dizi üzerindeki her geçişten sonra dizinin en büyük elemanı dizinin sonuna atılmaktadır. Örneğin ilk geçişten sonra en büyük eleman, 2. geçişten sonra en büyük iki eleman 20. geçişten sonra en büyük 20 eleman gibi dizinin sonunda yerleşmekte ve bir daha hiç değişmemektedir. bu durumda örneğin 20. geçişte son 20 elemana bakmanın bir anlamı yoktur. Bu iyileştirme (optmisation) ile de hız kazanmak mümkündür.

Yukarıda anlatılan algoritmanın java dilinde ve c dilinde kodları aşağıda verilmiştir.

JAVA dilindeki karşılığı:

  public void bubblesort(int [] A) // bir diziyi parametre alan fonksiyon
  {

     int tmp;

    for(int i=0; i<A.length; i++)
    {
  //    for(int j=1; j<A.length-i+1; j++) şeklinde de döngü yazılabilir
        for(int j=A.length-1 ; j>i;j--) //i'ye kadar olan kısmı sabitlendiği için tekrar geçişlerde kontrolü gerekmemektedir.
      {
        if(A[j-1]>A[j])
        {
          tmp=A[j-1];
          A[j-1]=A[j];
          A[j]=tmp;
        }
      }
    }
  }

Algoritmanın karmaşıklığına bakıldığında her geçişin bütün elemanlardan en az bir kere geçmesi gerektiği görülür. bu durumda her geçiş n kadar işlem gerektirmekte toplam n-1 geçiş gerektiği için de n x (n-1) geçiş gerektirir. Sonuçta O(n2) zaman karmaşıklığına sahiptir. Hafızadaki ihtiyacına bakıldığında ise mevcut veri kadar yer tutması yeterlidir. Bu durumda hafıza karmaşıklığı O(n) olarak hesaplanabilir.