[Algorithm] 삽입정렬

첫 key 값은 [1]번째 인덱스로 하여, 앞쪽(왼쪽)에 있는 정렬과 값을 비교하여 삽입하는 정렬이다.

 

EX)

2,5,3,1,7 [기본 배열]

2,5,3,1,7 

2,3,5,1,7 [교환] 

1,2,3,5,7 [교환] 

1,2,3,5,7

 

#include <stdio.h>
# define LEN 5
 
void insertionSort(int* arr){
  int i, j, key;
 
  for(i=1; i< LEN; i++){
    key = arr[i]; 
    
    // 삽입될 숫자 i번째 정수를 key 변수로 복사
 
    for(j=i-1; j>=0 && arr[j]>key; j--){ 
      arr[j+1] = arr[j];
    }
 // i-1부터 역순으로 조사, j값은 음수가 아니어야 함
 // key 값보다 배열에 있는 값이 크면 j번째를 j+1로 이동 
 
 
    arr[j+1] = key; // j+1에 key 삽입 
  }
}
 
int main(){
    int arr[LEN] = {7,5,1,4,3};
    int i;
    printf("정렬 전 : ");
    for(i=0; i<5; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    insertionSort(arr);
    printf("정렬 후 : ");
    for(i=0; i<5; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");    
    
    return 0; 
}

시간복잡도 O(n^2)