İnsertion Sort: Eklemeli Sıralama Algoritması C Sharp

İnsertion Sort (Eklemeli Sıralama veya araya sokmalı sıralama şeklinde de duyabilirsiniz) çok basit bir mantıkla çalışan bir algoritmadır. Merge Sort, Quick Sort, Heap Sort gibi sıralama algoritmalarına göre biraz daha yavaş çalışıyor. (Çünkü bu bahsettiğim algoritmalar da Böl ve Fethet tekniği uygulanıyor.(ilerleyen günlerde değineceğiz.) ) 

 

Şimdi bu algoritmanın çalışma mantığını anlatmaya çalışıyım:

Elimde bir “P” kümesi olsun ve

p= { 48, 73, 2, -4, 96 } gibi elemanlardan oluşsun. Adım adım inceliyoruz…

Adım1: (1. iterasyon)

p= { 48, 73, 2, -4, 96 }

Elime dizinin ilk elemanı olan 48 sayısını alıyorum. Ve kendinden bir sonra gelen sayı 73 ile karşılaştırıyorum. Sorum şu: Hangisi daha küçük? (Eğer elimdeki 48 sayısı küçük ise bir sonraki sayı olan 2 yi kıyaslamaya alıyorum.)

Cevap: 48, 73ten küçük. O halde yerinde kalsın.

Adım2: (2. iterasyon)

2 adım ilerledik elimde şu an 73 sayısı var. 73 ile 2 yi kıyasladığımda hangisi daha küçük? Cevap: 2

O halde 73 ile 2 nin yerlerini kendi aralarında değiştir.

p= { 482, 73, -4, 96 }  tamam yerleri değişti. ama 48 ile 2 yi kıyasladığımızda 2 nin 48 den küçük olduğunu görüyoruz. O halde bir yer değişim daha yapalım.

p= { 2, 48, 73, -4, 96 } (dizinin son hali)

Adım3: (3. iterasyon)

Şu an elimde 3. sayı yani 73 var.

p= { 2, 48, 73-4, 96 }

(73 < -4)  ? sorusunu sorduğumda hemen 73 ile -4 yerleri değişiyor.

p= { 2, 48, -4, 73, 96 }

(48 < -4)  ? sorusunu sorduğumda hemen 48 ile -4 yerleri değişiyor.

p= { 2, -4, 48, 73, 96 }

(2 < -4)  ? sorusunu sorduğumda hemen 2 ile -4 yerleri değişiyor.

p= {-4, 2, 48, 73, 96 } (dizinin son hali)

Adım4: (4. iterasyon)

p= {-4, 2, 48, 73, 96 }

4. adımda elimdeki sayı 73. (Vay arkadaş ne 73müş bir kurtulamadık!) şimdi 73 ile 96 (73 bir sonraki sayısı) kıyaslaması yapıyoruz.

(73 < 96)  ? sorusunu sorduğumda HAYIR cevabı alıyorum. Ve 73 ten sol tarafı sıralı olduğu için direk kestirip atıyorum bu iterasyonu.

Adım5: (5. iterasyon)

p= {-4, 2, 48, 73, 96 }

Elimde şu an 96 sayısı var. Hemen sağına bakıyorum. “Aaa. başka sayı kalmamış!” O halde biliyorum ki 96 dan öncesi yani sol tarafı kendi içinde sıralanarak buralara gelmişti. Yani sıralıydı. Eee 96 dan sonrası da olmadığı için Algoritmamız burada sona erer.

p= {-4, 2, 48, 73, 96 }

(Bitirdik sonunda, yazarken çok sıkılmıştım…)


 

Bu algoritma ile ilgili aşağıdaki video’ yu izlemenizi tavsiye ederim. Eğlenceli bir anlatım olmuş…


 

Karmaşıklık Hesabı                    [Bu başlık tr.wikipedia.org’ den alıntıdır.]

