[알고리즘] 삽입 정렬 (Insertion Sort)

삽입 정렬(Insertion Sort)

삽입 정렬은 배열을 정렬된 부분, 정렬되지 않은 부분으로 나눈 후, 정렬 되지 않은 원소를 순차적으로 비교하면서 정렬이 된 부분에 끼워 넣는 방법입니다. 시간 복잡도는 선택 정렬(Selection Sort)와 동일하게 O(N^2)이다. 각 원소에 적당한 위치 찾는 복잡도: 총 원소의 개수 O(N), 순차적으로 삽입 위치를 찾는 복잡도: O(N)이다. 

그림

여기서는 위 방법을 그림을 통해 설명합니다.

삽입 정렬은 정렬 부분(빨간 점선 박스), 정렬 되지 않은 부분(파란 점선 박스)을 나누고 정렬이 된 부분에 순차적으로 원소를 끼워 넣는 방법입니다. 

1단계에서는 첫 번째 원소 '19'를 정렬된 부분에 끼워 넣습니다. 

2단계에서는 두 번째 원소 '89'를 정렬 부분의 원소와 비교하여 끼워 넣습니다. 

3단계에서도 세 번째 원소 '6'를 정렬 부분의 원소들과 비교하여 제 위치에 끼워 넣습니다.

크기가 N인 배열은 N단계까지 반복하면 정렬된 배열을 획득할 수 있습니다. 

의사코드

이 알고리즘 의사코드는 다음과 같습니다.

insertionSort{
    ary[SIZE]
 
    for i = 1 to SIZE{
        for j = 1 to i-1{
            if(ary[j] > ary[i])
                swap(ary[j], ary[i])
        }
    }
}

예제

- 입력
첫 번째 줄에 원소의 개수

두 번째 줄에 N개의 원소를 갖는 배열의 값

- 출력

삽입 정렬이 수행된 배열의 원소 값을 출력

- 코드

#include <stdio.h>
 
#define SIZE 100
 
#define SWAP(a, b, type) do { \
    type tmp;    \
    tmp = a;    \
    a    = b;    \
    b    = tmp;    \
}while (0)
 
void insertionSort(int ary[], int N) {
    // 배열의 자료형(ary)과 배열의 크기(N)를 
    // 입력받고 삽입 정렬을 수행하는 함수 
    int i;
    int j;
 
    for (i = 0; i < N; i++) {
        for (j = 0; j < i; j++) {
            if (ary[j] > ary[i]) {
                SWAP(ary[i], ary[j], int);
            }
        }
    }
}
void printAry(int ary[], int N) {
    // 배열의 자료형(ary)과 배열의 크기(N)를 
    // 입력받고 배열의 원소를 출력하는 함수 
    int i;
 
    for (i = 0; i < N; i++) {
        printf("%d ", ary[i]);
    }
    printf("\n");
}
int main(void) {
    int ary[SIZE];
    int i;
    int N;
 
    // 배열의 크기를 표준입력으로부터 입력
    scanf("%d", &N);
 
    // 배열의 크기 만큼 반복문을 통해 배열의 원소를 초기화
    for (i = 0; i < N; i++) {
        scanf("%d", &ary[i]);
    }
 
    // 삽입 정렬 함수를 호출하고 배열의 원소를 출력
    insertionSort(ary, N);
    printAry(ary, N);
    //fflush(stdout);
    getchar();
    getchar();
 
    return 0;
}