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

삽입 정렬 개념

삽입 정렬은 선택정렬과 유사하지만 좀 더 효율적인 정렬 알고리즘이다.
삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 방식이다.

삽입정렬의 경우, 선택정렬과 달리 이미 정렬이 되어있는 상태라면 비교하여 스왑할 필요가 없을 것이다.(처음부터 값이 있어야 할 자리를 판단, 선택정렬은 값의 Min or Max를 우선적으로 찾음)
반대로 정렬이 되어있다면(최악의 경우) 비교해가면서 스왑하므로 선택정렬과 같은 연산(시간의 복잡도)을 할 것이다.

삽입 정렬의 장단점

장점

• 알고리즘이 단순하다.
• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.
• Selection Sort나 Bubble Sort과 같은 $O(n^2)$의 시간 복잡도를 갖는 알고리즘과 비교하여 상대적으로 빠르다.

단점

• 평균과 최악의 시간복잡도가 $O(n^2)$으로 비효율적이다.
• Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.

시간복잡도

최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, $(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2$ 즉, $O(n^2)$ 이다.

하지만 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 $O(n)$ 의 시간복잡도를 가지게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는 탐색을 제외한 오버헤드가 매우 적기 때문에 현실적으로 최고의 정렬 알고리즘이 된다.

따라서 최선의 경우는 $O(n)$ 의 시간복잡도를 갖고, 평균과 최악의 경우 $O(n^2)$ 의 시간복잡도를 갖게 된다.

구현

#include <iostream>
#include <array>

using namespace std;

array<int, 5> swap(array<int, 5> arr, int a, int b){
    int temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
    return arr;
}

void printArray(array<int, 5> arr){
    for(int i = 0; i < arr.size(); i++){
        cout << arr[i];
    }
}

int main(){
    int min;
    int temp;
    int index;
    array<int, 5> arr = {3, 8, 9, 7, 6};
    
    for(int i = 1; i < arr.size(); i++){
        for(int j = i; j >= 0; j--){
            if(arr[j] < arr[j-1]){
               arr = swap(arr, j, j-1);
            }else{
                break;
            }
        }
        printArray(arr);
        cout << "" << endl;
    }
}