Kabarcık Sıralaması (Baloncuk sıralaması, Bubble Sort)

Yazan : Şadi Evren ŞEKER

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe ardışık duran iki hafıza bloğunun birbirine nispetle sıralanması ve bu işlemin sürekli tekrarlanması sayesinde sıralar. Ardışık iki hafıza bloğuna bakmasından dolayı baloncuk ismini almıştır. Çünkü bu bakma işlemi bir baloncuğun (buble) hareket etmesi gibi sayıların üzerinde hareket etmektedir.

[flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/video/bubblesort.flv /]

Aşağıda bir örnek verilmiştir:

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(n²) 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.

Kabarcık Sıralamasında İyileştirmeler (Hasan Bey’in yorumu üzerine ekliyorum)

Kabarcık sıralaması yukarıdaki şekilde yazılabileceği gibi iki önemli iyileştirme (optimization) yapılabilir. Bunlardan birincisi, Hasan Bey’in de belirttiği üzere zaten sıralı bir dizinin daha fazla sıralanması içn döngünün dönmemesidir.

Örneğin yukarıdaki kodu ele alırsak ve zaten sıralı bir diziyi döngüye verirsek, döngü zaten sıralı dizi için, dizinin boyutu kadar dönecektir. Bunun yerine dizinin sıralandıktan sonra dönmesini engelleyebiliriz.

Peki dizinin sıralandığını nereden anlayacağız?

Dizi şayet sıralıysa elemanların yer değiştirmesini gerektiren if koşuluna hiç girilmez. Bu durumda kodumuzda bulunan if’e hiç girmiyorsak dizi sıralıdır ve daha fazla döngünün dönmesine gerek yoktur.

Kodu aşağıdaki şekilde iyileştirelim:

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

    for(int i=0; i<A.length; i++)
    {
    int sirali=1;
      for(int j=A.length-1 ; j>0;j--)
      {
        if(A[j-1]>A[j]) //şayet buraya girmiyorsak dizi sıralı demektir
        {
          sirali=0;  //şayet giriyorsak sıralı değil demektir
          tmp=A[j-1];
          A[j-1]=A[j];
          A[j]=tmp;
        }
      }
      if(sirali)//şayet dizinin üstünden geçtiğimiz halde
                //hiç bir değer yer değiştirmiyorsa
                // dizi sıralıdır döngüden çıkılabilir
         break;
    }
  }

Yukarıdaki iyileştirmenin yanında ilave bir iyileştirme daha yapabiliriz. Bu ise dizideki sabit değerlerdir.

Yukarıdaki döngü dikkat edilirse n boyutundaki bir dizi için n x n = n² kere döner.  Aslında buna gerek yoktur. Sebebi dizinin her geçişinden sonra (pass) belirli değerlerin sabit şekilde sona atılması ve bu değerlerin üzerinden tekrar geçilmesine gerek olmamasıdır.

Bu durumu örnek bir sıralama üzerinden anlamaya çalışalım. Sıralamak istediğimiz dizi aşağıdaki şekilde olsun:

4,5,2,9,6,1,8,7

Şimdi kabarcık sıralaması algoritması gereği dizinin üzerinden bir kere geçelim:

4,2,5,6,1,8,7,9

ilk geçişten sonra görüleceği üzeren en büyük sayı en sona atılmıştır. Sıralamaya devam edelim ve bir geçiş daha yapalım:

2,4,5,1,6,7,8,9

ikinci geçişten sonra sondaki iki sayı her zaman ve her durum için dizideki en büyük iki sayıdır.

Bu gerçeği farkettikten sonra artık diyebiliriz ki her geçişte bütün diziye bakılmasına gerek yoktur. Çünkü dizinin sonundaki elemanlar zaten yer değiştirmeyecektir.

Bu durumda dizinin üzerinden geçen içteki döngümüzü dizi boyutunda değil, dizi boyutundan eleman sayısı noksan değere kadar sıralamalıdır. Sebebi örneğin 3. geçişte sondaki 3 elemana bakılmasına gerek olmamasıdır.

Kodumuzu yeniden düzenleyelim:

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

    for(int i=0; i<A.length; i++)
    {
    int sirali=1;
      for(int j=A.length-1 ; j>i;j--)  //i. geçiş için i eksik dönüş
      {
        if(A[j-1]>A[j]) //şayet buraya girmiyorsak dizi sıralı demektir
        {
          sirali=0;  //şayet giriyorsak sıralı değil demektir
          tmp=A[j-1];
          A[j-1]=A[j];
          A[j]=tmp;
        }
      }
      if(sirali)//şayet dizinin üstünden geçtiğimiz halde
                //hiç bir değer yer değiştirmiyorsa
                // dizi sıralıdır döngüden çıkılabilir
         break;
    }
  }

Yukarıdaki yeni kodda, içteki döngü dikkat edilirse dıştaki döngü değişkeni kadar eksik dönmektedir. Dolayısıyla 0. geçişte 0, 1. geçişte 1 ve n. geçişte n eleman eksik dönecektir. Çünkü n. geçişte sondaki n eleman zaten sıralı olacak ve kontrol edilmesine gerek olmayacaktır.

Bu durumda kabarcık sıralamamızın algoritma performansını tekrar analiz edecek olursak

En iyi durumda (best case analysis) : n olur çünkü bütün dizi zaten sıralıysa dizideki her elemana birer kere bakarak döngü kırılır ve bir daha dizinin üzerinden geçilmez.

En kötü durumda (worst case analysis): n2 olur. Sebebini şu şekilde açıklayalım. Her geçişte geçiş sayısı kadar elemana bakılması gerekir. Örneğin eleman sayısı n olan bir dizi için k. geçişte n-k elemana bakılır. Dolayısıyla 0. geçişkte n elemana 1. geçişte n-1 elemana son geçişte ise n-n yani 0 elemana bakılır. Bu durumda toplam sayı 1’den n’ya kadar olan sayılrın toplamıdır ve

n x (n+1) / 2

elemana bakılması gerekir. Bu durumda O(n²) değeri bulunur (upper bound olduğu için).

Kodun çalışan halini JAVA dilinde indirmek için tıklayınız.