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(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.

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 = n2 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(n2) değeri bulunur (upper bound olduğu için).

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

Yorumlar

  1. Hasan Erdem Yantır

    Yazınız için çok teşekkürler.
    Siteniz Türk gençleri için (benim gibi) anlaşılması güç, ingilizce ama bilgi dolu kitapların çevirisi gibi. Türkçe kaynak sıkıntısının çözümüne çok büyük bir katkı. Tebrikler...
    Kabarcık Sıralama algoritmasında eğer bir geçiş sırasında herhangi bir yer değiştirme işlemi olmuyorsa, yani if'in içine girilmiyorsa en dıştaki for döngüsünden çıkılabilir. Bu da algoritmaya zaman kazancı sağlar ama yer konusunda biraz sıkıntı doğurur => 8 bitcik:)

  2. kaan

    Teşekkürler konuyu burdaki anlatım sayesinde anladım.Fakat kodlarda bir sıkıntı var galiba bunun demek haddime değil bende de bir hata olabilir ama yinede sormak istedim.256378941 yazınca 213456789 yazıyor.son değiştirmeyi yapmıyor sanırım.

  3. Şadi Evren ŞEKER Article Author

    evet yukarıdaki kodu, mesajınız üzerine tekrar deneyerek çalıştırdım. Haklsınız kodda bir hata bulunuyor. Düzeltmek için koddaki A.length-i ifadesini A.length-1 olarak değiştirmek gerekiyor. Hata, dizideki kontrol edilen elemanların hem baştan hem de sondan azaltılmasıydı. Yazıda da hatayı düzeltiyorum. Ve JAVA dilinde kaynak kodu yazıya ekliyorum.

    Teşekkürler.

  4. Şadi Evren ŞEKER Article Author

    Fikir vermesi açısından kabaca şu şekilde yapabilirsiniz.

    1
    2
    3
    4
    5
    6
    7
    8
    
    node * iter = head;
    while(iter->next != NULL){
      if(iter->next->data > iter->data){
       int temp = iter->next->data;
       iter->next->data = iter->data;
       iter->data = temp;
      }
    }

    Yukarıdaki kodda görüldüğü üzere, bir adet iterator, kendisinden sonraki veriye ve kendi verisine bakarak karşılaştırma yapmaktadır. Şayet kendisinden sonraki veri daha büyükse verileri yer değiştirmektedir (swap). Ben yukarıda basit eşittir ile atama işlemi kullandım ve verinin tipinin int olduğu kabulünü yaptım ancak karmaşık yapılarda bu durum değişebilir.
    Yukarıdaki döngü, kabarcık sıralamasının bir geçişine (pass) tekabül etmektedir. Algoritmayı kodlama şeklinde göre daha fazla geçişler kodlanabilir. En kötü kodlama yöntemi, yukarıdaki döngüyü, eleman sayısı kadar dönen bir döngünün içerisine yerleştirmek olacaktır.

    Başarılar

  5. hakan

    teşekkürler hocam ama ben içindeki sayıların değil kendisinin değiştirilmeli olarak linked listte arıyorum. yardımcı olabilirmisiniz bu konuda acaba ?

  6. Şadi Evren ŞEKER Article Author

    elbette, bağlantılar ile oynayarak kolayca yapabilirsiniz. Yukarıdaki kodu isteğinize göre düzeltelim:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    
    node * iter = head;
    while(iter->next->next != NULL){
      if(iter->next->next->data > iter->next->data){
       node *a = iter->next;
       node *b = iter->next->next;
       // iter-->a-->b  şeklinde bağlı liste
       a->next = b->next;
       b->next = a;
       iter->next = b;
       // iter-->b-->a  şeklinde bağlı listeye dönüşür
      }
    }

    Yukarıdaki kodda, swap işlemli (yer değiştirme) bağlantılar üzerinden (link) yapılmıştır. Ayrıca bu döngü bir geçişin kodudur. İnşaeAllah yardımcı olur.

    Başarılar

  7. ömer yiğit

    Evren bey bilgilerinizden çeşitli platformlar üzerinden yararlanıyoruz teşekkürü borç biliriz emeğinize sağlık..

  8. Fikret

    (Dip not)
    Hakan beyin "if'in içine girilmiyorsa en dıştaki for döngüsünden çıkılabilir" örneğinde performans artırı için yapılmış sanırım,
    fakat burada
    her seferinde:
    2 sayı arasında karşılaştırma yapmak yerine
    sirali = 0 değeri set edilmesi ve sirali değişkeninin true olduğunun kontrol edilmesi gibi bir iş yükü ortaya çıkmış.

    eğer
    (2 sayı arasında karşılaştırma yapmak) > (sirali = 0 ve sirali değişkeninin true olduğunu kontrol edilmesi)

    ise daha verimli diyebiliriz, bunu anlamak için birçok test yapmak gerekir tabiki

  9. AYCAN

    Hocam ben bu bölümde yeniyim derslerde iyi olmama ragmen sinavlarda klasik olunca kavramlari denklestiremiyorum bu bolum uzerinde devam edecegim icin kendimi nasil gelistirebilirim

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


+ 2 = dört