Eklemeli sıralama algoritmasının zaman karmaşıklığı hesaplanırken, yapılan karşılaştırmalar ve yer değiştirmeler dikkate alınır. Eklemeli sıralama algoritması {\textstyle n}elemanlı bir listede, ikinci eleman için en fazla 1 karşılaştırma ve 1 yer değiştirme yapar, üçüncü eleman için 2 karşılaştırma ve 2 yer değiştirme, dördüncü eleman için 3 karşılaştırma ve 3 yer değiştirme yapar. Bu şekilde son eleman için en fazla {\textstyle n-1} karşılaştırma ve {\textstyle n-1} yer değiştirme yapar. Listedeki bütün elemanlar için yapılan karşılaştırmaların ve yer değiştirmelerin toplamı

{\displaystyle 2(1 + 2 + 3+ 4+ ... + (n-2) + (n-1)) = 2(n(n-1)/2) = n(n-1)}yapar. Hesaplamalar sonucunda elde edilen{\displaystyle n(n-1)}degerinin asimptotik üst sınırı {\textstyle O(n^2)} değerini verir.

En kötü başarım: Eklemeli sıralama algoritması en kötü durumda, örneğin liste tersten sıralıysa {\textstyle O(n^2)} karmaşıklıkla çalışır.

En iyi başarım: Eklemeli sıralama algoritması en iyi durumda, örneğin liste sıralıysa sadece {\textstyle n-1} karşılaştırma yapar ve {\textstyle O(n)} karmaşıklıkla çalışır.

Ortalama başarım: Eklemeli sıralama algoritması ortalama {\textstyle O(n^2)} karmaşıklıkla çalışır.

 


 

 

Ve şimdi gelelim Kod Yazmaya…

 

Aşağıdaki programın örnek çıktısı:

Ekran Alıntısı

 

 

 

[code lang=”csharp”]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace insSort
{
class Program
{
// INSERTION SORT ALGORITMASI
public void insertionSortCalistir(int[] dizi)
{
for (int j = 1; j < dizi.Length; j++)
{
int key = dizi[j];
int i = j – 1;
while (i >= 0 && dizi[i] > key)
{
dizi[i + 1] = dizi[i];
i = i – 1;
}
dizi[i + 1] = key;
}
}
//————————-

static void Main(string[] args)
{
int n;
Console.Write("Kaç eleman gireceksiniz? : ");

n = Convert.ToInt32(Console.ReadLine());
int[] aDizisi = new int[n];// KULLANICIDAN ALINAN N DİZİSİ KADAR DİZİ OLUŞTURULUYOR.
Console.Write("\n\n\n");// 3 SATIR BOŞLUK

// N SAYISI KADAR OLUŞTURULAN DİZİYE DEĞER ATAMA İŞLEMİ
for (int i = 0; i < n; i++)
{
Console.Write("Dizinin " + (i + 1) + ". elemanı: ");
aDizisi[i] = Convert.ToInt32(Console.ReadLine());
}
//—————————-
Console.WriteLine("Girdiğiniz dizi şu şekildedir: \n \n");
for (int f = 0; f < n; f++)
{
Console.Write("\t" + aDizisi[f]);
}
/* PROGRAM SINIFI ALTINDA BULUNAN insertionSortCalistir METODUMUZ İÇİN BİR A SINIFI OLUŞTURDUK
VE SINIFA AİT OLAN insertionSortCalistir METODUNU KULLANDIK.
*/
Program a = new Program();
a.insertionSortCalistir(aDizisi);
Console.WriteLine("\n \n —İnsertion Sort ile sıralanan dizi şu şekildedir— \n \n");
for (int f = 0; f < n; f++)
{
Console.Write("\t" + aDizisi[f]);
}
//————–

// \t 8 KARAKTER GÜCÜNDE BOŞLUK BIRAKIYOR. \n İSE BİR ALT SATIRA İNDİRİYOR.
Console.WriteLine("\n \n \n \n \t\t\t MelihHilmiUludag");

// CONSOLE ORTAMINI EKRANDA TUTMAK İÇİN KULLANICININ KLAVYEYE BASMASINI BEKLİYORUM.
Console.ReadLine();
}
}
}

[/code]

Anlatımla ilgili bir yanlışım olduysa yorum olarak belirtin arkadaşlar, düzeltelim. Bildiğim kadarıyla anlatmaya çalıştım. Kolay gelsin, iyi çalışmalar.

Melih Hilmi Uludağ

Bir cevap yazın

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