[Algorithm] 삽입 정렬 (Insertion Sort)

삽입 정렬은 해당 요소를 올바른 위치에 삽입하는 정렬 알고리즘입니다.

 

다음과 같은 순서로 이루어집니다.

1. i번째 원소 선택 (i = 1, 2, 3...)
2. i번째 앞 원소들을 비교하여 올바른 위치에 i번째 원소 값 삽입
3. 위 과정을 배열 원소의 개수만큼 반복

 

[그림 1] 예제 배열

[그림 1] 배열이 있다고 했을 때, 오름차순으로 삽입정렬을 해 보겠습니다.

 

1. i번째 원소 선택 (i = 1, 2, 3...)

[그림 2] i번째 원소 선택

차례대로 원소를 선택합니다.

맨 처음 원소는 선택해도 아무런 의미가 없으므로 두 번째 원소부터 선택합니다.

tmp에 i번째 원소 값을 따로 저장하는 이유는, 삽입하는 과정에서 i번째 원소 값이 손실되기 때문입니다.

 

2. i번째 앞 원소들을 비교하여 올바른 위치에 i번째 원소 값 삽입

[그림 3] i번째 원소 앞 원소와 비교

앞 원소와 값을 비교합니다.

[그림 3]에서 보면 13이 더 크므로, 13을 뒤로 보내고 그 자리에 5를 넣으면 됩니다.

[그림 4] 1회전 완료한 모습

이제 i + 1 한 뒤 계속 반복하면 됩니다.

 

3. 위 과정을 배열 원소의 개수만큼 반복

[그림 5] i번째 원소 선택

다음 원소를 선택합니다.

[그림 6] i번째 원소 앞 원소와 비교

앞 원소와 비교해 보면, 13이 더 크기 때문에 13을 뒤로 보냅니다.

[그림 7] i번째 원소 앞 원소와 비교

한 칸 더 앞으로 가서 비교를 합니다.

5가 더 작으므로, tmp의 값은 5 바로 뒤쪽이 되겠습니다.

[그림 8] 2회전 완료한 모습

이런 식으로 i가 끝에 도달할 때 까지 반복해야 합니다.

 

---

C++로 작성된 삽입 정렬 알고리즘입니다.

#include <iostream>
#define SIZE 6
using namespace std;

int main() {
	int arr[SIZE] = {13, 5, 9, 4, 6, 7};
	
	cout << "정렬 전 :" << ' ';
	for(int i = 0; i < SIZE; i++) cout << arr[i] << ' ';
	
	for(int i = 1; i < SIZE; i++) {
		int tmp = arr[i];
		int j;
		for(j = i - 1; j > -1; j--) {
			if(arr[j] > tmp) arr[j + 1] = arr[j];
			else break;
		}
		arr[j + 1] = tmp;
	}
	
	cout << '\n' << "정렬 후 :" << ' ';
	for(int i = 0; i < SIZE; i++) cout << arr[i] << ' ';
}

[그림 9] 실행 결과

정렬이 되었음을 확인할 수 있습니다.