삽입정렬(Insertion Sort) 개념/시간복잡도/Stable/In-place

삽입정렬에 대한 이해

- 삽입정렬이란, 새로운 원소를 이전까지 정렬된 원소 사이에 올바르게 삽입시키는 알고리즘이다.

- 새로운 원소를 올바른 위치에 삽입시켜나가는 과정을 모든 원소에 대해 수행하면 정렬이 완성된다.

 

 

 

N = 8인 다음과 같은 수열을 오름차순으로 정렬해보자.

 

 

 

 

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

 

 

 

 

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

 

 

 

 

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

 

 

 

 

 

 

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

 

 

 

 

 

 

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

 

 

 

 

 

 

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

 

 

 

 

 

 

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

 

 

 

 

 

 

마지막 원소인 인덱스 7번에 있는 수 0을 이전까지 정렬된 배열 [1, 2, 3, 4, 5, 6, 7]에 삽입하자. 인덱스 0, 1, 2, 3, 4, 5, 6번에 있는 수들은 인덱스 7번에 있는 수 0보다 크므로 한자리씩 뒤로 옮겨진다. 인덱스 0번에 있는 수 1을 마지막으로 옮긴 뒤 0을 제일 앞쪽에 삽입하면 배열의 모든 원소가 오름차순으로 정렬된다.

 

 

 

코드

#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*/

 

 

 

삽입정렬의 시간복잡도

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

따라서 최선의 경우, Best T(n) = (N-1)*1

O(n) = n 이 된다.

 

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

따라서 최악의 경우, Worst T(n) = 1+2+...+(N-1) = (N-1)*N/2

O(n) = n^2 이 된다.

 

 

 

안정성 & 제자리성

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