[Sort] 삽입정렬 Insertion Sort

삽입정렬 Insertion Sort

✏️개념

• 각 숫자를 적절한 위치에 삽입하는 방법

• 선택/버블정렬과 달리 삽입정렬은 필요할 때만 위치를 바꾼다.

• 선택, 버블, 삽입정렬 중 가장 강력한 정렬이다.

  1, 10, 5, 8, 9, 2, 4, 3, 7, 6

  • 과정

    1, 10, 5, 8, 9, 2, 4, 3, 7, 6       // 맨 앞의 1은 이미 가장 앞에 있기 때문에 삽입할 위치가 없으므로 내버려둔다.
    1, 10, 5, 8, 9, 2, 4, 3, 7, 6       // 그 다음 10은 1의 앞/뒤 둘 중 하나에 들어갈 수 있는데, 1보다 크므로 그대로 유지한다.
    1, 10, 5, 8, 9, 2, 4, 3, 7, 6       // 그 다음 5는 들어갈 수 있는 위치가 1의 앞, 1과10 사이, 10 뒤 세군데에 들어갈 수 있다. 1과 10 사이에 들어간다.
    1, 5, 10, 8, 9, 2, 4, 3, 7, 6       // 그 다음 8은 들어갈 수 있는 위치가 네 군데인데(_1_5_10_), 5와 10 사이에 들어간다.
    ...                                 // 이러한 과정을 반복한다.  
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  
  

  • 상대적으로 효과적인 이유는 선택된 숫자 앞의 숫자들은 이미 정렬이 된 상태이기 때문에 추가적으로 정렬해줄 필요가 없다. 숫자 위치만 확인해보면서 숫자의 위치만 바꿔주면 되기 때문에, 전체를 다 살펴볼 필요가 없다. 그래서 필요한 만큼만 이동하게 된다.

✏️구현

    1, 10, 5, 8, 9, 2, 4, 3, 7, 6       // 처음엔 1과 10 비교. 1 > 10은 거짓이므로 그다음으로 넘어간다
    1, 10, 5, 8, 9, 2, 4, 3, 7, 6       // 10과 5 비교. 10 > 5이므로 10과 5를 바꾼다. 그리고 5와 1을 다시 비교하는데, 1 > 5는 거짓이므로 그다음으로 넘어간다.
    1, 5, 10, 8, 9, 2, 4, 3, 7, 6       // 10과 8 비교. 10 > 8이므로 10과 8을 바꾼다. 그리고 8과 5를 비교한다.
    1, 5, 8, 10, 9, 2, 4, 3, 7, 6
    ...                                 // 이러한 과정을 반복한다
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10

    #include<iostream>
    using namespace std;

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

✏️시간복잡도 / BigO

• 10 + 9 + 8 + … + 1 만큼 연산이 이루어지므로 O(N^2)이다.

• 그러나 실제 연산 횟수는 적기 때문에 그나마 효율적이다.

• 거의 정렬이 되어 있는 상태에서 삽입정렬은 매우 효과적인데, 2 3 4 5 6 7 8 9 10 1을 정렬한다고 생각해보면 실제 연산/비교횟수는 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 9 이다.

데이터가 이미 거의 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다