삽입 정렬(Insertion Sort)

삽입 정렬

정렬을 하다 보면 배열 안의 데이터들을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다. 삽입 정렬은 정렬되지 않은 데이터들 중 가장 앞의 데이터를 정렬된 부분에서의 자기 위치를 찾아 정렬하는 방법입니다.

정렬 과정

길이가 6인 정수형 배열({3, 1, 4, 4, 6, 5})을 정렬해봅시다. 먼저 3을 정렬하려면 정렬된 부분과의 대소 비교를 통해 자기 위치를 찾아야 합니다. 하지만 지금은 정렬 시작 단계이기 때문에 정렬된 부분이 없습니다. 따라서 실질적인 삽입 정렬의 시작은 두 번째 원소인 '1'에서부터 시작하고 3은 정렬된 부분으로 포함시킵니다.

정렬되지 않은 원소들 중 가장 앞인 '1' 원소의 위치를 찾기 위해 정렬된 부분의 '3'과 비교합니다. 1이 3보다 작으므로 3과 1의 위치를 바꿉니다.

그 다음 원소 '4'를 정렬된 부분의 1, 3과 대소 비교를 해봅니다. 4는 3보다 큰 수이기 때문에 위치는 현재 위치와 동일합니다.

삽입 정렬 1

다음 4를 정렬하기 위해 정렬된 부분의 1, 3, 4와 비교를 합니다. 4가 제일 큰 숫자이기 때문에 이 4도 위치가 그대로입니다.

다음은 6을 정렬하기 위해 정렬된 부분의 1, 3, 4, 4와 비교를 진행합니다. 6이 가장 큰 숫자이기 때문에 6의 위치는 바뀌지 않습니다.

마지막으로 5를 정렬하기 위해 정렬된 부분의 모든 원소와 비교를 진행합니다. 5는 4보다 크고 6보다 작으므로 4와 6 사이에 5를 삽입합니다. 이렇게 삽입 정렬은 끝납니다.

삽입 정렬 2

삽입 정렬 코드 (C++)

#include <iostream>
using namespace std;

void insertionSort(int[], int);

int main()
{
    int myArray[6] = {3, 1, 4, 4, 6, 5};
    insertionSort(myArray, 6);
    return 0;
}

void insertionSort(int arr[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int value = arr[i];
        int idx = i;
        for (int j = i - 1; j >= 0; j--)
        {
            if (arr[j] > value)
            {
                arr[j + 1] = arr[j];
                idx = j;
            }
            else
            {
                break;
            }
        }
        arr[idx] = value;
    }
}

처음부터 정렬된 배열로 삽입 정렬을 진행할 경우 처음 (n - 1) 번의 비교만 진행하면 되므로 best case에 대해 O(N) 만큼 걸리고 역순으로 정렬된 배열을 삽입 정렬할 경우 n(n - 1) / 2번의 비교를 진행해야 하므로 worst case에 대해 O(N**2) 만큼 걸립니다. 삽입 정렬을 진행하는 과정에서 value, idx, i, j의 변수만을 사용했기 때문에 메모리 복잡도는 O(1)이라 할 수 있습니다.

삽입 정렬은 주어진 배열 안에서 정렬이 이루어지기 때문에 In-place 알고리즘이고 크기가 같은 원소의 순서는 정렬이 진행되어도 변하지 않기 때문에 stable 한 정렬 알고리즘입니다.