Ekleme Sıralama Algoritması(Insertion Sort)

Ekleme Sıralama Algoritması(insertion sort)

Ekleme sıralaması, sıralı dizinin tek seferde bir öğe içerecek şekilde oluşturulduğu sıralama mekanizmasıdır. Dizi elemanları birbiri ile ardışık olarak karşılaştırılır ve daha sonra belirli bir sırada eşzamanlı olarak düzenlenir. Bu sıralama, belirli bir konuma bir öğe ekleme ilkesi üzerinde çalışır, bu nedenle adı Ekleme Sıralamasıdır.

Ekleme Sıralama(insertion sort) nasıl çalışır?
  1. İlk adım, söz konusu elemanın bitişik elemanıyla karşılaştırılmasıdır.
  2. Karşılaştırma sonucunda, söz konusu eleman belirli bir konuma yerleştirilecekse, diğer elemanların bir konum sağa kaydırılması ve elemanın uygun konuma yerleştirilmesiyle alan yaratılır.
  3. Yukarıdaki prosedür dizideki tüm elemanlar uygun pozisyonlarına gelinceye kadar tekrarlanır.

Şimdi aşağıdaki örnekle çalışmayı anlayalım:

Şu diziyi göz önünde bulundurun: 25, 17, 31, 13, 2

İlk Yineleme : 25’i 17 ile karşılaştırın. Karşılaştırma 17<25’i gösterir. Dolayısıyla, 17 ve 25’in yerlerini değiştirin.

Dizi şimdi şöyle görünüyor: 17, 25, 31, 13, 2

Ekleme Sıralama Algoritması(Insertion Sort)
İlk Yineleme

İkinci Yineleme : İkinci sayıyla (25) başlayın, ancak doğru pozisyon da olduğu görülüyor, bu yüzden bir sonraki sayıya ilerliyoruz.

Şimdi üçüncü elemanı (31) tutun ve ondan önceki elemanlarla karşılaştırın.

Karşılaştırma 31> 25’i gösterir bu yüzden değişim yapılmaz.

Ayrıca bir sonraki karşılaştırma da 31> 17 gösterir bu yüzden değişim yapılmaz ve 31 pozisyonda kalır.

İkinci yinelemeden sonraki dizi şöyle görünür: 17, 25, 31, 13, 2

Ekleme Sıralama Algoritması(Insertion Sort)
İkinci Yineleme

Üçüncü Yineleme : Aşağıdaki Yinelemeyi dördüncü öğe (13) ile başlatın ve önceki öğelerle karşılaştırın.

13 <31 olduğu için ikisini değiştiriyoruz.

Dizi şu şekilde olur: 17, 25, 13, 31, 2.

Ancak hala 13 ile karşılaştırılmadığımız unsurlar var. Şimdi karşılaştırma 25 ile 13 arasında gerçekleşiyor. 13 <25 olduğu için ikisini değiştiriyoruz.

Dizi 17, 13, 25, 31, 2 olur .

Yineleme için son karşılaştırma şimdi 17 ile 13 arasındadır. 13 <17 olduğu için ikisini değiştiriyoruz.

Dizi şimdi 13, 17, 25, 31, 2 olur .

Ekleme Sıralama Algoritması(Insertion Sort)
Ekleme Sıralama Algoritması(Insertion Sort)
Üçüncü Yineleme

Dördüncü Yineleme : Son yineleme, son elemanın (2) önceki tüm elemanlarla karşılaştırılması gerekiyor.

İlk karşılaştırmamız  2 <31 olduğu için 2 ve 31’i değiştirin.

Dizi şu şekilde olur: 13, 17, 25, 2, 31.

2’yi 25, 17, 13 ile karşılaştıracağız.

İkinci karşılaştırmamızın sonucu 2 <25 olduğu için 25 ve 2’yi değiştirin.

Dizi şu şekilde olur:13, 17, 2, 25, 31.

2’yi 17 ve 13 ile karşılaştıracağız.

Üçüncü karşılaştırmamızın sonucu 2 <17 olduğu için 2 ve 17’yi değiştirin.

Dizi şu şekilde olur:13, 2, 17, 25, 31.

Yineleme için son karşılaştırma 2 ile 13’ü karşılaştırmaktır.

Son karşılaştırmamız da 2 <13 olduğu için 2 ve 13’ün yerleri değiştirilmelidir.

Dizinin son hali bu şekildedir: 2, 13, 17, 25, 31 .

Bu, karşılık gelen tüm yinelemelerden ve öğelerin yer değiştirmesinden sonraki son dizidir.

Ekleme Sıralama Algoritması(Insertion Sort)
Dördüncü Yineleme

Insertion Sort (Ekleme Sıralaması) Java Kodları

 	int dizi[] = { 25, 17, 31, 13, 2 };
		int boyut = dizi.length;
		for (int i = 1; i < boyut; ++i) {
			int deger = dizi[i];
			int j = i - 1;
			while (j >= 0 && dizi[j] > deger) {
				dizi[j + 1] = dizi[j];
				j = j - 1;
			}
			dizi[j + 1] = deger;
		}