[자료구조] 정렬 #3 - 삽입정렬(Insertion Sort)

삽입정렬이란?

: 앞에서부터 이미 정렬된 배열 부분과 비교하여 맞는 위치에 삽입하는 정렬

- 앞에있는 값부터 key가 되어 올바른 위치에 삽입된다.

- 첫번째 key값은 두번째 index부터

 

시간복잡도

Best: 이미 정렬되어 있는 경우 O(n)

Worst: 역순으로 정렬되어 있는 경우 O(n^2)

 

구현 (오름차순)

void insertionSort(int a[], int size) {
	int min;
    
    for(int i=1; i<size; i++){
    	int key = a[i];
        int j;
        
        for(j=i-1; j>=0; j--){
            if(a[j] > key){
            	a[j+1]=a[j];
            }
            else{
            	break;
            }
        }
        a[j+1] = key;
    }
}

 

출처

gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html