[Algorithm] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

: 각 숫자를 적절한 위치에 삽입하는 정렬 방법으로, 정렬 대상 숫자를 기준으로 앞의 원소들은 이미 정렬이 되어 있다고 가정한다.

적절한 위치?
선택 정렬(Selection Sort)와 버블 정렬(Bubble Sort)은 무조건 위치를 변경하는 정렬 방식으로, 이미 정렬이 이루어져 있는 상황에서도 반드시 반복을 수행한다.
반면에, 삽입 정렬(Insertion Sort)은 필요할 때만 위치를 변경한다.

 

Insertion Sort Sequence

정렬 DATA

반복 1

반복 2

반복 3

반복 4

반복 5

반복 6

반복 7

반복 8

반복 9

 

코드

#include <iostream>
using namespace std;

int main(void){
    int i, j, tmp;
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<9;i++){
        j = i;
        while(arr[j] > arr[j+1]){
            tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            j--;
        }
    }

    for(i=0;i<10;i++)
        cout << arr[i] << " ";
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

 

시간 복잡도 

최악의 경우 : 10 + 9 + 8 + 7 + ... + 1

=> O(N*N)

 

Insertion Sort(삽입 정렬)은 특정 조건에서는 속도가 빠르다.

특정 조건?

만약 Insertion Sort(삽입 정렬)을 이용해 아래 배열을 정렬한다면?

정렬 DATA

반복 1 - 8

반복 9

→ 거의 정렬된 상태의 배열의 경우 효율적인 정렬 알고리즘으로, 자원 소모가 적으며 연산 자체도 적게 수행한다.
    (= Quick Sort / Heap Sort / Merge Sort와 비슷하거나 더 빠르게 정렬 수행)

∴ Insertion Sort(삽입 정렬)는 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘 중 가장 강력한 알고리즘이다.