[ 정렬 ] 삽입 정렬 (Insertion Sort) (C++)

이번 글에서는 삽입정렬(Insertion Sort) 에 대해서 다뤄보고자 한다.

삽입정렬은 앞으로 가면서 탐색을 진행한다. 즉, N만큼의 크기의 배열을 선언하고 0부터 N -1번까지의 배열을 사용한다고

생각했을 때, Index 1번부터 탐색을 진행하게 된다. 왜냐하면, 앞으로 가면서 탐색을 하는 방식이기 때문에 0번 Index는

의미가 없기 때문이다.

동작 원리는 그림으로 보도록 하자.

위의 과정은 간단하게 모든 정렬이 아닌 앞부분에 대해서만 정렬하는 과정을 나타내 보았다.

위의 그림을 토대로 말로 설명을 해 보겠다. (오름차순 기준)

시작 Index를 기점으로 앞으로 쭉 탐색을 진행하는데 탐색을 진행하는 조건은 2가지이고 다음과 같다.

1. 0보다 크거나 같은지?

   - 0보다 작은 Index는 존재하지 않기 때문에 아무리 탐색을 많이 하더라도 0보다 크거나 같을 때 까지만 탐색이 가능하다..

2. 비교하는 값이 더 큰지??

   - 위의 그림에서 봐서 알겠지만 앞의 값이 더 크다면 특정한 과정을 진행한 후, 탐색을 계속하지만 그 반대경우라면,

     즉, 비교하는 값이 더 작다면 그대로 탐색을 종료하게 된다.

그렇다면 2번 조건에서 말한 특정한 과정이라는게 무엇인지 구체적으로 알아보도록 하자.

내가 K번 Index이고 K -1번부터 0번이 될 때까지 탐색하는 과정이라고 생각해보자.

만약, K - 1번 Index가 현재 내 값보다 더 크다면 (K - 1) + 1 번 Index에 (K - 1)번 값을 그대로 넣어주게 된다.

위의 그림에서 3번째 배열 상태를 보면 { 3, 7, 7, .... } 식으로 되어있는 그림을 볼 수가 있는데, 이렇게 되는 상황인 것이다.

즉, 오름차순으로 정렬을 할 때, 만약 비교하는 값(비교 Idx)이 나보다 더 큰 경우를 만나게 된다면

Arr[비교Idx + 1] = Arr[비교Idx]가 된다. 그렇다면 내 원본의 값은?? 바로 임시저장변수인 Temp에 저장해 놨기 때문에 계속해서 탐색이 가능하다.

그렇다면 위의 그림에서 1번째 배열상태 밑에 적혀있는 설명에서 '탐색종료'라고 적힌 빨강색 글씨를 한번 주목해보자.

이게 무슨말일까?? 왜 더이상 탐색을 해도 되지 않을까??

위의 그림의 마지막 상황을 그대로 가져와서 한번 설명해보겠다.

{ 1, 3, 7, 15, 4, 2, 8, 10, 6 } 의 상황에서 이제 '15'를 기준으로 탐색을 시작하는 상황이다.

여기서 탐색을 하기전에 눈여겨 봐야할 것이 하나 있다. 바로 '15' 앞에 있는 숫자들은 이미 정렬이 완료되어 있다는 것이다.

Insertion Sort는 1번인덱스부터 차례대로 정렬을 실시하기 때문에, K번 Index부터 탐색을 할 때, K - 1번 Index들 까지는

이미 정렬이 완료되어 있음을 확인할 수 있다.

그렇다면 이 상황에서 '15'를 시작으로 앞으로 진행해보자. 바로 앞에 '7'이라는 값이 있다. '7'이 더 작은 숫자이기 때문에

아무 일도 일어나지 않을 것이다. 그렇다면 이 때, '7' 앞에 있는 '3'까지 탐색을 진행해야할까??

아니다. 어차피 '7'앞에는 '7'보다 작은 값들만 정렬된 채로 존재할 것이기 때문에 더 이상 탐색을 진행할 필요가 없다.

그렇다면 그 다음 '4'를 시작으로 탐색을 해보자.

'4'와 '15'를 비교했을 때 15가 더 크기 때문에, 배열이 [ 1, 3, 7, 15, 15, .... ] 이 될 것이다.

그 다음 '4'와 '7'을 비교했을 때 7이 더 크기 때문에 배열이 [ 1, 3, 7, 7, 15, ... ] 이 될 것이다.

그 다음 '4'와 '3'을 비교했을 때 4가 더 큰 값이기 때문에 아무일도 일어나지 않고 탐색을 종료한다. 왜냐하면 탐색을 더 해

봤자, '3'앞에는 '3'보다 작은 값들만 정렬된 채로 존재할 것이기 때문에 더 쳐다볼 필요가 없다.

하지만, 이대로 끝내버린다면?? 아마 배열의 상태는 [ 1, 3, 7, 7, 15... ] 가 될 것이다.

따라서 우리는 탐색을 종료한 후에, 값을 바꿔주는 한 가지 일을 더 해줘야 한다.

바로 배열을 [ 1, 3, 4, 7, 15, ... ] 형태로 만들어주는 것 !

이 경우를 위해서 배열의 Index를 가르키는 변수를 하나 만들어서 관리해 주어야 한다.

