삽입 정렬

개요

삽입 정렬이란, 새로운 원소를 이전까지 정렬된 원소 사이에 올바르게 삽입시키는 알고리즘이다. 새로운 원소를 올바른 위치에 삽입 시켜나가는 과정을 모든 원소에 대해 수행하면 정렬이 완성된다.

예시

[math]\displaystyle{ N = 8 }[/math]인 다음과 같은 수열을 오름차순으로 정렬한다고 할 때,

arr[idx]	0	1	2	3	4	5	6	7
	3	7	2	1	6	5	4	0

0번째 인덱스에 있는 수는 그 자체로 정렬이 되어있으므로 그 다음 인덱스인 1번 인덱스부터 올바른 위치에 삽입을 시작한다.

arr[idx]	0	1	2	3	4	5	6	7
	3	7	2	1	6	5	4	0

인덱스 1번 이전에 있는 수와 1번을 비교했을 때, 인덱스 0번에 있는 수 3은 인덱스 1번에 있는 수 7보다 작으므로 자리 교환없이 삽입을 끝낸다.

arr[idx]	0	1	2	3	4	5	6	7
	3	7	2	1	6	5	4	0
	↘	↘
	2	3	7

이후, 인덱스 2번에 있는 수를 이전까지 정렬된 수열 [3, 7] 에 삽입한다. 인덱스 2번 이전에 있는 수들과 2번을 비교했을 때, 인덱스 1번에 있는 수 7은 인덱스 2번에 있는 수 2보다 크므로 한자리 뒤로 이동시킨다. 인덱스 0번에 있는 수 3도 인덱스 2번에 있던 수 2보다 크므로 한자리 뒤로 이동시킨다. 이후, 인덱스 2번에 있던 수 2를 제일 앞에 삽입한다.

arr[idx]	0	1	2	3	4	5	6	7
	2	3	7	1	6	5	4	0
	↘	↘	↘
	1	2	3	7

새로운 원소인 인덱스 3번에 있는 수를 이전까지 정렬된 배열 [math]\displaystyle{ [2, 3, 7] }[/math]에 삽입한다. 인덱스 2번에 있는 수 7은 인덱스 3번에 있는 수 1보다 크므로 7을 한자리 뒤로 이동시킨다. 인덱스 1번에 있는 수 3도 인덱스 1번에 있던 수 1보다 크므로 한자리 뒤로 이동시킨다. 인덱스 0번에 있는 수 2도 1보다 크므로 한자리 뒤로 이동시킨다. 마지막으로, 1을 올바른 위치 인덱스 0번에 삽입한다.

arr[idx]	0	1	2	3	4	5	6	7
	1	2	3	7	6	5	4	0
				↘
				6	7

새로운 원소인 인덱스 4번에 있는 수를 이전까지 정렬된 배열 [math]\displaystyle{ [1, 2, 3, 7] }[/math]에 삽입한다. 인덱스 3번에 있는 수 7은 인덱스 4번에 있는 수 6보다 크므로 한자리 뒤로 이동시킨다. 인덱스 3번에 있는 수 3은 인덱스 4번에 있던 수 6보다 작거나 같으므로 비교를 멈추고 6을 3 뒤에 위치시킨다.

arr[idx]	0	1	2	3	4	5	6	7
	1	2	3	6	7	5	4	0
				↘	↘
				5	6	7

새로운 원소인 인덱스 5번에 있는 수 5를 이전까지 정렬된 배열 [math]\displaystyle{ [1, 2, 3, 6, 7] }[/math]에 삽입한다. 인덱스 4번에 있는 수 7은 인덱스 5번에 있는 수 5보다 크므로 한자리 뒤로 이동시킨다. 인덱스 3번에 있는 수 6도 인덱스 5번에 있던 수 5보다 크므로 한자리 뒤로 이동시킨다. 인덱스 2번에 있는 수 3은 5보다 작거나 같으므로 비교를 멈추고 5를 3 뒤에 삽입한다.

arr[idx]	0	1	2	3	4	5	6	7
	1	2	3	5	6	7	4	0
				↘	↘	↘
				4	5	6	7

새로운 원소인 인덱스 6번에 있는 수 4를 이전까지 정렬된 배열 [math]\displaystyle{ [1, 2, 3, 5, 6, 7] }[/math]에 삽입한다. 인덱스 5번에 있는 수 7, 인덱스 4번에 있는 수 6, 인덱스 3번에 있는 수 5는 모두 4보다 크므로 한자리 씩 뒤로 이동한다. 인덱스 2번에 있는 수 3은 인덱스 6번에 있던 수 4보다 작거나 같으므로 비교를 멈추고 인덱스 2번의 뒤에 4를 삽입한다.

arr[idx]	0	1	2	3	4	5	6	7
	1	2	3	4	5	6	7	0
	↘	↘	↘	↘	↘	↘	↘
	0	1	2	3	4	5	6	7

코드

#include <iostream>
using namespace std;

int N = 8;
int arr[8] = {1, 2, 3, 6, 7, 5, 4, 0};

void insertionSort() {

    for (int i=1; i<N; i++) {
        int key = arr[i];
        int j;
        for (j=i-1; j>=0 && arr[j] > key; j--)
            arr[j+1] = arr[j];
        arr[j+1] = key;
    }
}

void printarr() {

    for (int i=0; i<N; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
}

int main() {

    insertionSort();
    printarr();
    return 0;
}

/*output: 0 1 2 3 4 5 6 7*/

시간 복잡도

최선의 경우

모든 원소가 이미 정렬이 되어있는 경우, 외부 루프를 [math]\displaystyle{ N-1 }[/math]번 도는 동안 비교 연산은 1번씩 수행된다.

따라서 최선의 경우, [math]\displaystyle{ T(n) = (N-1)*1 }[/math], [math]\displaystyle{ O(n) = n }[/math]이 된다.

최악의 경우

모든 원소가 역순으로 정렬되어 있는 경우, 외부 루프를 [math]\displaystyle{ N-1 }[/math]번 도는 동안 비교연산은 [math]\displaystyle{ 1, 2, ... , (N-1) }[/math]번 수행된다.

따라서 최악의 경우, [math]\displaystyle{ T(n) = 1+2+...+(N-1) = (N-1)*N/2 }[/math], [math]\displaystyle{ O(n) = n^2 }[/math]이 된다.

안정성과 제자리성

삽입정렬을 구현할 시, 비교대상의 원소가 새로운 원소보다 클 때만 한자리 뒤로 이동시키므로 동일한 원소의 우선순위는 처음 정렬과 동일하게 유지된다. 따라서 삽입정렬은 안정정렬(Stable sort)이다. 또한, 삽입정렬은 정렬해야 하는 배열 외 추가 메모리를 거의 사용하지 않으므로 제자리 정렬(In-place sort)이다.

CC BY로 가져옴