Bubble Sort – Kabarcık Sıralama Algoritması

17 Nisan 2021 04 Cts, 2021 11:31 tarihinde düzenlendi 2033 kez okundu Okuma süresi: 6dk, 15sn

+ - 0

Bubble Sort – Kabarcık Sıralama Algoritması yazım ile yapay zekaya temellerinden bir giriş yapıyoruz. Bu seride C++ ‘ı da öğrenmeye başlayacağız. Sıralama algoritmalarının hem C# ve C++ kodları ile yazıp göreceğiz. Olabildiğinde çok sıralama algoritmasını işledikten ve sindirdikten sonra üst seviyelerine doğru adım adım çıkacağız. Yani hem C++ öğrenip hem de sıralama algoritmalarından başlayarak yapay zeka konularına girişeceğiz.

Bubble Sort – Kabarcık Sıralama Algoritması

Bubble Sort – Kabarcık Sıralaması Nedir?

Bubble Sort bilgisayar bilimlerinde kullanılan bir çeşit sıralama algoritmasıdır. Bu algoritmada her sayı çifti birbirleri ile karşılaştırılarak büyükten küçüğe doğru sayıların yerlerini değiştirerek tüm dizi sıralanmış olur. Eğer sağdaki sayı soldaki sayıdan büyükse işlem yapılmaz. Sağdaki sayı, soldaki sayıdan küçükse iki sayı yer değiştirilir. Bubble Sort – Kabarcık Sıralaması algoritmasının çalışma mantığı bu şekildedir. Bizde bu mantığa göre kodlarımızı yazacağız.

Bubble Sort‘un kullandığı veri yapısı Dizi’dir. Zaman Karmaşıklığı О(n²), Alan Karmaşıklığı ise toplamda О(n), ek alanda olarak da O(1) ‘dir

Bu algoritma dizide sıralanacak sayı kalmayana kadar, tekrar tekrar en başa dönerek kendisini yineler. Bu algoritmaya Bubble (Kabarcık) denmesinin sebebi ise büyük sayıların dizinin sonuna doğru itilmesinin, kabarcıkların suyun yüzeyine çıkmasına benzetildiği içindir.

Algoritmanın temel mantığı büyükleri sayıları dizisin sonuna küçük sayıları da dizinin başına doğru yerlerini değiştirerek sıralamasıdır. Aşağıdaki gif bubble sort‘un nasıl çalıştığını görselleştirmektedir.

Bubble_sort_animation

Aşağıdaki görsel Bubble Sort sıralama Algoritmasının durağan görüntüsüdür.

Bubble Sort – Kabarcık Sıralaması Nasıl Çalışır?

Bubble Sort, dizinin en başından başlar ve dizi elemanları arasında sırayla gezer. Seçilen bir eleman, kendinden sonra gelen elemandan küçükse bir işlem yapılmaz. Ancak aksi durumda, seçilen dizi elemanı, kendinden sonra seçilen dizi elemanından büyük ise iki elemanın yerleri değiştirilir.

Algoritmanın Karmaşıklığı

Kabarcık Sıralama Algoritmasını ortalama ve en kötü durumdaki karmaşıklığı ${\mathcal {O}}(n^{2})$

Algoritmanın Adım Adım İşleyişi

Aşağıdaki şekilde bir dizimiz olsun. Bubble Sort çalışmaya 99’dan başlar. Kalın ve Kırmızı elemanlar karşılaştırılan elemanlardır.

“99, 5, 2, 78, 89, 56, 1, 3, 7″ , 99 ile 5 karşılaştırılır. 99 büyük olduğundan iki sayı yer değiştirilir. Sıra 2. İndex’e gelir

“5, 99, 2, 78, 89, 56, 1, 3, 7″ , 99 ile 2 karşılaştırılır. 99 büyük olduğundan iki sayı yer değiştirilir. Sıra 3. İndex’e gelir

“5, 2, 99, 78, 89, 56, 1, 3, 7″ , 99 ile 2 karşılaştırılır. 99 büyük olduğundan iki sayı yer değiştirilir. Sıra 4. İndex’e gelir

Sıralama bu şekilde devam eder. Ta ki 99 en sona gelene kadar. 99 en sona geldiğinde sıralama başa döner. Burada en büyük en başta olduğu için bu kadar yavaş oldu. Eğer 99 sona yakın bir yerde olsaydı, büyükle küçüğün yer değiştirmesi 99’a gelene kadar yine devam edecekti. Yani işin özü, her zaman en büyük sayı en sona gider. Büyük sayı küçüklerin üstlerinden atlatılır küçük sayılar arkada kalır ve zaten büyüklerin itelenmesi sırasında küçükler büyük ölçüde sıralanmış olacaktır.

Başka bir örnek üzerinden de bakalım.

Dizimiz “5, 1, 4, 2, 8” olsun.

