3) 삽입 정렬 (Insertion Sort)

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법이다.
문제는 지난 시간과 동일하다.

<다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.>

(1, 10, 8, 3, 5, 4, 7, 9, 2, 6)

int main() {
	int temp, j;
	int array[10] = { 1, 10, 8, 3, 5, 4, 7, 9, 2, 6 };
	for (int 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 (int i = 0; i < 10; i++)
	{
		cout << array[i];
	}
}

ㅡ 1 ㅡ 10 ㅡ, 8, 3, 5, 4, 7, 9, 2, 6
j가 8일때 빈칸 중 앞의 수 1 보단 크고 10보단 작으므로 그 사이에 삽입한다.
이렇게 반복해서 나가는 방법이다.

다른 정렬들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 때만 위치를 바꾸게 된다.
그래서 앞에서 학습했던 정렬보단 실제로 연산이 제일 적다.

삽입 정렬의 시간 복잡도는 O(N^2)이다.

하지만 이미 어느정도 정렬이 되어있다는 가정하에 이 방법을 사용하면 그 속도는 매우 빠르다.