삽입정렬(insertion sort)

삽입정렬(insertion sort) : 삽입할 위치를 찾는 정렬

---

점진적으로 범위를 늘려가며 범위내에서 정렬, 1번째 인덱스부터 시작

pseudocode

삽입정렬(base : 배열시작주소 , n : 배열요소 개수)
	반복(i : 1 -> n) //위치선택
		key = base[i]
		반복(j : i-1 -> 0 && base[j] > key) //앞부분은 정렬이 되어있기 때문에 확인X
			base[j+1] = base[j]  //앞부분의 배열 1칸씩 뒤로 이동
		base[j+1] = key

best case 시간복잡도 : $O(n)$ (배열이 어느정도 정렬된 경우)

worst case 시간복잡도 : $O(n^2)$

안정성 : 안정

장점 : 어느정도 정렬된 경우 매우 효율적

단점 : 많은 이동(1칸씩 밀기), record가 클수록 불리

실제코드

#include <stdio.h>

int main(int argc, const char * argv[]) {

    int arr[20] = {
        1, 2, 3, 4, 5, 6, 1, 8, 9, 10,
        11, 1, 13, 14, 15, 6, 17, 18, 19, 20
    };
    int n = sizeof(arr)/sizeof(int);
    int count = 0;
    int i,j,key;
    
    
    for(i = 1 ; i <  n ; i ++){
        key = arr[i];
        for(j = i-1 ; j >= 0 && arr[j]> key ; j--){
            arr[j+1] = arr[j];
            count++;
        }
        arr[j+1] = key;
    }

    
    for (int k = 0 ; k < n ; k++){
        printf("%d ",arr[k]);
    }
   printf("\nn^%d",count/n);
    return 0;
}