[알고리즘] 삽입정렬 Insertion Sort (C++ 구현)

📌 삽입정렬

삽입정렬에서는 정렬대상이 될 원소를 두 부분으로 나누는 것이 핵심이다. 이미 정렬된 부분(왼쪽)과 정렬해야 하는 부분(오른쪽)으로 나누고 정렬해야 하는 부분의 첫번째 원소를 이미 정렬이 된 부분에 하나씩 삽입해 정렬한다. 즉, 정렬할 부분의 원소를 이미 정렬된 부분에 하나씩 삽입해 전체적으로 정렬된 부분의 비율을 키우는 것이다. 이미 정렬된 부분에 하나씩 삽입한다고 해서 '삽입'정렬이라고 부른다. 이때 삽입할 때는 이미 정렬된 부분의 가장 큰 원소(가장 오른쪽 원소)부터 비교해나간다.

 

n = 5 인 { 8, 3, 9, 7, 6 } 배열을 오름차순으로 삽입정렬해본다. 이미 오름차순으로 정렬된 부분은 왼쪽에, 정렬되지 않은 부분은 오른쪽으로 두고 3부터 하나씩 삽입한다. 총 3, 9, 7, 6 의 숫자가 추가되었으며 삽입 시 초록색 이미 정렬된 부분 중 가장 큰 원소부터 오른쪽 -> 왼쪽으로 비교해나간다.

📌 시간복잡도

알고리즘 전공 수업 때 정말 도움이 많이 되었던 부분이다. (교수님의 말씀과 강의자료 인용했다)

삽입정렬의 시간 복잡도는 최악과 최상일 때로 구분할 수 있다. 

- 성능이 가장 좋을 때는 이미 오름차순으로 정렬되어 있을 때이다. 이미 정렬이 되었는지 여부는 사람만 알고 있으므로 정렬된 부분에 원소를 넣을 때마다 가장 큰 숫자와의 비교를 한번만 하게 되므로 총 n-1 번 계산으로 O(n) 시간복잡도를 가진다.

- 최악의 경우에는 역순으로 (내림차순으로) 정렬된 경우이다. 이때는 가능한 모든 비교를 다 해봐야 하므로 i + 1 번째 원소를 추가할 때 i 개의 앞서 정렬된 원소와 모두 비교해줘야 한다. 이때의 성능은 1 + 2 + ... + (n - 1) = n(n-1) / 2 가 됨. O(n^2) 시간복잡도를 가진다.

- 최악의 경우가 아니더라도 평균적인 경우의 시간 복잡도 또한 O(n^2)이 된다. 이를 증명하려면 수식이 너무 길어지는데 여기 쓰기엔 번거로우므로 패스..

 

결론적으로 인접한 두 원소를 교환하는 방식(버블정렬, 삽입정렬 등)은 O(n^2) 시간복잡도가 최적이다. 

간단하게 증명을 해보자면 n 개의 서로 다른 값을 가지는 원소를 나열하는 방법은 n! 이다. n개의 원소 중 2개를 뽑는 경우는 nC2 = (n, 2)가지. 정렬되지 않은 배열이라면 순서가 틀린 쌍이 분명 있을 것이고 완전히 정렬된 배열이라면 순서가 틀린 쌍은 없을 것이다. 이때 인접한 두 원소를 교환하면 순서가 틀린 쌍 하나가 줄어든다. 따라서 n개의 원소 중 2개를 뽑는 (n, 2)번의 교환이 평균적으로 필요하며 이는 마찬가지로 O(n^2)이 된다.

📌 C++ 구현

간단하게 insertion_sort 라는 함수로만 구현했다. 버블정렬과 비슷한 구조라 크게 어렵지 않았다.

병렬 문제는 다른 것보다도 인덱싱만 잘하면 문제없지..

vector<int> insertion_sort(vector<int> target) {
	int n = target.size();
	int temp;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j > 0; j--) {
			if (target[j] < target[j-1]) {
				temp = target[j-1];
				target[j-1] = target[j];
				target[j] = temp;
			}
			else
				break;
		}

		// i번째 정렬 결과 출력
		for (int c = 0; c < n; c++) {
			cout << target[c] << " ";
		}
		cout << endl;
	}
	return target;
}

(좌) { 8, 3, 9, 7, 6 } 삽입정렬, (우) { 8, 3, 5, 9, 4, 1, 7, 6, 2 } 삽입정렬 결과

 

다음은 병합정렬!