1. 삽입 정렬을 통해 알아보는 알고리즘의 명확성

삽입 정렬 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int i, j, k, N, temp;
	int array[1000];
	scanf("%d", &N);

	for (i = 0; i < N; i++)
	{
		scanf("%d", &array[i]);
	}

	for (i = 1; i < N; i++)
	{
		for (j = i - 1; j >= 0; j--)
		{
			if (array[i] >= array[j]) break;//array[j + 1]에 array[i]를 삽입, array[j + 1]부터 arrray[i - 1]은 모두 한칸씩 앞으로 이동
			//if에 한번도 안 걸리면 j는 -1로 반복문을 빠져나가게 된다. 그럼 똑같이 하면 된다.
		}

		temp = array[i];

		for (k = i - 1; k > j; k--)
		{
			array[k + 1] = array[k];
		}

		array[j + 1] = temp;
	}

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

이는
1. 처음에 한칸은 정의상 정렬되어 있는 상태이다. - 초기 조건 성립

2. 이미 정렬되어 있는 N칸에 하나를 더 삽입하면 이도 정렬되어 있다. - 유지 조건 성립

3. N칸을 모두 정렬하면 종료 - 종료 조건 성립

-> 따라서 이는 합당한 알고리즘임을 알 수 있다.

삽입 정렬의 분석 - worst case :

2분의 n곱하기 n - 1은 1 ~ (n - 1)까지의 합이다.

위 그림에서 얘들이 워스트케이스일 때 빨생하는 경우,

단 c5의 경우는 2 ~ n까지의 합이므로 2분의 n곱하기 (n + 1) - 1이다.