[알고리즘] 삽입 정렬 알고리즘 (Insertion Sort)

삽입 정렬(Insertion Sort)

 

삽입 정렬은 필요할 때만 각 데이터를 적절한 위치에 삽입하는 정렬입니다. 무조건 위치를 교환하는 선택 정렬과 버블 정렬에 비해 다소 효율적이라고 볼 수 있습니다.

 

1   9   4   6   11   10   3   15   2   13

 

위와 같은 수가 있을 때 수들을 오름차순하는 삽입 정렬을 해보겠습니다.

삽입 정렬의 경우, 앞에 있는 원소들이 이미 정렬되어 있다고 가정합니다. 

 

1   9   4   6   11   10   3   15   2   13

1   9   4   6   11   10   3   15   2   13

1   4   9   6   11   10   3   15   2   13

1   4   6   9   11   10   3   15   2   13

. . .

 

1은 앞의 원소가 없으므로 삽입할 위치가 없어 그대로 남습니다. 

그 다음 원소인 9는 앞의 원소에서 대소를 비교하여 적절한 위치에 삽입할 수 있는데 9가 1보다 큰 수이므로 1의 뒤 자리에 그대로 위치를 유지합니다.

그 다음 원소인 4 역시 앞의 원소에서 대소를 비교하여 적절한 위치에 삽입할 수 있는데 4가 1보다 크고 9보다 작으므로 1과 9사이에 삽입됩니다.

그 다음 원소인 6도 앞의 원소에서 대소를 비교하여 4와 9사이에 삽입됩니다.

 

이러한 방식으로 반복하여 정렬하는 방식이 삽입 정렬 방식입니다.

 

알고리즘 구현

// Algorithm Analysis
// 삽입 정렬(Insertion Sort) : (필요할 때만)각 데이터를 적절한 위치에 삽입한다.

#include <stdio.h>
#include <stdlib.h>

int main() {
	int i, j, temp;
	int arr[10] = { 1, 9, 4, 6, 11, 10, 3, 15, 2, 13 };
	for (i = 0; i < 9; i++) {
		j = i;
		while (j >= 0 && 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;
}

 

시간 복잡도 : O(N * N)

같은 시간 복잡도를 가지는 선택, 버블 정렬에 비해 필요할 때에만 삽입을 한다는 점에서 연산 수가 적어 비교적 효율적인 정렬 방식입니다. 특히, 앞에 이미 정렬이 확정되어있는 데이터가 많다면 그 어떤 정렬 알고리즘보다 빠른 알고리즘입니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.