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

1. 삽입정렬 정의

자신보다 앞의 원소가 큰지 작은지 비교하여 자신의 위치를 찾아서 삽입하는 정렬 알고리즘이다.

• 왼쪽에는 이미 정렬된 부분, 오른쪽에는 정렬해야하는 부분으로 나눈 후 정렬한다.
• 두 번째 원소부터 시작하여 왼쪽에 있는 이미 정렬된 부분이랑 비교하여 삽입할 위치를 지정한 후, 삽입할 위치 뒤에 있는 원소들을 뒤로 옮겨 해당 위치에 원소를 삽입하는 알고리즘이다.

 

삽입정렬 예제

(사진 출처: https://rninche01.tistory.com/entry/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-01-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC)

 

2. 삽입정렬 특징

• 정렬하고자 하는 개수 크기가 작을수록 좋은 알고리즘
• 이미 정렬되어있는 경우 빠름 (역순의 경우 최악의 알고리즘)

 

3. 시간 복잡도

• Best Case
  • 이미 정렬이 되어있는 경우 : O(n)
  • 비교횟수 : n-1 번 (n: 원소개수)
• Worst Case
  • 정렬이 하나도 안되어있는 경우, 즉 역순일 경우 : O(n^2) 
  • 비교횟수 : 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2 = O(n^2)

 

4. 구현 방법  (C++)

int temp;
    for (int i = 1; i < n; i++){
        temp = arr[i]; 
        for (int j = i - 1 ; j >= 0 && temp < arr[j]; j--){
            arr[j+1] = arr[j];
        }
        arr[j+1] = temp;
    }