Home / Algoritmalar / Bubble Sort (Kabarcık Sıralama) – Örnekli Anlatım – C Kodu

Bubble Sort (Kabarcık Sıralama) – Örnekli Anlatım – C Kodu

Sıralama algoritmaları temelde verilen sayıları (ya da genel anlamda verileri) sıralamaya yarayan algoritmalardır. Büyükten küçüğe ya da küçükten büyüğe olması durumu değiştirmez. Ancak sıralama algoritmaları anlatılırken genelde sıralama küçükten büyüğü yapılmaktadır. Genel olarak kullanılan sıralama algoritmaları şu şekildedir.

Sıralama Algoritmaları Nelerdir?

  • Bubble Sort (Kabarcık sıralama)
  • Selection Sort (Seçmeli Sıralama)
  • Insertion Sort (Araya sokarak sıralama)
  • Merge Sort (Birleştirme Sıralaması)
  • Quick Sort (Hızlı Sıralama

Bunlar dışında daha pek çok sıralama algoritması mevcuttur. Ancak en temel sıralama algoritmaları bunlar olduğu için sizlere bunları anlatacağız.

Bubble Sort Algoritması Nedir?

Bubble sort algoritmasının türkçesi kabarcık sıralama algoritmasıdır. Kabarcık denmesinin en önemli sebebi bu algoritmada en büyük sayının en sona atılmasıdır. Tüm mantığını bunun üzerinedir. Her iterasyonda en büyük sayı sona atılır ve iterasyonlar tamamlandığında sıralama gerçekleşmiş olur.

Bubble Sort Algoritması Sözde (Pseudo) Kod

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort


Yukarıdaki sözde kodu adım adım anlatalım. (Not: Bu kod çalıştırılabilir kod değildir, yalnızca algoritmanın mantığını göstermek içindir)

begin BubbleSort(list) => Burası fonksiyon kısmı. begin fonksiyonun başlangıcı. BubbleSort fonksiyonun ismi. Parantez içerisindeki list ise sayılarımızı barındıran dizimiz.

for all elements of list => for döngümüzün listenin tüm elemanları için döneceğini kast eder. (esasında iç içe iki for döngüsü olacak, esas kodu altta bulabilirsiniz)

if list[i] > list[i+1] => Eğer i. eleman i+1. elemandan büyükse alttaki satır çalışacaktır.

swap(list[i], list[i+1]) => swap yer değiştirme demektir. Yani i. sayi, i+1. sayıdan büyükse yer değiştir anlamındadır.

end if => if statement’ını bitir.

end for => for döngüsünü bitir.

return list => sıralanmış listeyi kullanıcıya geri döndür.

end BubbleSort => fonksiyonu bitir.

Swap Ne Demektir?

Yazılımda Swap demek iki değişkenin yer değiştirmesi demektir. Bu işlem için ek bir değişkene ihtiyaç duyulur. x = 5, y = 10 olsun. Biz istiyoruz ki x = 10, y = 5 olsun. İşte bunu yapmak için en bir değişken oluştururuz.

int z;

z = x;

x = y;

y = z;

Yukarıdaki işlem tipik bir yer değiştirme işlemidir. x değerine y’yi atayınca x’in eski değeri kaybolur. Bu yüzden biz z diye bir değişken oluşturup ilk başka x değerini orada sakladık, en son olarak da y’ye atadık.

Bubble Sort Algoritması Genel Çalışma Mantığı

Bubble Sort Algoritması her adımda iki sayıyı karşılaştırır. yani i. eleman ile i+1. elemana bakar. Eğer ilk eleman ikinci elemandan büyükse yer değiştirme yapılır. Bunun sebebi algoritmanın prensibi gereğidir. Zira bu algoritmadaki temel prensip en büyük sayının en sona atılmasıdır. Her iterasyonda en büyük sayısı sona gelir, iterasyonlar tamamlandığında algoritma tamamlanmış olur.

Bubble Sort Algoritması Örnek

Şimdi bir örnek yapalım ve algoritmayı bunun üzerinde uygulayalım.

sayılarımız; 2, 0 , 11, 1, 7, 9, 5 olsun.

1. İterasyon

i sıfırdan başlar, her adımda bir artırılır.

Birinci Adım: 0 eleman  ile 1. eleman karşılaştırılır. (2, 0) => 2 0’dan büyük olduğu için swap yapılır. 0, 2 , 11, 1, 7, 9, 5

İkinci Adım: 1. eleman ile 2. eleman karşılaştırılır.(2, 11) => 2 sayısı 11’den küçük olduğu için yer değiştirme yapılmaz. aynen kalır. 0, 2 , 11, 1, 7, 9, 5

Üçüncü Adım: 2. eleman 3. eleman karşılaştırılır. (11, 1) => 11 sayısı 1’den büyük olduğu için swap yapılır.  0, 2 , 1, 11, 7, 9, 5

Dördüncü Adım: 3. eleman ile 4. eleman karşılaştırılır. (11, 7) => 11 sayısı 7’den büyük olduğu için yer değiştirilir.  0, 2 , 1, 7, 11, 9, 5

Beşinci Adım: 4. eleman ile 5. eleman karşılaştırılır (11, 9) => 11 sayısı 9’dan büyük olduğu için yer değiştirme yapılır.  0, 2 , 1, 7, 9, 11, 5

Altıncı Adım: 5. eleman ile 6. eleman karşılaştırılır. (11, 5) => 11 sayısı 5’ten büyük olduğu için yer değiştirme yapılır. 0, 2 , 1, 7, 9, 5, 11

dikkat ettiyseniz ilk iterasyon sonucunda dizinin en büyük sayısı en son eleman oldu. diğer iterasyonları tek tek yazmıycam. Dizide n tane eleman varsa n – 1 tane iterasyon olur. Her iterasyonda adım sayısı bir azalır. Sebebi bir önceki adımda zaten en büyük sayının doğru konuma yerleşmiş olmasıdır.

İterasyonları dış döngü, adımları ise iç döngü olarak düşünebilirsiniz.

Bubble Sort C Kodu


#include <stdio.h>
//dizinin boyutu için SIZE 
#define SIZE 10000

//toplam 10000 sayı tutacak bir dizi oluşturduk.
int myArray[SIZE - 1];

//Kabarcık sıralama fonksiyonumuz, parametre olarak dizimizi gönderiyoruz.
void bubbleSort(int x[])
{
    int i, j;

    //iterasyonların olduğu dış döngü
    for(i = 1; i < SIZE; i++)
    {
        //Her iterasyonda elemanları karşılaştıracak olan iç döngü
        for( j = 0; j < SIZE - 1; j++)
        {
            //iki eleman arasında karşılaştırma yapıyor eğer soldaki (i) sağdaki sayıdan (i+1)'den büyükse swap yapılacak'
            if(myArray[j] > myArray[j+1])
                //swap fonksiyonunu çağırıyoruz.
                swapf(j, j+1);
        }
    }
}

//dizimizin elemanlarını ekrana basan fonksiyon
void printSorted()
{
    int i;
    for( i = 0; i < SIZE - 1; i++)
    {
        printf("%d\n", myArray[i]);
    }
}

//swap yani yer değiştirme fonksiyonumuz.
//Bu fonksiyon direkt global değişken olan dizimiz üzerinde işlem yapıyor, ondan void
void swapf(int x, int y)
{
    int temp;
    temp = myArray[x];
    myArray[x] = myArray[y];
    myArray[y] = temp;

}

//Programı çalıştıracağımızda random olarak 10.000 adet sayı üretip dizimize atan muhteşem fonksiyonumuz.
void init()
{
    int i;
    for( i = 0; i < SIZE - 1; i++)
    {
        myArray[i] = rand()%10000;
    }
}

//ilgili fonksiyonları çağırdığımız main fonksiyonu
int main()
{
    init();
    bubbleSort(myArray);
    printSorted();
    return 0;
}

 

Bubble Sort Algoritma Analizi (Best Case – Worst Case – Avarage Case) En iyi Durum – En Kötü Durum

 

Bubble Sort En Kötü Durum (Worst Case) Performansı O(n²) şeklindedir. Neden? Çünkü Big O Notasyonu yazımızdan hatırlarsanız iç içe döngülerde algoritma karmaşıklığı hesaplarken döngülerin çarpımını alıyorduk. n * (n – 1) çarpımı üzerinden bize yine O(n²) performansı gelir. En kötü durumda döngünün tüm adımları gerçekleşecektir.

Bubble Sort Ortalama Durum (Avarage Case) Performansı. Bubble Sort optimal bir algoritma değildir. ortalama durumda da O(n²) performansı alınmaktadır.

Bubble Sort En iyi Durum (Best Case) Performansı. O(n) şeklindedir. Ancak yukarıda paylaştığımız kodda en iyi durumu elde edemezsiniz. İyileştirilmiş bubble sort algoritması üzerinde bu durum gerçekleşir. Hemen aşağıda bulunmakta.

Bubble Sort İyileştirilmiş C Kodu

Bubble Sort Algoritması iç içe iki döngüye sahiptir. Bu yüzden neredeyse tüm durumlarda O(n²)’ye gider. Ancak özel bir durum için algoritma üzerinde iyileştirme yapılabilir. Bu da tüm dizi zaten sıralı ise dış döngünün dönmesini engellemektir. Bunu nasıl yaparız? Basit bir flag değişkeni oluşturarak gerçekleştirebiliriz.


 void bubbleSort(int *arr, int n)
{
    for(int i=0; i<n; i++)
    {  
      bool flag = false;
       for(int j=0; j<n-i-1; j++) { if(array[j]>array[j+1])
          {
            flag = true;
             int temp = array[j+1];
             array[j+1] = array[j];
             array[j] = temp;
          }
       }
      // Eğer hiç swap gerçekleşmemişse dizi sıralı demek, dış döngüye gerek kalmadan return ederiz.
      if(!flag){ 
         return; 
      } 
   }
}

 

2 comments

  1. Swap fonksiyonu ile ilgili bir sorun mu var derlenmiyor dev c++ de

Bir cevap yazın

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