삽입 정렬 (Insertion Sort)

1. 삽입 정렬

각 숫자를 적절한 위치에 삽입하자 !

 

※ 한번 수행할 때마다 [앞] 정렬된 부분의 원소 수가 1개 증가, [뒤] 정렬 안된 부분의 원소 수는 1개 감소됨

    반복해서 수행하면 결국 [뒤] 정렬 안된 부분에는 아무 원소도 남지 않고 모두 정렬됨

 

 

※ 선택/버블 vs. 삽입

▶ 선택, 버블: 이미 알맞게 정렬되어 있더라도 차례가 되면 정렬당함 (위치 바꾸는 과정 거침) : 비효율적

▶ 삽입: 필요할때만 위치를 바꿈 : 효율적

      이번 주자 앞에 있는 애들은 다 이미 알맞은 위치에 정렬되어 있는 상태이므로 다시 정렬할 필요 없음

 

 

 

 

2. 삽입 정렬 예제

ex )  1  10  5  8  7  6  4  3  2  9  오름차순 정리하시오.

 

#include <stdio.h>

int main(void) {
	int a[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
	int n = sizeof(a) / sizeof(int);
	int temp;

	for (int i = 1; i < n; i++) {   // i는 이번 주자
		int j = i;
        
        // 이번 주자 바로 앞의 원소부터 하나씩 비교하며 하극상인 애 있으면 자리 바꾸기
		while (a[j-1] > a[j]) {     
			temp = a[j-1];
			a[j-1] = a[j];
			a[j] = temp;
			j--;
		}
	}

	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}

	return 0;
}

 

 

 

3. 삽입 정렬의 시간 복잡도

앞의 예제에서 최악의 경우 총 비교 횟수를 대략적으로 살펴보면 다음과 같다. 

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 +1 = 10 * (10 +1) / 2

 

∴  input이 N개일 때, 삽입 정렬의 시간복잡도는 O(N^2) 

 

선택정렬, 버블정렬, 삽입정렬 모두 시간 복잡도가 동일하지만, 실제로는 삽입정렬이 가장 연산횟수 적다!

(∵ 거의 정렬이 되어있는 배열의 경우, 삽입정렬이 절대적으로 유리함)