[이취코] ch06-2. 삽입 정렬 (Insertion Sort)

삽입정렬?

특정한 데이터를 적절한 위치에 '삽입'한다

 

선택정렬보다 실행 시간 측면에서 더 효율적이고 선택정렬에 비해 구현 난이도가 높은편이다

특히 삽입정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다

 

삽입정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다

정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다

 

그림으로 보면 이해가 더 쉬울것이니 그림으로 살펴보도록 하자

 

초기 데이터가 다음과 같이 있다

삽입정렬은 두번째 데이터부터 시작한다

첫번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다

 

 

(1)

첫번째 데이터 7은 이미 그 자체로 정렬되어 있다고 생각하고, 두번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다

7의 왼쪽/오른쪽 두 경우가 존재하고 우리는 오름차순으로 정렬할 것이므로 5를 7의 왼쪽에 삽입한다

→ 5 7 9 0 3 5 6 2 4 8

 

 

(2)

이제 세번째 데이터인 9가 어디 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지 (5 왼쪽, 5~7 사이, 7오른쪽)이며

9는 5와 7 모두보다 크기때문에 가만히 둔다

→ 5 7 9 0 3 5 6 2 4 8

 

 

(3) 

이어 0이 어디들어갈지 판단한다. 0은 가장 작기 때문에 5 앞에 삽입한다

 

→ 0 5 7 9 3 5 6 2 4 8

 

이 과정을 반복하면 오름차순으로 정렬이 완료된다

 

이렇게 특정 데이터 앞에 있는 데이터는 이미 정렬이 된 상태로 삽입할 위치만 찾아주면 된다

 

삽입정렬의 특징은, 정렬이 이루어진 원소는 항상 오름차순을 유지하고있고 초록색으로 칠해진 카드들은 어떤 단계든지 항상 정렬된 상태라는 것이다

이러한 특징떄문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다

 

위 그림을 보면 이어 데이터 3을 삽입할 위치를 찾을때 자신보다 작은 0을 만나면 그 자리에서 멈추고 그 위치에 삽입된다

다시말해 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 하나 만났다면 더이상 왼쪽 데이터를 살펴볼 필요가 없다는 것이다

 

 

 

삽입정렬을 코드로 구현하면 (cpp)

#include <iostream>

using namespace std;

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

int main(void) {
    for (int i = 1; i < n; i++) {
        // 인덱스 i부터 1까지 감소하며 반복하는 문법
        for (int j = i; j > 0; j--) {
            // 한 칸씩 왼쪽으로 이동
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
            // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            else break;
        }
    }
    for(int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

이중반복문을 통해 이미 정렬된 데이터를 오른쪽부터 비교하면서

이동 데이터가 더 작으면 한칸 옆으로 이동한다

그렇게 이동하다가 이동 데이터보다 작은 데이터를 만나면 그 자리에 멈춘다 (break)

 

 

삽입정렬의 시간 복잡도

 

선택정렬과 마찬가지로 반복문이 2번 중첩되어 시간복잡도가 O(n^2)라는 것을 알 수 있다

삽입정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 것을 기억하자

최선의 경우 O(n)의 시간복잡도를 가진다

 

따라서 거의 정렬되어있는 상태로 입력이 주어지는 문제라면 삽입정렬을 이용하도록 하자