삽입 정렬(Insertion Sort)

개요

삽입 정렬은 앞선 선택 정렬, 버블 정렬과 같이 O(N^2)의 시간 복잡도를 가지는 알고리즘이다. 하지만 이 세 가지 알고리즘 중에서는 가장 효율적인 알고리즘이다. 그 이유에 대해 한번 알아보겠다.

삽입 정렬

"3 1 2 9 8 4 7 10 5 6
위 숫자들을 오름차순으로 정렬하라."

삽입 정렬은 이미 앞선 인덱스들이 정렬되어 있다고 가정하고 그 부분과 비교하여 알맞은 위치에 삽입하는 알고리즘이다. 정렬된 부분에서 자신보다 큰 수는 뒤로 밀어낸다고 생각하면 이해하기 좋다. 이는 필요한 경우에만 스왑을 하기 때문에 모든 경우에 스왑을 했던 선택 정렬과 버블 정렬보다는 효율적이라 할 수 있다. 만약 이미 거의 정렬된 상태라면 이 알고리즘은 위와 같은 이유로 가장 강력한 알고리즘이 될 수 있다.

수행 과정

1. [3, 1, 2, 9, 8, 4, 7, 10, 5, 6]에서 1번째 인덱스인 '1'은 0번째 인덱스인 '3'과 비교하여 큰 수를 뒤로 밀어내고 그 자리에 삽입된다.
2. [1, 3, 2, 9, 8, 4, 7, 10, 5, 6]에서 2번째 인덱스인 '2'는 앞서 정렬된 [1, 3]과 비교하여 '3'을 밀어내고 그 자리에 삽입된다.
3. [1, 2, 3, 9, 8, 4, 7, 10, 5, 6]에서 3번째 인덱스인 '9'는 앞서 정렬된 [1, 2, 3]과 비교하여 가장 큰 수이므로 변화가 없다.
4. [1, 2, 3, 9, 8, 4, 7, 10, 5, 6]에서 4번째 인덱스인 '8'은 앞서 정렬된 [1, 2, 3, 9]와 비교하여 '9'를 밀어내고 '3'의 뒤에 삽입된다.
5. 이와 같은 과정을 모든 숫자를 배치할 때까지 반복한다.

시간 복잡도

첫 번째 인덱스부터 마지막 인덱스까지 각각 앞서 정렬된 부분과 비교를 하기 때문에 O(N^2)의 시간 복잡도를 가진다.

코드 구현

삽입 정렬을 코드로 구현하면 다음과 같다.

#include <iostream>

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

int main(){
    int temp;

    for (int i=1; i<10; i++){
        int temp = array[i];
        int j=i;
        while (array[j-1] > temp){
            array[j] = array[j-1];
            j--;
            if (j<1) break;
        }
        array[j] = temp;
    }

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

    return 0;
}
//array : 1 2 3 4 5 6 7 8 9 10

Reference

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221226806398&navType=by
https://jongmin92.github.io/2017/11/06/Algorithm/Concept/basic-sort/