Insertion Sort Algoritması

Merhabalar, bir önceki  yazımda Selection Sort(seçerek sıralama)’dan bahsetmiştim bu yazımda ise Insertion Sort algoritmasını kullanarak sıralama yapmaya çalışacağım. Insertion Sort algoritmasının çalışma mantığı array içerisinde bulunan ilk elemanı atlıyoruz yani en küçük olduğunu varsayıyoruz ve onun sağındaki elemanları da sıralı olduğunu düşünüyoruz ve kontrolünü yapıyoruz. Insertion Sort algoritmasının en iyi durumda ki karışıklığı n olurken en kötü durumda n² ‘dir. Yaptığım örnek program üzerinden anlatmak gerekirse, varsayalım ki bir array’imiz var ve bu array sıralanmamış şu şekilde bir array olsun [3,1,6,5,7,8,2,4].

Array içerisinde ilk olarak birincinin sağında kilerini teker teker kontrol edeceğiz.

3|1,6,5,7,8,2,4 bakıyoruz ki array’in ilk elemanı ikinci elemanından küçük ise yer değişiriyoruz.

1,3|6,5,7,8,2,4 bi sonraki elemanımız büyük sayı olduğu için yer değişimi yapmıyoruz ve diğer elemana bakıyoruz.

1,3,6|5,7,8,2,4 burada kaydırma yapmamız lazım bakıyoruz 5 6 dan küçük olduğu için kaydırıyoruz. ve devam ediyoruz.

1,3,5,6|7,8,2,4 aynı kontrolleri burada da yapıyoruz ve devam ediyoruz.

1,3,5,6,7|8,2,4 gene sayı büyük olduğu için herhangi bir değişim olmuyor.

1,3,5,6,7,8|2,4 şimdi sayı küçük olduğu için kaydırmamız lazım bi kaydırdık 1,3,5,6,7|2,8,4 oldu hala kaydırmamız gerekiyor bu işlemi de while döngüsü içerisinde düzgün konumuna gelene kadar devam ediyor.

1,2,3,5,6,7,8|4 yukarıda ki gibi 4 doğru yerine gelene kadar while döngüsü içerisinde yeri değiştiriliyor.

C kodu:

#include<stdio.h>

void insertionSort(int array[],int size){
	
	for(int i=1;i<size;i++){
		int temp = array[i];
		int j = i-1;
		
		while(j>=0 && temp<array[j]){
			array[j+1] = array[j];
			j -=1;
		}
		array[j+1] = temp;
	}
	
}

void maxToMin(int array[],int size){
	
	for(int i =1;i<size;i++){
		int temp = array[i];
		int j = i-1;
		
		while(j>=0 && temp>array[j]){
			array[j+1] = array[j];
			j = j-1;
		}
		array[j+1]=temp;
	}
}


int main(){
	
	int array[] = {3,1,6,5,7,8,2,4};
	int size = sizeof(array)/sizeof(array[0]);
	
	insertionSort(array,size);
	
	printf("Insertion Sort\n");
	for(int i=0;i<size;i++){
		printf("%d ",array[i]);
	}
	
	maxToMin(array,size);
	printf("\nMax to Min\n");
	for(int i=0;i<size;i++){
		printf("%d ",array[i]);
	}
}

Python kodu:

def maxtomin(array):
    for i in range(1,len(array)):
        temp = array[i]
        j = i-1
        while j>=0 and temp>array[j]:
            array[j+1] = array[j]
            j= j-1
        array[j+1] = temp

array = [3,1,6,5,7,8,2,4]


for i in range(1,len(array)):
    
    temp = array[i]
    j = i-1
    while j>=0 and temp<array[j]:
        array[j+1] = array[j]
        j = j-1
    array[j+1] = temp


print("Insertion Sort")
for i in range(len(array)):
    print("%d " %array[i])
    
maxtomin(array)
print("Max to Min")
for i in range(len(array)):
    print("%d" %array[i])

Soru ve görüşlerinizi e-mail veya yorum olarak belirtirseniz sevinirim.