Insertion Sort ( 삽입 정렬 )

* 오름차순을 기준으로 정렬한다.

## 개념 요약 ##

• 손 안의 카드를 정렬하는 방법과 유사하다.
  • 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입하는 방법.
  • 새로 삽입될 카드의 수 만큼 반복하게 되면, 전체 카드가 정렬됨.
• 배열의 모든 요소를, 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 해서, 자신의 위치를 찾아 삽입해 완성하는 알고리즘.
• 매 순서마다 해당 원소를 삽입 할 수 있는 위치를 찾아 해당 위치에 넣는다.

## 구체적인 개념 ##

• 삽입 정렬은 2번째 값 부터 시작해, 그 앞의 값들과 비교하여 삽입할 위치를 지정한 후 값을 뒤로 옮기고, 지정한 자리에 값을 삽입해 정렬하는 알고리즘이다. 
• 즉, 2번째 값은 첫 번째 값, 3번째 값은 2, 1번째 값, 4번째 값은 3,2,1 값과 비교한 후 값이 삽입될 위치를 찾는다. 값이 삽입될 위치를 찾았다면, 그 위치에 값을 삽입하기 위해 값을 한 칸씩 뒤로 이동시킨다. 
• 처음 Key 값은 2번째 값부터 시작한다. ! 

음 ... 결국 걍 똑같은 정렬인데, 선택 정렬은 swap이고, 이건 메모리를 추가로 써야되는 (옮길 값을 새로 저장할 곳이 필요한..?) 정렬인건가.... 

## Insertion Sort 의 특징 ##

• 장점
  • 안정적인 정렬 방법?
  • 값의 수가 (배열의 수가) 적을 경우, 알고리즘이 간단하므로 , 다른 복잡한 정렬 방법보다 유리 하다.
  • 대부분의 값이 이미 정렬되어 있는경우에 매우 효율적이다.
• 단점
  • 비교적 많은 값의 이동을 요구한다.
  • 값의 수가 많고, 값의 크기가 클 경우에는 적합하지 않다.

## Insertion Sort 의 시간 복잡도 ## 

• 최선의 경우
  • 비교 횟수
    • 이동없이 1번에 완료, 외부 루프 : n-1번
  • Best T(n) = O(n)
• 최악의 경우 ( 입력 자료가 역순일 경우 )
  • 비교 횟수 
    • 외부 loop 안의 각 반복마다 i번의 비교 수행
    • 외부 loop : (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)
  • 교환 횟수
    • 외부 loop 의 각 단계마다 (i+2)번의 이동 발생
    • n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O(n^2)
  • Worst T(n) = O(n^2)

 

소스코드 ~ 

#include <stdio.h>
#define MAX_SIZE 5

void insertion_sort(int list[], int n) {
    int i, j, key;
    for ( i=1; i < n; i++) { // i = 2
        key = list[i];
        for(j = i-1; j >= 0 && list[j] > key; j--) { // 1, 0
            list[j+1] = list[j];
        }
        list[j+1] = key;
    }
}   

void main() {
    int i;
    int n = MAX_SIZE;
    int list[5] = {8,5,6,2,4};
    
    insertion_sort(list, n);
    
    for(i = 0; i < MAX_SIZE; i++) {
        printf("%d, ", list[i]);
    }   
    printf("\n");
}