Insertion Sort – Eklemeli Sıralama Algoritması

Merhabalar, yazma sırası Insertion Sort – Eklemeli Sıralama Algoritması ‘na geldi. Daha önce Bubble Sort algoritmasını görmüştük. Hem C# hem de C++ programlama dillerinde nasıl kodlandığını paylaşacağım. Hem yapay zekaya temellerinden başlamak hem de C++ öğrenmeyi hedefliyoruz.

Insertion Sort – Eklemeli Sıralama Algoritması

Insertion Sort – Eklemeli Sıralama Algoritması Nedir?

İngilizcesi Insertion Sort Türkçesi Eklemeli Sıralama‘dır. Eklemeli denmesindeki sebep her itemi olması gereken yere sokmadan diğer sayılara ilerlemiyor olmasıdır. Yani sıralama öge öge sıraya dizilir. Büyük diziler ile çalışıldığında Insertion Sort Hızlı Sıralama (Quick), Birleştirmeli Sıralama (Merged) ve Yığın Sıralamasına (Heapsort) göre daha verimsiz çalışmaktadır ancak yine de bazı artıları vardır.

1. Insertion Sort ‘un uygulanması kolaydır.
2. Küçük veri kümelerinde avantajlıdır.
3. Çoğunluğu zaten sıralı olan dizilerde çok daha hızlıdır.
4. Karmaşıklık seviyesi   olan Seçmeli Sıralama (Selection) ve Kabarcık Sıralama (Bubble) gibi yalın sıralamalardan daha verimlidir.
5. Kararlı bir algoritmadır.
6. Sıralanması istenen diziyi yerinde sıraladığı için ekstra bir alan gerekmez.
7. Sıralanacak dizinin algoritma girdisi olmasına gerek yoktur ve ek olarak sıralama esnasında diziye eleman eklenebilir.

BİLGİ: İnsanlar neredeyse her şeyi sıralarken Eklemeli Sıralama (Insertion) kullanır. Örneğin iskambil kağıtlarını sıralama…

Insertion Sort Çalışma Prensibi

Bir ögenin olması gerektiği yere konularak devam edilmesi ve böylece giderek kontrol edilecek ögelerin sayısını azaltma prensibine dayanır. Bu çalışma prensibini elimizde iskambil kağıtlarını sıralama şeklimize benzetebiliriz. Örneğin  A yı bir elimize alırız sonra listeden sırayla ikisini, üçünü, dördünü ararız.

Aşağıdaki görselde eklemeli sıralamanın çalışma şeklinin görselleştirilmiş halini görebilirsiniz.

Karmaşıklık Hesabı

Algoritmanın zaman karmaşıklığı hesaplanırken sıralama esnasında yapılan karşılaştırmalar ve yer değiştirmelere bakılır. Algoritma sıralaması n elemanlı bir listede ikinci öge için en az bir karşılaştırma ve en az 1 yer değiştirme yapar. Üçüncü öge için iki karşılaştırma ve iki yer değiştirme yapılır. Dördüncü öge için üç karşılaştırma ve üç yer değiştirme yapılır. Bu da demek oluyor ki son eleman için n-1 karşılaştırma ve n-1 yer değiştirme yapılır.

Tüm ögelerin hesabı…

2(1+2+3+4+…+(n-2) + (n-1)) = 2(n(n-1)/2) = n(n-1)

yani sonuç olarak n(n-1) ‘i elde ederiz ve asimptotik üst sınırı olarak O(n²) değerini verir.

• En İyi Başarım: Liste sıralı ise n-1 karşılaştırma yaparak O(n) karmaşıklıkta çalışır. (Genellikle en iyi değil.)
• Ortama Başarım: Ortalama olarak O(n²) karmaşıklıkta çalışır.
• En Kötü Başarım:  Liste tersten sıralı ise O(n²) karmaşıklıkta çalışır.

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

Algoritmanın adım adım çalışma şekline bir bakalım

• 8 2 4 9 3 6   > İlk olarak 8 seçilir.
• 8 2 4 9 3 6   > Dizinin ikinci ögesi olan 2 seçildi. Elimizde ilk tuttuğumuz 8 sayısından küçük olduğu için yer değiştirirler.
• 2 8 4 9 3 6   > 4 seçildi.  8, 4 ile kıyaslandı. 4 küçük olduğu için 8 ile 4 yer değişti.
• 2 4 8 9 3 6   > 9 seçildi. 8, 9 ile kıyaslandı. 8 küçük olduğu için 8 ile 9 yer değiştirmedi
• 2 4 8 9 3 6   > 3 seçildi 9 ile kıyaslanacak.
• 2 3 4 8 9 6   > 9, 3 ile kıyaslandı. 3 küçük olduğu için 9 ile 3 yer değişti. 3 olması gereken yer ulaşana kadar hareket etti.
• 2 3 4 8 9 6   > 6 seçildi. 9 ile 6 kıyaslandı. 6 küçük olduğu için 9 ile 6 yer değişti. 6 olması gereken yere kadar hareket etti.
• 2 3 4 6 8 9 — > Sıralanmış dizimiz

Yukarıdaki örnekten de anlayacağınız gibi bir sayı kendinden öncesi ile kıyaslanır. Eğer küçük ise yer değiştirir. Eğer yer değiştirme olmuşsa odak bir geri kayar. Az önce küçük olduğu için yeri değiştirilen sayı, yine kendinden önceki ile kıyaslanır. Eğer küçük ise kendinden önceki sayı ile yer değiştirir. Bu şekilde en küçük sayı ilk saraya gelene kadar devam eder.

Insertion Sort – Eklemeli 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ı

        int[] sayilar = new int[] { 5, 6, 8, 1, 88, 99, 78, 45, 36, 25, 12, 9, 7 };
        private void button2_Click(object sender, EventArgs e)
        {
            for (int i = 0; i < sayilar.Count(); i++)
            {
                int deger = sayilar[i];
                int j = i - 1;
                while (j >= 0 && sayilar[j] > deger)
                {
                    sayilar[j + 1] = sayilar[j];
                    j -= 1;
                }
                sayilar[j + 1] = deger;
                textBox1.Text += string.Join(",", sayilar) + Environment.NewLine;
            }
        }

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

C++ Kodları

#include< iostream >

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

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

void insertionSort(int arr[], int n)
{
	int  deger, j;
	for (int i = 1; i < n; i++)
	{
		deger = arr[i];
		j = i - 1;

		while (j >= 0 && arr[j] > deger)
		{
			arr[j + 1] = arr[j];
			j -= 1;
		}
		arr[j + 1] = deger;
		
	}
}

int main()
{
	int n = sizeof(sayilar) / sizeof(sayilar[0]);
	insertionSort(sayilar, n);
	printArray(sayilar, n);
}

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

C:\Users\pc\source\repos\insertion_sorting\Debug\insertion_sorting.exe (process 8476) 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.

Insertion Sort – Eklemeli Sıralama Algoritması yazımda bu kadar arkadaşlar.

Bu arada unutmadan söylemek istiyorum. Bu algoritmalara de C++ ‘a dü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# Insertion Sorting  ve C++ Insertion Sorting 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! ?