Sorting Algoritmaları #1 – Bubble Sort (Kabarcık/Baloncuk Sıralaması)

Okuma süresi: 3 dakika

Algoritmalar bölümünün açılışını anlaşılması ve kodlaması kolay/zevkli olan Bubble Sort ile yapmak istedim. Halk arasında(bu kavramı sadece tıp alanında çalışanların tekeline bırakamamakta kararlıyım 🙂 ) Kabarcık/Baloncuk Sıralaması olarak da bilinen Bubble Sort oldukça basit bir mantığa dayanıyor.

Bubble Sort, karışık sırada verilen bir dizi içinde en baştan veya en sondan başlayarak birbirine bitişik şekilde duran ikili elemanları kıyaslayarak hareket eder. Bitişik elemanlar yanlış bir dizilime sahipse birbirleriyle yer değiştirmesi gerektiği ancak doğru dizilimdeyse yerlerinde kalmaları gerektiği temeline dayanır.

Tamamen teorik bir anlatımla her şey yerine oturmayabilir. İşi biraz daha görsel bir hale getirelim ve adım adım algoritmamızı inceleyelim.

Başlangıç: Karışık sırada verilen dizimizin (3,6,2,7,1,8) olduğunu düşünerek sıralamaya en baştan başlayarak algoritmayı adım adım işletelim.

1. Adım: En baştan başlayarak bitişik iki elemanı kıyasla, ilk eleman ikinci elemandan büyükse yerlerini değiştir değilse o şekilde kalsın. (3,6,2,7,1,8) İlk elemanımız olan 3 rakamı 6‘dan küçük olduğu için ikilinin yer değiştirmesine gerek yoktur. Yani ilk adım sonrası dizide bir değişiklik olmayacaktır. Birinci adımın sonucu: (3,6,2,7,1,8)

2. Adım: Bir eleman ilerleyerek sıradaki bitişik ikiliyi kıyasla ve Bubble Sort algoritma kurallarını uygula. (3,6,2,7,1,8) İlk elemanımız olan 6 rakamı 2‘den büyük olduğu için yer değiştirmeleri gerekmektedir. İkinci adımın sonucu: (3,2,6,7,1,8)

3. Adım: Bir eleman ilerleyerek sıradaki bitişik ikiliyi kıyasla ve Bubble Sort algoritma kurallarını uygula. (3,2,6,7,1,8) 6 rakamı 7’den küçük olduğu için yer değiştirmelerine gerek yoktur. Üçüncü adım sonucunda dizide bir değişiklik olmayacaktır. Üçünü adımın sonucu: (3,2,6,7,1,8)

4. Adım: Bir eleman ilerleyerek sıradaki bitişik ikiliyi kıyasla ve Bubble Sort algoritma kurallarını uygula. (3,2,6,7,1,8) 7 rakamı 1’den büyük olduğu için yer değiştirmeleri gerekmektedir. Dördüncü adımın sonucu: (3,2,6,1,7,8)

5. Adım: Bir eleman ilerleyerek sıradaki bitişik ikiliyi kıyasla ve Bubble Sort algoritma kurallarını uygula. (3,2,6,1,7,8) 7 rakamı 8’den küçük olduğu için yer değiştirmelerine gerek yoktur. Beşinci adım sonrası dizide bir değişiklik olmayacaktır. Beşinci adımın sonucu: (3,2,6,1,7,8)

Beşinci adıma kadar Bubble Sort algoritması uyguladığımız dizideki değişiklikleri aşağıda görebiliriz.

Dizi sıralı bir hale gelene kadar bu adımlar en başa dönerek tekrar edilir. Bubble Sort algoritmasını C# ile implement edersek;

void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // swap temp and arr[i] 
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void BubbleSort(int[] arr)

{

int n = arr.Length;

for (int i = 0; i < n - 1; i++)

{

for (int j = 0; j < n - i - 1; j++)

{

if (arr[j] > arr[j + 1])

{

// swap temp and arr[i]

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

Yukarıda adım adım algoritmayı incelerken kullandığımız (3,6,2,7,1,8) dizisini yazdığımız BubbleSort metoduna gönderdiğimizde aşağıdaki çıktı ile karşılaşıyoruz. Bubble Sort algoritması 15 adımda 7 elemanlı bir diziyi sıralamayı başarabilmiş.

7 elemanlı bir dizi için 15 adım algoritmanın performansı üzerine bizleri derin düşüncelere sevk ediyor olmalı. Şimdi de dilerseniz Bubble Sort algoritmasının performansını analiz edelim.

En İyi Durum Analizi (Best Case): Bubble Sort algoritması için en iyi durum verilen dizinin sıralı olması durumudur. Bu durumda dizideki her elemana bir kez bakılır ve işlem tamamlanır. Yani n elemanlı bir dizi için en iyi durum Ω(n) olur.

En Kötü Durum Analizi (Worst Case): Bubble Sort algoritması için verilen dizinin bitişik her elemanının karışık sırada olduğunu varsayalım. Yani dizinin tüm elemanları sırasız verilmiş olsun. n elemanlı bir dizi için başlangıçta n elemana bakılırken birinci geçişte n-1, ikinci geçişte n-2 ve son geçişte n-n yani sıfır tane elemana bakılır. Her geçişte geçiş sayısı kadar elemana bakılmış olur. Bu durumu formüle dökersek 1’den n’e kadar olan sayıların toplamını ifade etmemiz gerekir.

n x (n+1) /2

1	n x (n+1) /2

Yukarıdaki ifadede n’i parantez içine dağıttımızda;

n^2 + n /2

1	n^2 + n /2

ifadesine ulaşırız. Bu durumda üst sınırın (upper bound) n² olduğunu görüyoruz. Bubble Sort algoritmasının en kötü durumu O(n²) olarak bulunur.

Algoritmalar serisine sıralama algoritmalarından Bubble Sort ile başlamış bulunduk. Diğer algoritmaları inceleyeceğimiz yazılarda görüşene dek herkese mutlu günler, keyifli kodlamalar dilerim :)!