[ 1, 3, 7, 15, 4 .... ] 에서 4는 4번Index에 속하는 값이었고 우리는 탐색을 3번 Index, 2번 Index, 1번 Index까지 해주고

탐색을 종료하였다. 즉, 우리가 Index를 가르키도록 만든 변수는 아마 '1'번 Index를 가리키고 있는 채로 탐색이 종료되었을

것이다. 즉, 그 Index를 ++ 시켜준 후에, Arr[Index] = Temp 로 설정해주면 아마 [1, 3, 4, 7, 15, ... ] 와 같은 결과를 얻을 수

있을 것이다.

코드를 한번 봐보도록 하자.

void Insertion_Sort()
{
    for (int Cur_Idx = 1; Cur_Idx < MAX; Cur_Idx++)  // 1번 Index부터 마지막 Index까지 탐색. 0번 Index는 탐색 X
    {
        int Temp = Arr[Cur_Idx];        // 현재의 값을 Temp라는 임시 저장 변수에 저장.
        int Before_Idx = Cur_Idx - 1;  // Index를 관리하는 변수. 현재 Index - 1번부터 탐색 시작.

        while (Before_Idx >= 0 && Arr[Before_Idx] > Temp) // Idx번호가 0보다 크거나 같고, 이전 값이 더 큰 경우만
        {
            Arr[Before_Idx + 1] = Arr[Before_Idx];  // 값을 그대로 복사해서 넣어주고
            Before_Idx = Before_Idx - 1;               // 탐색 계속해서 진행
        }
        Arr[Before_Idx + 1] = Temp;    // 탐색이 종료되면, 올바른 배열을 만들어 주기 위해서 값 삽입.
    }
}

# 시간복잡도

- 삽입정렬은 최악의 경우와 최선의 경우 시간의 차이가 많이 정렬법이다.

  먼저 최악의 경우를 한번 보도록 하자. 아래와 같은 배열이 있다.

 

  위와 같은 배열이 있을 때, 시간복잡도는 얼마일까??

   위에서 말한 방식대로 천천히 한번 해보도록 하자. 아마 1번 Index인 '6'부터 정렬을 위한 비교를 시작할 것이다.

   그럼 6에서 7로 1번 비교.

   2번 Index인 5에서는 7과 6 2번 비교.

   3번 Index인 4에서는 7, 6, 5 3번 비교..

   ..... 마지막 6번 Index인 1에서는 7,6,5,4,3,2, 6번 비교할 것이다.

   결과적으로 1 + 2 + 3 + 4 + 5 + 6 = 21번 비교할 것이고 이는 N(N-1)/2와 같다.

   즉, 최악의 경우 삽입정렬의 시간복잡도는 이 걸리게 된다.

   그렇다면, 최선의 상황을 계산해보자.

  

   위와 같은 배열이 있을 때, 계산을 해보자. 위에서 충분히 설명했지만 한번 더 말하자면, 앞으로 움직이면서 Swap조건에

   맞지 않는 값이 나온다면 그대로 비교를 종료하는게 삽입정렬이다 !

   1번 Index인 2에서 1 1번비교.

   2번 Index인 3에서 2 1번비교.

   3번 Index인 4에서 3 1번비교.

   4번 Index인 5에서 4 1번비교....

   .... 마지막 Index인 7에서 6 1번비교.

   결과적으로 1 + 1 + 1 + 1 + 1 + 1 = 6번 비교를 하게 된다. 이는 수식으로 나타내면 N-1번 비교를 한 것과 같다.

   즉, 최선의 경우 삽입정렬의 시간복잡도는 이 걸리게 된다.

  

   삽입정렬의 시간복잡도는 이렇게 정리할 수가 있다. 최악의 경우와 최선의 경우 시간복잡도가 다르다는 것 !  

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
 
#define MAX 100
using namespace std;
 
int Arr[MAX];
bool Flag[10000];
 
void Print()
{
    cout << "##########################################################################################################" << endl;
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        printf("%3d ", Arr[i]);
        Cnt++;
        if (Cnt == 20)
        {
            Cnt = 0;
            cout << endl;
        }
    }
    cout << "##########################################################################################################" << endl;
    cout << endl;
}
 
void Insertion_Sort()
{
    for (int Cur_Idx = 1; Cur_Idx < MAX; Cur_Idx++) // Start Index '1';
    {
        int Temp = Arr[Cur_Idx];
        int Before_Idx = Cur_Idx - 1;
 
        while (Before_Idx >= 0 && Arr[Before_Idx] > Temp)
        {
            Arr[Before_Idx + 1] = Arr[Before_Idx];
            Before_Idx = Before_Idx - 1;
        }
        Arr[Before_Idx + 1] = Temp;
    }
}
 
int main(void)
{
    for (int i = 0; i < MAX; )
    {
        Arr[i] = rand() % 300 + 1;
        if (Flag[Arr[i]] == false)
        {
            Flag[Arr[i]] = true;
            i++;
        }
    }
    cout << "[ Initialize Array State ]" << endl;
    Print();
 
    Insertion_Sort();
    cout << "[ After Sorting Array State]" << endl;
    Print();
    
    return 0;
}