[Algorithm] 삽입 정렬(Insertion Sort)

삽입 정렬이란?

삽입 정렬이란 앞 숫자들을 비교하여 알맞은 위치에 숫자를 넣는 정렬입니다.
예시를 살펴보겠습니다.

1 10 6 3 9 5 8 2 4 7

이렇게 10개의 숫자를 가진 배열이 존재한다고 가정하겠습니다.

제일 왼쪽부터 비교를 시작해줍니다.
1은 제일 왼쪽에 있으니 생략
그 다음으로 10은 1보다 크니 1 오른쪽에 위치시켜 줍니다.
그 다음으로 6은 1보다 크고 10보다 작으니 둘 사이에 위치시켜 줍니다.

이런식으로 정렬된 숫자(재정렬 할 숫자보다 앞에 있는 숫자)들을 비교해 나가며 적절한 위치에 넣어주면 됩니다.

코드는 다음과 같습니다.

#include <iostream>

using namespace std;

int main() {
	int array[10] = { 1, 10, 6, 3, 9, 5, 8, 2, 4, 7 };

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

	for (int i = 0; i < 10; i++) {
		cout << array[i] << " ";
	}
}

탐색하는 과정에서 삽입할 위치를 찾는 것은, 본인(정렬할 숫자)의 오른쪽에 있는 숫자가 본인보다 크다면 해당위치에 넣어주는 형식으로 진행하였습니다.

시간복잡도

마찬가지로 삽입 정렬의 시간 복잡도도 $O(n^2)$ 입니다.

그러나 앞서 본 삽입 정렬, 버블 정렬과 다르게 더 효율적인 알고리즘이라 볼 수 있습니다.
그 이유는 정렬할 숫자의 왼쪽 숫자들은 모두 정렬된 상태이기에 필요한 부분만 교환하면 된다는 장점이 존재하기 때문입니다.