1. Geçiş
1.Adım : ( 5 1 4 2 8 ) $\to$ ( 1 5 4 2 8 ) – 1, 5 ten küçüktür. O halde yer değişirler
2.Adım: ( 1 5 4 2 8 ) $\to$ ( 1 4 5 2 8 ) – 4, 5 ten küçüktür. O halde yer değişirler
3.Adım: ( 1 4 5 2 8 ) $\to$ ( 1 4 2 5 8 ) – 2, 5 ten küçüktür. O halde yer değişirler
4.Adım: ( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ) – 8, 5 ten büyüktür. Yer değiştirme yapılmaz.
2. Geçiş
1.Adım : ( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 )
2.Adım: ( 1 4 2 5 8 ) $\to$ ( 1 2 4 5 8 )
3.Adım: ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
4.Adım: ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
3. Geçiş
1.Adım : ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
2.Adım: ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
3.Adım: ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
4.Adım: ( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )

Sonuç olarak dizi sıralanmıştır ve döngü sona erer.

Bubble Sort – Kabarcık Sıralama Algoritması C# ve C++ Kodları

Şimdi gelelim kodlarına. C# ve C++ olarak nasıl kodlanıyor görelim. Kodları ve çıktılarını ekran görüntüsü olarak vereceğim arkadaşlar.

Dizimiz bu şekilde: {5, 6, 8, 1, 88, 99, 78, 45, 36, 25, 12, 9, 7}

C# Kodları

        private void btn_bubble_short_Click(object sender, EventArgs e)
        {
            Bubble_Short();
        }
        int[] Sayilar = new int[] { 5, 6, 8, 1, 88, 99, 78, 45, 36, 25, 12, 9, 7 };
        void Bubble_Short()
        {
            for (int i = 0; i < Sayilar.Count(); i++)
                for (int j = 0; j < (Sayilar.Count() - i - 1); j++)
                    if (Sayilar[j] > Sayilar[j + 1])
                    {
                        swap(Sayilar[j], j, Sayilar[j + 1], j + 1);
                    }
            Yazdir();
        }
        void swap(int num1, int index1, int num2, int index2)
        {
            Sayilar[index1] = num2;
            Sayilar[index2] = num1;
        }

        void Yazdir()
        {
            listBox1.Items.Add(string.Join(",", Sayilar));
        }

Şimdi… C# kodlarında her aşamasının adım adım çıktısına bakalım.

5,6,1,8,88,99,78,45,36,25,12,9,7
5,6,1,8,88,78,99,45,36,25,12,9,7
5,6,1,8,88,78,45,99,36,25,12,9,7
5,6,1,8,88,78,45,36,99,25,12,9,7
5,6,1,8,88,78,45,36,25,99,12,9,7
5,6,1,8,88,78,45,36,25,12,99,9,7
5,6,1,8,88,78,45,36,25,12,9,99,7
5,6,1,8,88,78,45,36,25,12,9,7,99
5,1,6,8,88,78,45,36,25,12,9,7,99
5,1,6,8,78,88,45,36,25,12,9,7,99
5,1,6,8,78,45,88,36,25,12,9,7,99
5,1,6,8,78,45,36,88,25,12,9,7,99
5,1,6,8,78,45,36,25,88,12,9,7,99
5,1,6,8,78,45,36,25,12,88,9,7,99
5,1,6,8,78,45,36,25,12,9,88,7,99
5,1,6,8,78,45,36,25,12,9,7,88,99
1,5,6,8,78,45,36,25,12,9,7,88,99
1,5,6,8,45,78,36,25,12,9,7,88,99
1,5,6,8,45,36,78,25,12,9,7,88,99
1,5,6,8,45,36,25,78,12,9,7,88,99
1,5,6,8,45,36,25,12,78,9,7,88,99
1,5,6,8,45,36,25,12,9,78,7,88,99
1,5,6,8,45,36,25,12,9,7,78,88,99
1,5,6,8,36,45,25,12,9,7,78,88,99
1,5,6,8,36,25,45,12,9,7,78,88,99
1,5,6,8,36,25,12,45,9,7,78,88,99
1,5,6,8,36,25,12,9,45,7,78,88,99
1,5,6,8,36,25,12,9,7,45,78,88,99
1,5,6,8,25,36,12,9,7,45,78,88,99
1,5,6,8,25,12,36,9,7,45,78,88,99
1,5,6,8,25,12,9,36,7,45,78,88,99
1,5,6,8,25,12,9,7,36,45,78,88,99
1,5,6,8,12,25,9,7,36,45,78,88,99
1,5,6,8,12,9,25,7,36,45,78,88,99
1,5,6,8,12,9,7,25,36,45,78,88,99
1,5,6,8,9,12,7,25,36,45,78,88,99
1,5,6,8,9,7,12,25,36,45,78,88,99
1,5,6,8,7,9,12,25,36,45,78,88,99
1,5,6,7,8,9,12,25,36,45,78,88,99

C++ Kodları

#include <stdio.h>
#include <iostream>
using namespace std;

int dizi[] = { 5, 6, 8, 1, 88, 99, 78, 45, 36, 25, 12, 9, 7 };

