[C언어 알고리즘] 정렬(3) - 삽입정렬 (Insertion sort)

삽입정렬(Insertion sort)은 선택정렬(Selection sort)와 함께 많이 사용되는 아주 간단한 정렬 방법입니다. 카드 뭉치로 예를 들자면, 이미 정렬된 카드패에 새로운 카드를 다른 항목사이에 끼워넣는 것으로 생각하시면 됩니다.

 

삽입정렬 알고리즘

우선 삽입 정렬의 의사코드(Pseudo code)를 보면 다음과 같습니다.

1. i=1
2. j=i
3. a[j-1] > a[i] 이고 j > 0인 동안
  3.1. a[j] = a[j-1]
  3.2. j--
4. a[j] = a[i]

위 코드를 보면 배열에서 i번째 미만은 이미 정렬된 상태이며 i번째 항을 적절한 위치에 삽입하는 과정을 반복합니다.

 

그림을 통해서 살며보면 우선 다음과 같은 문자 배열이 있다고 가정을 합니다.

 

첫 번째 수행

첫 번째 수행 전

시작은 i가 1인 항인 'e'를 i보다 작은 항들에 삽입시키는 건데, 'e'가 'l'보다 작으므로 'l' 앞에 'e'를 삽입합니다.

첫 번째 수행 후

수행 결과는 배열의 붉은 색 음영으로 된 데이터가 정렬이 된 결과를 얻을 수 있습니다.

 

두 번째 수행

두 번째 수행 전

두 번째 수행은 i=2인 항인 'a'를 이미 정렬이 된 'e', 'l' 리스트에 삽입을 하는 과정인데 'l'과 'e'가 모두 'a'보다 크므로 'a'를 가장 앞에 삽입을 합니다.

두 번째 수행 후

그러면 'a', 'e', 'l'은 정렬된 상태의 결과를 얻을 수 있습니다.

이와 같은 과정을 반복하여 배열의 마지막 항목까지 수행을 합니다.

 

아래는 C언어로 작성한 소스코드입니다.

#include <stdio.h>
#include <string.h>

void print_data(char a[], int n);

void insertion_sort(char a[], int n)
{
    int i, j;
    char t;
    for (i = 1; i< n; i++) {
        t = a[i];
        j = i;
        while(--j >= 0 && a[j] > t)
            a[j+1] = a[j];
        
        a[j+1] = t;
        print_data(a, n);
    }
}

void print_data(char a[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf ("%c ", a[i]);
    }
    printf ("\n");
}

void main (int argc, char *argv[])
{
    char data[] = "learnalgorithm";
    print_data(data, strlen(data));
    insertion_sort(data, strlen(data));
}

실행 결과는 다음과 같습니다.

PS C:\CS> .\insertion_sort.exe
l e a r n a l g o r i t h m 
e l a r n a l g o r i t h m
a e l r n a l g o r i t h m
a e l r n a l g o r i t h m
a e l n r a l g o r i t h m
a a e l n r l g o r i t h m
a a e l l n r g o r i t h m
a a e g l l n r o r i t h m
a a e g l l n o r r i t h m
a a e g l l n o r r i t h m
a a e g i l l n o r r t h m
a a e g i l l n o r r t h m
a a e g h i l l n o r r t m
a a e g h i l l m n o r r t

선택정렬이 비교적 많은 비교와 적은 교환을 한다고 하면, 삽입정렬은 비교적 적은 비교와 많은 교환을 한다고 보면 됩니다. 이번에도 참 쉬운 삽입정렬 이었습니다.