[Data Structure] 삽입 정렬(insertion sort)

---

삽입 정렬

 

 

차례에 해당하는 수를 앞쪽 올바른 자리에 삽입하는 정렬 방식이다. 이미 정렬되어 있다면 정렬된 것을 확인하고 정렬이 종료된다는 장점이 있다.

정렬은 두번째 자리의 값부터 확인한다. 두번째 자리의 값의 바로 앞 값이 자신보다 크다면 그 값을 교환한다. 그 후 세번째 자리의 값을 선택하여 자신의 앞의 값과 비교하고 자신보다 크다면 교환한다. 만약 교환되었다면 다시 자신의 앞의 값과 비교하고, 크다면 교환한다. 이를 끝까지 반복하면 정렬이 완료된다.

따라서 만약 자신의 앞의 값이 자신보다 작다는 것이 확인된다면 정렬되어 있다는 뜻이기 때문에 따로 교환이 일어나지 않고 넘어간다. 즉 이미 정렬되어 있다면 모든 값이 정렬되어 있다는 것을 확인하고 정렬 알고리즘이 종료되기 때문에 버블 정렬, 선택 정렬이 정렬 상태와 관련없이 $ \mathcal{O}(n^2) $ 의 시간복잡도를 가지는 것과 다르게 자료가 완벽히 정렬되어 있다면 $ \mathcal{O}(n) $ 의 시간복잡도를 가진다.

단 삽입이 일어날 때 배열의 전체 값을 밀어주어야 하기 때문에 많은 이동이 필요하고, 따라서 레코드가 클 경우 불리하다는 단점이 있다.

그럼에도 순서대로 이동하기 때문에 안정된 정렬이라는 점과 정렬된 상태에서 효율적이라는 장점 때문에 버블 정렬, 선택 정렬과 달리 실제로도 사용할만한 정렬이다.

 

---

예시

 

예를 들어 위와 같은 리스트를 정렬한다고 해보자.

먼저 위와 같이 두번째 값을 선택하고 그 앞의 값과 비교한다. 비교대상인 9가 더 크다.

그러므로 위와 같이 교환한다.

가장 처음 선택한 수가 가장 앞에 도달하였으므로 내부 루프에서의 정렬은 종료된다. 이렇게 앞 두개의 임시 정렬이 끝났다.

이번에는 세번째 값을 선택하고, 자신의 앞 값과 비교한다. 역시 비교대상이 더 크다.

그러므로 교환한다.

다시 다신의 앞 값과 비교한다.

비교대상이 더 크므로 교환한다.

세번째까지 임시 정렬이 끝났다.

같은 방식으로 정렬하다가 앞 값이 더 작다면 그대로 임시 정렬을 종료한다.

그렇다면 위와 같이 정렬된다.

이 과정을 계속 반복하면 아래와 같이 정렬이 끝난다.

총 두 개의 루프가 돌아가는데, 밖의 루프는 고정이지만, 안의 루프, 즉 위에서 임시 정렬하는 루프는 자신의 앞 값이 자신보다 클 때는 동작하지 않기 때문에 버블 정렬, 선택 정렬과 달리 가변적으로 작동한다. 따라서 앞서 설명한 것과 같이 정렬되어 있는 상태라면 정렬되어 있는 것을 확인하고 종료되기 때문에 시간복잡도가 $ \mathcal{O}(n) $ 이고, 반대로 반대로 정렬되어 있는 최악의 경우 외부 루프, 내부 루프가 모두 처음부터 끝까지 동작하기 때문에 $ \mathcal{O}(n^2) $ 의 시간복잡도를 가진다.

 

---

구현 | C

 

void insertion_sort(int list[], int n) {
    for (int i = 1; i < n; i++) {
        int key = list[i];
        for (int j = i - 1; j >= 0 && list[j] > key; j--) {
            list[j+1] = list[j];
        list[j+1] = key;
    }
}