[Algorithm] 삽입정렬(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 삽입정렬은 정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 삽입하는 방식이다. 

     정렬된 부분집합과 정렬되지 않은 부분집합이 존재한다.

     구현이 간단하지만 선택정렬, 버블정렬과 마찬가지로 비효율적이다.

     단, 정렬된 데이터에 새 값을 하나 넣을 때 빠른 효능을 보이고, 적은 데이터에 사용하기에는 괜찮은(?) 정렬 알고리즘이라고 한다.

     시간복잡도는 아래와 같다.

     Best : O(n) 

     Average : O(n^2)

     Worst : O(n^2)

     11 7 5 6 10 9 가 입력되었을 때,

     index 0에 있는 11은 이미 정렬된 부분집합이라고 생각하면 된다.

     11 / 7 5 6 10 9 

     i = 1, j = 0 (i-1), key = 7 (a[i])

     11 / (7) 5 6 10 9 에서 key인 7은 정렬된 부분집합에서 자신의 위치를 찾아 삽입된다.

     11은 7보다 크므로 7의 index(j+1)인 [1] 에 11이 들어가고 7은 index j에 들어가게 된다.

     7 11 / 5 6 10 9 

     

     i = 2, j = 1 (i-1), key = 5 (a[i])

     마찬가지로 7 11 / (5) 6 10 9 에서 key인 5는 정렬된 부분집합에서 자신의 위치를 찾아 삽입된다.

     11은 5보다 크므로 5의 index(j+1)인 [2] 11이 들어가고 j--, 7 5 11 / 6 10 9

     7은 5보다 크므로 j+1 index인 [1] 에 7이 들어가고 j--, 7 7 11 / 6 10 9

     j는 여기서 -1 이 되므로 while문이 종료되고 j+1 index인 [0] 에 key인 5를 넣어준다.

     5 7 11 / 6 10 9 

    

    ...

   

   글로 적기가 사실 쓰는 사람도 헷갈리고 보는 사람도 헷갈릴 것 같다. 

   위의 방식이 이해가 안 간다면 노트에 그림을 그려가며 하나씩 디버깅해보면 좋을 것 같다.

   하나씩 디버깅해보면서 이해한 알고리즘이야말로 진짜 내 것이 되는 것 같다(?) 

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int main(void) {     freopen("input.txt", "rt", stdin);       int n, i, j, key;       scanf("%d", &n);     vector<int> v(n);       for (i = 0; i < n; i++)         scanf("%d", &v[i]);       for (i = 1; i < n; i++)     {         j = i - 1;         key = v[i];                  while (j >= 0 && v[j] > key)         {             v[j + 1] = v[j];             j--;         }           v[j + 1] = key;     }       for (i = 0; i < n; i++)         printf("%d ", v[i]);       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include<stdio.h> #include<vector> #include<algorithm>   using namespace std;   int main(){     int a[100], n, tmp, i, j;       scanf("%d", &n);       for(i=0; i<n; i++)         scanf("%d", &a[i]);          for(i=1; i<n; i++){         tmp=a[i];           for(j=i-1; j>=0; j--){             if(a[j]>tmp) a[j+1]=a[j];             else break;         }           a[j+1]=tmp;     }       for(i=0; i<n; i++)         printf("%d ", a[i]);          return 0; }

cs

while 과 for 차이만 있을 뿐 로직은 같다.

#. Result

  - Input --------------------------------------------------------

6

11 7 5 6 10 9

------------------------------------------------------------------

  - Output --------------------------------------------------------

5 6 7 9 10 11

------------------------------------------------------------------