[알고리즘] 삽입 정렬 (Insertion Sort)

알고리즘

삽입 정렬(Insertion Sort)의 알고리즘은 다음과 같습니다.

• 두 번째 원소부터 시작해 해당 원소가 이전 원소들과 비교해 어디에 삽입할지 결정
• 이를 마지막 원소까지 반복합니다

예를 들어 다음 배열을 정렬해 보겠습니다.

 

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

 

1) 두 번째 원소인 6을 이전 원소들인 4와 비교해 어디에 삽입할지 결정합니다. 6은 4보다 크니 두 번째 상자에 삽입합니다.

□ 4 □ ◀ 6을 어디에 삽입?

 

[6 삽입] ↓

□    4    ■

 

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

 

2) 세 번째 원소인 8을 이전 원소들인 4, 6과 비교해 어디에 삽입할지 결정합니다. 8은 6보다 크니 세 번째 상자에 삽입합니다.

□ 4 □ 6 □ ◀ 8을 어디에 삽입?

 

□  4  □  6  ■ 

 

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

 

3) 네 번째 원소인 1을 이전 원소들인 4, 6, 8과 비교해 어디에 삽입할지 결정합니다. 1은 4보다 작으니 첫 번째 상자에 삽입합니다.

□ 4 □ 6 □ 8 □ ◀ 1을 어디에 삽입?

 

↓ [1 삽입]         

■ 4 □ 6 □ 8 □

 

[1 , 4 , 6 , 8 , 3 , 5 , 7 , 2 , 10 , 9]

4) 다섯 번째 원소인 3을 이전 원소들인 1, 4, 6, 8과 비교해 어디에 삽입할지 결정합니다. 3은 1보다 크고 4보다 작으니 두 번째 상자에 삽입합니다.

□ 1 □ 4 □ 6 □ 8 □ ◀ 3을 어디에 삽입?

 

↓ [3 삽입]   

□ 1 ■ 4 □ 6 □ 8 □

 

[1 , 3 , 4 , 6 , 8 , 5 , 7 , 2 , 10 , 9]

 

5) 여섯 번째 원소인 5를 이전 원소들인 1, 3, 4, 6, 8과 비교해 어디에 삽입할지 결정합니다. 5는 4보다 크고, 6보다 작으니 세 번째 상자에 삽입합니다.

□ 1 □ 3 □ 4 □ 6 □ 8 □ ◀ 5를 어디에 삽입?

 

[5 삽입] ↓

□  1  □  3  □  4  ■  6 □ 8 □

 

[1 , 3 , 4 , 5 , 6 , 8 , 7 , 2 , 10 , 9]

 

위의 알고리즘을 10번 반복하면 배열은 다음과 같이 정렬되게 됩니다

[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]

---

시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)입니다.

 

위의 예제를 예로 들어 왜 버블 정렬의 시간 복잡도가 O(N^2)인지에 대해 설명하겠습니다.

 

첫 번째 단계에서 6을 4와 비교해 삽입할 위치를 결정합니다. 비교 횟수 - 1번

 

두 번째 단계에서 8을 4, 6과 비교해 삽입할 위치를 결정합니다. 비교 횟수 - 2번

 

...

 

이렇게 10개의 숫자를 정렬하기 위해 비교한 횟수는 1번 + 2번 + ... + 9번입니다.

1부터 N-1까지의 합 공식을 적용하면 다음과 같습니다.

 

(N - 1) x N / 2

 

즉, 삽입 정렬의 시간 복잡도는 O(N^2)입니다.

---

삽입 정렬 vs 선택 정렬 vs 버블 정렬

선택 정렬에 대한 설명은 다음 포스팅에서 확인할 수 있습니다.

 

https://programforlife.tistory.com/30?category=915326

[알고리즘] 선택 정렬 (Selection Sort)

 

 

버블 정렬에 대한 설명은 다음 포스팅에서 확인할 수 있습니다.

 

https://programforlife.tistory.com/31?category=915326

[알고리즘] 버블 정렬 (Bubble Sort)

 

삽입 정렬, 선택 정렬, 버블 정렬의 시간 복잡도는 모두 O(N^2)입니다.

 

하지만, 삽입 정렬이 선택 정렬, 버블 정렬에 비해 훨씬 효율적입니다. 이유는 다음과 같습니다.

 

삽입 정렬은 비교하기 전에 앞의 원소들은 이미 정렬되어있다고 가정하고, 알맞은 위치를 찾아갑니다.

 

삽입 정렬은 필요할 때에만 삽입을 진행합니다.

 

즉, 전체 비교를 하지 않습니다.

 

하지만 버블 정렬과 선택 정렬은, 원소들이 정렬되어있어도 반드시 비교 알고리즘을 수행합니다.

 

삽입 정렬이 가장 효율적인 상황은, 대부분 정렬된 배열인 경우입니다.

 

이때는 그 어떤 정렬 알고리즘보다 좋은 효율성을 갖고 있습니다.

---

소스코드

위의 내용을 바탕으로 C++로 소스코드를 작성해 보겠습니다.

 

#include <bits/stdc++.h>
using namespace std;

int main(void){
    int j, temp;

    //정렬할 배열
    int array[10] = {4,6,8,1,3,5,7,2,10,9};

    //배열의 크기 만큼 반복
    for(int i=0;i<10;i++) {
        j = i;
        //array[j] > array[j+1] 인 경우, 즉 배열이 정렬이 안되어있을 경우에만 정렬!
        while(j >= 0 && array[j] > array[j+1]) {
            //정렬 될때까지 Swap 진행
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            j--;
        }
    }

    for(int i=0;i<10;i++) {
        cout << array[i] << " ";
    }

    return 0;
}

 

위 코드를 실행시켜 보면 다음과 같이 정렬된 배열을 확인할 수 있습니다.