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

이번 시간에는 삽입 정렬에 대해 알아보도록 하겠다.

 

 

 

 

 

 

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결한다.

다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 때만 위치를 바꾼다.

 

 

 

삽입 정렬은 비교적 느린 정렬 알고리즘에 속하지만 쉽게 생각할 수 없는, 조금은 복잡한 구조를 가지고 있다.

 

 

하지만 삽입 정렬은 앞서 소개했던 버블 정렬과 선택 정렬에 비해서는 더 효율적인데, 매 차례에 바로 앞 원소와 비교하면서 자신의 위치까지만 swap 연산을 하고, 자신의 위치를 찾으면 멈추기 때문이다. 

 

 

 

 

 

 

 

코드로 구현해 보면,

 

#include <stdio.h>
int main() {
	int i, j, temp;
	int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

	for (i = 0; i < 9; i++) {
		j = i;
		while (j >= 0 && array[j] > array[j + 1]) {
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}

	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}

	return 0;
}

위와 같은 코드는 while을 사용해서 더 짧게 구현했다.

 

 

 

#include <stdio.h>
int main() {
	// Insertion Sort
	int i, j, temp;
	int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

	for (i = 1; i < 10; i++) {
		j = i;
		while (j > 0 && (array[j - 1] > array[j])) {
			temp = array[j - 1];
			array[j - 1] = array[j];
			array[j] = temp;
			j--;
		}
	}
	

	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}

	return 0;
}

 

 

 

 

또한, for와 break를 사용하여 아래와 같이 구현해보았다.

#include <stdio.h>
int main() {
	int i, j, temp;
	int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

	for (i = 1; i < 10; i++) {
		for (j = i; j >= 0; j--) {
			if (array[j-1] > array[j]) {
				temp = array[j];
				array[j] = array[j - 1];
				array[j - 1] = temp;
			}
			else
				break;
		}
	}

	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}

	return 0;
}

 

 

 

 

 

 

결과는

1 2 3 4 5 6 7 8 9 10

로 역시나 바르게 정렬된 것을 볼 수 있다.

 

 

 

 

 

삽입 정렬은 기본적으로 '정렬이 되어있다고 가정'을 한다는 점에서 특정한 경우에 따라 굉장히 빠른 속도를 자랑한다.

하지만 for, while의 반복문을 두 번 사용했다는 점에서 시간복잡도는 O(N ^ 2)이다.

 

 

 

 

 

 

시간 복잡도는 O(N ^ 2)로 똑같지만, 필요한만큼만 연산하므로 선택 정렬과 버블 정렬에 비해 연산량이 상대적으로 적어서 효율적이다. (하지만 이후에 소개할 정렬 연산들보다는 비효율적이다.)

 

 

 

 

 

 

만약 데이터가 거의 정렬된 상태라면 삽입 정렬이 가장 효율적이다. 삽입 정렬은 필요한 때에 한해서만 삽입을 진행하기

때문에 데이터가 이미 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다.

 

 

 

 

 

 

 

다음 시간에는 퀵 정렬에 대해 알아보도록 하겠다.