[C/C++] 삽입 정렬(insertion sort)

삽입 정렬이란?

삽입 정렬(insertion sort)은 새로운 데이터를 이미 정렬된 데이터들 사이의 적절한 자리에 집어넣는 정렬 방식입니다.

 

예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다.

값	5	6	10	4	3	8	7	1	2	9
위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

 

먼저, [0]인 5는 이미 정렬된 상태라고 생각합니다.

그다음 [1] 위치의 6이라는 숫자를 정렬해야 합니다. 그러면 6이 올 수 있는 위치는 두 군데입니다.

_ 5 _

 

6은 5보다 크므로 5 뒤에 위치합니다.

5 6

 

이제 [2] 위치의 10을 정렬해야 합니다. 10이 올 수 있는 위치는 세 군데입니다.

_ 5 _ 6 _

 

10은 가장 뒤에 있는 숫자 6과 비교하여 크므로 6 뒤에 위치합니다.

5 6 10

 

마지막으로 [3] 위치의 4까지 해봅시다. 4는 앞의 10과 비교하여 더 작으므로 교환이 일어납니다. 그다음 4와 6을 비교하여 4가 더 작으므로 교환이 일어납니다. 계속해서 교환이 일어나서 가장 앞자리까지 오게 됩니다.

_ 5 _ 6 _ 10 _ 4

_ 5 _ 6  4  10

_ 5  4  6  10

4  5  6  10

 

이처럼 삽입 정렬은 앞에 데이터들은 이미 정렬되었다 가정하고 이미 정렬된 데이터들 사이에 적절한 위치에 집어넣는 방식입니다. 이미 정렬된 데이터이기 때문에 적절한 위치에 집어넣기 위해서는 뒤에서부터 차례대로 교환이 일어나야 합니다.

 

#include <stdio.h>

int main(){
	//1~10 무작위 배열
	int arr[10] = {5, 6, 10, 4, 3, 8, 7, 1, 2, 9};
	int i, j, temp;
	
	for(i=0;i<9;++i){ 
		j=i+1;
		//뒤에서 부터 비교하여 교환 
		while(arr[j]>arr[j+1]){
			temp = arr[j];
			arr[j] = arr[j+1];
			arr[j+1] = temp;
			j--;
		}
	}
	
	//출력 
	for(i=0;i<10;++i){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

결과값:

1 2 3 4 5 6 7 8 9 10

 

삽입 정렬은 거의 정렬된 상태의 배열을 정렬하는데 매우 빠릅니다. 하지만 최대 시간 복잡도는 선택 정렬, 버블 정렬들과 시간 복잡도가 같습니다.

 

 

삽입 정렬의 시간 복잡도(or 빅오)는 O(N^2)입니다.