Insertion Sort 삽입정렬

안녕하세요. 주인장 H입니다. 

오늘은 삽입 정렬에 대해 알아보겠습니다.

오름차순으로 무질서한 1~10 을 정렬한다고 했을때, 

각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 풉니다. 

다른 정렬과 비교해 본다면 삽입 정렬은 필요할 때만 위치를 바꾸게 됩니다. 

 

삽입 정렬은 기본적으로 정렬이 되어있다고 가정 했을 때 굉장히 빠른 속도를 자랑합니다. 

소스 코드 상 반복문이 두 번 들어가 있다는 점에서 시간 복잡도는 O(N^2)입니다.

 

#include <stdio.h>

int main(void)
{
	int arr[10] = { 1,3,2,5,7,6,10,9,8,4 };
	int i, j, tmp;
	for (i = 0; i < 9; i++)
	{
		j = i;
		while (j >= 0 && arr[j] > arr[j + 1]) {
			tmp = arr[j]; 
			arr[j] = arr[j + 1];
			arr[j + 1] = tmp;
			j--;
		}
	}
	for (i = 0; i < 10; i++) {
		printf("%2d", arr[i]);
	}
	return 0;
}