삽입 정렬(Insertion Sort)이란?

개념

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

즉, 삽입 정렬은 2번째 요소부터 시작하여 앞 쪽과 비교하여 위치를 지정한다.

삽입 정렬에서는 정렬할 자료가 2개의 부분집합인 S(Sorted)와 U(Unsorted)로 나뉘어져 있다.

정렬된 앞부분의 요소들은 부분집합 S이고, 정렬되지 않은 나머지 요소들은 부분집합 U이다.

부분집합 U에서 요소를 하나씩 꺼내서 이미 정렬된 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.

따라서 S의 요소는 1개씩 늘리고, U의 요소는 1개씩 줄인다.

이렇게 U의 요소를 모두 S에 삽입하여 공집합이 되면 삽입 정렬이 끝난다.

 

 

 

과정

삽입 정렬

시작 지점이 있으면 그 앞의 정렬된 부분집합인 S들의 요소들과 비교하게 되는데

만약 S의 요소가 크다면 그 요소의 위치를 +1해주는걸 반복하다가, S의 요소가 작을 때 [현재 비교한 위치 +1]번방에 삽입하게 된다.

 

배열 [67, 10, 32, 5, 16] 이 있을 때의 과정은 아래 그림처럼 동작하게 된다.

삽입 정렬 - 그림 설명

1회전

첫 시작으로 2번째 원소인 10을 기준으로 앞의 원소들과 비교한다.

10과 67을 비교하여 10이 작으므로 67의 위치는 +1해주고, 그 자리에 삽입한다.

2회전

3번째 원소인 32를 기준으로 비교한다.

첫번째로 67과 비교하여 더 작으므로 67의 위치를 +1 해주고, 그 다음 원소인 10과 비교한다.

10보다는 크므로 그 앞에 값을 삽입한다.

3회전

4번째 원소인 5를 기준으로 비교한다.

첫번째로 67과 비교하여 더 작으므로 67의 위치를 +1 해주고, 그 다음 원소인 32와 비교한다.

32보다 작으므로 32의 위치를 +1 해주고, 그 다음 원소인 10과 비교한다.

10보다 작으므로 10의 위치를 +1 해주고, 제일 앞에 값을 넣는다.

4회전

5번째 원소인 16을 기준으로 비교한다.

첫번째로 67과 비교하여 더 작으므로 67의 위치를 +1 해주고, 그 다음 원소인 32와 비교한다.

32보다 작으므로 32의 위치를 +1 해주고, 그 다음 원소인 10과 비교한다.

10보다 크므로 그 앞에 값을 넣는다.

 

정렬이 안된 부분집합 U가 없으므로(공집합이므로) 전부 정렬이 됐다.

 

 

 

구현(C++)

#include <stdio.h>
int main()
{
    int n, i, j, temp, a[5];
    scanf("%d", &n);        // 데이터 개수를 n에 입력받는다.
    for (i = 0; i < n; i++) // 데이터 개수만큼 값을 a[]에 입력받는다.
    {
        scanf("%d", &a[i]);
    }
    // 삽입 정렬 시작
    for (i = 1; i < n; i++) // 첫 시작은 2번째부터니 배열 인덱스 a[1]번부터 시작
    {
        temp = a[i];                 // 삽입 값을 temp 변수에 저장
        for (j = i-1; j >= 0; j--) // i-1번부터 처음까지 하나씩 비교하면서 넣으므로
        {
            if (a[j] > temp) // 비교값이 더 크면 한칸씩 당긴다.
            {
                a[j+1] = a[j];
            }
            else // 비교값이 더 작으면 삽입할 곳을 찾았으므로 멈춘다.
                break;
        }
        a[j+1] = temp; // 삽입할 곳에 값을 넣는다.
    }
    // 삽입 정렬 끝났으므로 출력
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

 

 

 

시간 복잡도

최악일 경우 시간 복잡도 O(n^2)를 가진다.

최선(최적)일 경우 시간 복잡도 O(n)을 가진다.

 

 

 

정렬 비교

같은 시간 복잡도 O(n^2)인 선택 정렬과 버블 정렬과 비교하면 성능적으로 우수하다.