void swap(int num1, int index1, int num2, int index2)
{
	// burada değerler parametre olarak tutulduğu içim temp değişkenine gerek duymadık.
	dizi[index1] = num2;
	dizi[index2] = num1;
}

void bubbleSort(int n)
{
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < n - i - 1; j++)
			if (dizi[j] > dizi[j + 1])
				swap(dizi[j], j, dizi[j + 1], (j + 1));
}

void printArray(int dizii[], int size)
{
	for (int i = 0; i < size; i++)
		cout << dizii[i] << " ";
	cout << endl;
}

int main()
{
	int n = sizeof(dizi) / sizeof(dizi[0]);
	bubbleSort(n);
	cout << "Sıralanmis Dizi: \n";
	printArray(dizi, n);
	return 0;
}

Bubble sort - kabarcık sıralama cpp 2

5 6 1 8 88 99 78 45 36 25 12 9 7
5 6 1 8 88 78 99 45 36 25 12 9 7
5 6 1 8 88 78 45 99 36 25 12 9 7
5 6 1 8 88 78 45 36 99 25 12 9 7
5 6 1 8 88 78 45 36 25 99 12 9 7
5 6 1 8 88 78 45 36 25 12 99 9 7
5 6 1 8 88 78 45 36 25 12 9 99 7
5 6 1 8 88 78 45 36 25 12 9 7 99
5 1 6 8 88 78 45 36 25 12 9 7 99
5 1 6 8 78 88 45 36 25 12 9 7 99
5 1 6 8 78 45 88 36 25 12 9 7 99
5 1 6 8 78 45 36 88 25 12 9 7 99
5 1 6 8 78 45 36 25 88 12 9 7 99
5 1 6 8 78 45 36 25 12 88 9 7 99
5 1 6 8 78 45 36 25 12 9 88 7 99
5 1 6 8 78 45 36 25 12 9 7 88 99
1 5 6 8 78 45 36 25 12 9 7 88 99
1 5 6 8 45 78 36 25 12 9 7 88 99
1 5 6 8 45 36 78 25 12 9 7 88 99
1 5 6 8 45 36 25 78 12 9 7 88 99
1 5 6 8 45 36 25 12 78 9 7 88 99
1 5 6 8 45 36 25 12 9 78 7 88 99
1 5 6 8 45 36 25 12 9 7 78 88 99
1 5 6 8 36 45 25 12 9 7 78 88 99
1 5 6 8 36 25 45 12 9 7 78 88 99
1 5 6 8 36 25 12 45 9 7 78 88 99
1 5 6 8 36 25 12 9 45 7 78 88 99
1 5 6 8 36 25 12 9 7 45 78 88 99
1 5 6 8 25 36 12 9 7 45 78 88 99
1 5 6 8 25 12 36 9 7 45 78 88 99
1 5 6 8 25 12 9 36 7 45 78 88 99
1 5 6 8 25 12 9 7 36 45 78 88 99
1 5 6 8 12 25 9 7 36 45 78 88 99
1 5 6 8 12 9 25 7 36 45 78 88 99
1 5 6 8 12 9 7 25 36 45 78 88 99
1 5 6 8 9 12 7 25 36 45 78 88 99
1 5 6 8 9 7 12 25 36 45 78 88 99
1 5 6 8 7 9 12 25 36 45 78 88 99
1 5 6 7 8 9 12 25 36 45 78 88 99
Siralanmis Dizi:

C:\Users\pc\source\repos\CPP_Bubble_Sort_Algoritm\Debug\CPP_Bubble_Sort_Algoritm.exe (process 13352) exited with code 0.
To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops.
Press any key to close this window . . .

Adım adım çıktılarını incelerseniz C++ ve C# çıktılarının aynı olduğunu görebilirsiniz.

Bubble Sort – Kabarcık Sıralama Algoritması yazım da bu kadardı arkadaşlar. Gerçekten çok doyurucu ve tatmin edici bir ders olduğunu düşünüyorum. Umarım sizler içinde öyle olmuştur.

Bu arada unutmadan söylemek istiyorum. Bu algoritmalara de C++ ‘a bugün (16.04.2021) ‘de başladım. Sonra dedim ki bunların dersleri yazmalıyım. Hem araştırmalarımda, hem denemelerimde defalarca aynı kodları yazdığım için ve tabi anlatabilmek için anlamam gerektiği için aynı zamanda da öğrenip pekiştiriyorum.

Bu derste verdiğim C# Bubble Shorting ve C++ Bubble Shorting kodları github profilimde paylaştım. Bağlantılarına tıklayarak projelere ulaşabilirsiniz.

Bu dersler Yapay Zeka temelinde olduğundan dolayı ilgili kategorinin derslerine ulaşmak için bağlantıya tıklayabilirsiniz. Ayrıca bu yazının PDF’ine buraya ve ya buraya tıklayarak ulaşabilirsiniz.

Diğer derslerde görüşürüz.

Bol Kodlu günler! :)

Bu yazıya tepkiniz ne oldu?