Insertion Sort Nedir?

Genelde kart oyunları gibi sıralama gerektiren oyunlarda insanlar elindeki kartları sıralamak için farkında olmadan bu algoritmayı uygulamaktadır. Karmaşıklığı N^2 olduğu için verimlilik konusunda biraz düşündürücü olan bu algoritma nasıl çalışır hep beraber bakalım.

1. Verilen dizinin insertion sort aşamaları

Birinci dizi: [22, 27, 16, 2, 18, 6]

1. [22, 27, 16, 2, 18, 6]
2. [16, 22, 27, 2, 18, 6]
3. [2, 16, 22, 27, 18, 6]
4. [2, 16, 18, 22, 27, 6]
5. [2, 6, 16, 18, 22, 27]

2. Big-O gösterimi ve time complexity

Worst case: En kötü durumda diziyi komple sıralamak gerekmektedir çünkü dizi tam tersi sırada verilmiştir. İlk basamakta 1 tane işlem yapılır yani ilk elemanla ikincinin yeri değiştirilir. İkinci basamakta ise 2. ve 3.elemanın yerini değiştirdikten sonra 1. ve 2. elemanın yeri değiştirilir yani 2 işlem yapılmış olur. Bu şekilde devam edildiğinde 1+2+3+4+...+n-1 = (n*(n-1))/2 bu da n^2 eşitliğine denktir. Burada big-o gösterimi ise O(n^2) olmaktadır.

Best case: En iyi durumda ise dizi zaten sıralıdır. n tane sıralı dizinin üzerinden sadece 1 kere geçer. O(n)

Avarage case: En kötü ve en iyi case'in ortalamasıdır. O(n^2)

3. 18 sayısının case durumu nedir? 

Dizi sıralandığında 18 sayısı dizinin ortasında yer aldığından average case'dir.

İkinci dizi: [7, 3, 5, 8, 2, 9, 4, 15, 6]

3.1 Verilen dizinin insertion sort'a göre ilk 4 aşaması

1. [3, 7, 5, 8, 2, 9, 4, 15, 6]
2. [3, 5, 7, 8, 2, 9, 4, 15, 6]
3. [3, 5, 7, 8, 2, 9, 4, 15, 6]
4. [2, 3, 5, 7, 8, 9, 4, 15, 6]

Python Insertion Sort Örneği

def insertionSort(array):

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

value = array[i]

index = i

while index>0 and array[index-1]>value:

array[index] = array[index-1]

index = index - 1

array[index] = value

list = [10, 5, 1, 4, 3]

insertionSort(list)

print(list)

Çıktı: [1, 3, 4, 5, 10]

Yazar: Simge Bakış