[C/C++] 삽입 정렬(Insertion Sort)

 삽입 정렬은 배열의 모든 요소를 순서대로 비교하고 앞서 규칙에 맞게 정렬된 배열 사이, 적절한 위치에 요소가 삽입되는 정렬 알고리즘이다. 삽입 정렬의 기본 규칙은 이렇다.

1. 비교하고자 하는 배열 요소를 지정하고 (보통 두 번째 요소) 그 이전의 값과 비교한다.

2. 오름차순, 내림차순의 기준에 따라 값을 교환한다.

3. 한번 이상 교환된 구간은 그 구간에 한하여 정렬되어있다.

4. 비교해야할 값이 더 이상 없거나 배열의 끝에 다다랐을 때 종료한다.

 

 삽입 정렬은 최악의 경우 O(N^2), 최선의 경우 O(N)의 시간 복잡도를 가진다. 최악의 경우는 정렬이 역으로 되어있는 경우이고 최선의 경우는 이미 정렬이 되어있는 경우에는 단 하나의 교환 처리가 일어나지 않아 O(N)의 시간 복잡도를 가지게 된다.

삽입 정렬은 안정 정렬(Stable Sort)이다. 안정 정렬이란 같은 값을 가진 요소들이 있을 때 이 요소들의 순서가 뒤바뀌지 않고 정렬된다는 의미다. 예를 들어 [1, 5(1), 4, 5(2), 6](괄호는 같은 값의 순서)라는 요소를 가진 배열이 있다고 가정할 때 오름차순으로 정렬할 경우 [1, 4, 5(1), 5(2), 6]처럼 같은 값의 순서가 유지된다는 의미다. 이처럼 값의 순서를 지켜주는 정렬 방식을 안정 정렬(Stable Sort)이라고 하며 그 반대의 경우에는 불안정 정렬(Unstable Sort)이라고 부른다.

 

 아래 코드는 입력받은 N개의 값을 배열에 저장해 내림차순으로 삽입 정렬한 케이스이다.

오름차순의 경우에는 key값과 비교하는 부분에서 부등호만 반대로 해주면 된다.

#include <iostream>

void swap(int* arr, int left, int right)
{
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

int main()
{
    int n;
    std::cin >> n;
    int* arr = new int[n];

    for (int i = 0; i < n; ++i)
        std::cin >> arr[i];

    // Insertion Sort
    for (int i = 1; i < n; ++i)
    {
    	// 비교할 값을 보관한다.
        int key = arr[i];
        int j = i - 1;
        // 보관한 값보다 작은 경우에 값을 밀어줘야 하기 때문에
	// 반복적으로 값을 밀어주고 보관한 값보다 큰 값이 나오거나 j가 음수가 될 경우
        // 빠져나와 보관한 값을 적절한 위치에 삽입한다.
        while (j >= 0 && arr[j] < key)
            arr[j + 1] = arr[j--];
        arr[j + 1] = key;
    }

    for (int i = 0; i < n; ++i)
        std::cout << arr[i] << '\n';
    
    delete[] arr;
    return 0;
}