Insertion Sort Algoritması (Eklemeli Sıralama)

Insertion Sort algoritması (Eklemeli Sıralama) nedir? Ne için kullanılır?

Eklemeli Sıralama, bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öge öge oluşturan bir sıralama algoritmasıdır. Büyük dizilerle çalışıldığında hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması gibi daha gelişmiş sıralama algoritmalarından daha verimsiz çalışır. Sokma sıralamasının (insert sort) performansı O(n²)’dir. Bunun sebebi dizideki eleman sayısı kadar geçiş gerekmesi ve her geçişte en kötü ihtimalle elemsan sayısı kadar kaydırma gerekmesidir. Yani insertion sort’un en kötü durumu tersten sıralı bir listedir. 

Sıralanacak olan sayılarımız :

33 44 21 83 56 73 22  olsun. Bu sayıları sıralamaya ilk sayıdan başlıyoruz (yani 33).

İlk geçişte (pass) sadece 33 sayısı sıralanmış oluyor (yani hiçbir şey yapmıyoruz):

33| 44 21 83 56 73 22 ( | işareti o anda kadar sıraladığımız sayıları gösteriyor. Bu işaretin “|” solundaki sayılar sıralanmış kabul ediyoruz. Ve her geçişte bir sağındaki sayıyı alıyoruz)

İkinci geçişte sıralayacağımız sayı 44. 33 ile 44’ü karşılaştırıyoruz. 33 küçük, dolayısıyla yer değiştirmiyorlar:

33 44 | 21 83 56 73 22

Üçüncü geçişte sıradaki sayı 21. 21 ile 44 karşılaştırılıyor ve 21 küçük olduğu için 44 ile yer değiştiriyorlar :

33 21 44 | 83 56 73 22 (geçişimiz henüz bitmedi çünkü 21, 33’ten de küçük:)

21 33 44 | 83 56 73 22 (şimdi 3. geçişi tamamladık ve bir sonraki sayı 83’ü alabiliriz:)

Dördüncü geçişte 83 var:

21 33 44 83 | 56 73 22 ( bu geçiş çabuk bitti çünkü 83, 44’ten büyük ve sadece bunu görmemiz durmamız için yeterli sonuçta 56’ya kadar sıralamış olduk)

Beşinci geçişte 56’yı sıralayacağız:

21 33 44 56 83 | 73 22 ( burada 56 ile 83 karşılaştırıldı ve 56 sayısı 83’ün soluna kaydırıldı. Bunun sebebi 56’nın 83’ten küçük olması. Bu geçişte burada bitti çünkü 56, 44’ten büyüktür)

Altıncı geçişte sıra 73’te:

21 33 44 56 73 83 | 22 ( sıralamamız yine tek adımda bitiyor çünkü 73, 83’ten küçük ve 56’dan büyük)

Yedinci geçişte 22 sayısını yerleştireceğiz ve adım adım 22’den küçük olan bir sayı görene kadar 22’yi dizide kaydırıyoruz:

21 33 44 56 73 22 83 |

21 33 44 56 22 73 83 |

21 33 44 22 56 73 83 |

21 33 22 44 56 73 83 |

21 22 33 44 56 73 83 |

Sonuçta işaretimiz “|” dizinin sonuna ulaştı ve dizimiz sıralanmış oldu.

Kodlama

Python, Java ve C dillerinde ise şu şekilde yazabiliriz.

JAVA

void sort(int arr[])
{
int n = arr.length;
for (int i=1; i<n; ++i)
{
int deger = arr[i];
int j = i-1;while (j>=0 && arr[j] > deger)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = deger;
}
}

def insertionSort(arr):

for i in range(1, len(arr)):

deger = arr[i]

j = i-1
while j >=0 and deger< arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = deger

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

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