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

• 두 번째 자료부터 시작하여 앞에 자료들과 비교하여 알맞은 위치에 자료를 넣는 형식의 정렬이다.
• 비교를 하는 앞의 배열은 이미 정렬이 되어있다. 즉, n번째 자료를 비교할 때 0 ~ (n - 1) 번째 자료는 정렬이 되어있다.
• 손에 카드를 들고 정렬하는 방식과 유사하다.

1. i = (1 ~ n)인덱스까지 탐색

2. j = ( (i - 1) ~ 0 ) 인덱스까지 탐색

3. j번째 값이 i번째 값보다 크면 j + 1의 값에 j의 값을 할당하고, 크지 않으면 해당 위치에 i번째 값을 삽입

4. 위 과정 반복

---

코드 구현

#include <stdio.h>

void PrintArray(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void Insertion(int* arr, int size)
{

	int tmp, j;
	for (int i = 1; i < size; i++)
	{
		tmp = arr[i];
		for (j = i - 1; j >= 0 && arr[j] > tmp; j--)
			arr[j + 1] = arr[j];
		arr[j + 1] = tmp;

		printf("%d번째 순회: ", i);
		PrintArray(arr, size);
	}
}


int main(void)
{
	int arr[5] = { 5 , 3, 1, 9, 7 };

	printf("정렬 전: ");
	PrintArray(arr, 5);

	Insertion(arr, 5);

	printf("정렬 후: ");
	PrintArray(arr, 5);

	return 0;

}

결과

정렬 전: 5 3 1 9 7
1번째 순회: 3 5 1 9 7
2번째 순회: 1 3 5 9 7
3번째 순회: 1 3 5 9 7
4번째 순회: 1 3 5 7 9
정렬 후: 1 3 5 7 9

---

정리

• 시간 복잡도:
  • 최선의 경우: 데이터를 이동할 경우가 없으므로 (n - 1)번 = O(n)
  • 최악의 경우: 1 + 2 + .... + (n - 1) = n(n-1) / 2 번 탐색을 하므로 = O(n^2)
• 앞에서부터 정렬이 된다.