Insertion Sort, bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öge öge oluşturan bir sıralama algoritmasıdır. Insertion Sort Algoritması, düzensiz dizi elemanlarını tek tek ele alarak her birini dizinin sıralanmış kısmındaki uygun yerine yerleştirme esasına dayanır. Genelllikle günlük hayatımızda farketmeden kullandığımız bir çözüm yöntemidir. Küçük boyutlu dizileri sıralamada hızlı olsa da çok sayıda veriyi sıralarken Insertion Sort diğer sıralama yöntemlerine göre çok yavaş kalmaktadır.
Algoritmanın Çalışma Mantığı
Algoritmada, ikinci elemandan başlayarak elemanın kendinden önceki elemanlarla karşılaştırılması suretiyle büyük elemanlar dizide sağa doğru kaydırılır. Böylelikle açılan uygun pozisyona o anda sıralanmakta olan eleman yerleştirilir. Yani, algoritmanın küçükten büyüğe sıralama yaptığı düşünülürse, sayı dizisinin ikinci elemanını kendisine anahtar eleman olarak seçer. Bu anahtar eleman bir önceki elemandan başlayıp, kendinden önceki tüm sayılarla, anahtar olarak seçilen sayıyı kıyaslar. Kendinden büyük olan her sayıyla yerleri değiştirir. Kendinden küçük sayıyla karşılaştığında yer değiştirme işlemi biter. Ardından dizinin son elemanına kadar anahtar sayı seçimi ve devamındaki tüm işlemler devam eder.
Bir sayı dizisinin sıralaması aşağıdaki gibi olur.
Algoritmanın C# Programlama Diliyle Gerçeklenmesi
Aşağıdaki "btSort_Click" metodunun içerisinde "Random" metodu için gerekli olan veriler aşağıadki örnekte gösterilen metin kutularından alınmaktadır. İlk metin kutusuna girilen değer kaç adet sayı oluşturulacağı, ikinci metin kutusuna girilen değer ise sayıların 1'den başlayarak kaça kadar rastgele tanımlanacağını belirtmektedir. Metin kutuları doldurulduktan sonra "Sırala" düğmesine tıklanarak "btSort_Click" metodu çalıştırılır. "btSort_Click" metodu içerisinde metin kutularındaki verilere göre rastgele sayılar ile bir dizi oluşturularak, "insertion_sort" metoduna gönderilir. Bu dizi "insertion_sort" metodunda sıralanarak, "btSort_Click" metoduna geri gönderilip ekrana yazdırılır. Bu sırada "TimeSpan" metodu ile sıralama işlemi bitene kadar olan süre hesaplanır.
protected void btSort_Click(object sender, EventArgs e)
{
int length = int.Parse(tbNumber.Text);
int limit = int.Parse(tbLimit.Text);
int[] dizi = new int[length];
Random random = new Random();
Stopwatch sw = new Stopwatch();
for (int i = 0; i < length; i++)
dizi[i] = random.Next(1,limit);
sw.Start();
insertion_sort(dizi);
sw.Stop();
TimeSpan time = sw.Elapsed;
Response.Write("Geçen süre:" + time.ToString());
for (int i = 0; i < length; i++)
lbSorted.Text += (dizi[i].ToString() + " ");
}
Bir dizinin içerisindeki elemanlar "insertion_sort" metodu ile küçükten büyüğe doğru sıralanır.
public void insertion_sort(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;
}
}
Bu uygulamanın çıktısı aşağıdaki gibi olacaktır: