[알고리즘/C] 삽입정렬(insertion sort)

삽입정렬이란?

배열의 두번째 원소부터 시작해서 오름차순 혹은 내림차순으로 정렬했을 때 알맞은 자리를 찾고, 오름차순일 경우에 삽입하고자 하는 수보다 큰 수들을 뒤로 밀어낸다. 그리고 알맞은 자리에 넣고자 하는 수를 삽입하고, 이 과정을 수가 모두 정렬될 때까지 반복하는 방법이 삽입 정렬이다.(내림차순일 경우 작은 수들을 뒤로 밀어냄)

 

void insertion_sort(int list[], int n) {
	int i, j, k;
	int temp;

	for (i = 1; i < n; i++) { //배열의 두 번째 원소부터 시작
		for (j = 0; j < i; j++) {
			if (list[i] < list[j]) break; //들어갈 자리 찾기
		}
		temp = list[i];
		for (k = i; k >j; k--) {  
			list[k] = list[k - 1]; //뒤로 밀기
		}
		list[j] = temp;
	}
}

시간복잡도

삽입정렬의 시간복잡도는 입력 자료의 구성에 따라서 달라진다.

• 최선의 경우: 입력 자료가 이미 정렬되어있는 경우 -> 외부 루프는 n-1번, 각 단계마다 1번의 비교 연산과 2번의 이동 연산이 발생하므로 비교 횟수는 (n-1), 이동 횟수는 2(n-1)이므로 시간 복잡도는 O(n)
• 최악의 경우: 입력 자료가 역순으로 정렬되어있을 경우 -> 외부 루프는 n-1번, 각 단계마다 i번의 비교 연산과 i+2번의 이동 횟수가 발생하므로 비교 횟수는 0+1+2+...(n-1) = n(n-1)/2, 이동 횟수는 n(n-1)/2+2(n-1) = n^2+3n-4/2 이므로 시간 복잡도는 O(n^2)

(최악의 경우를 시간 복잡도의 척도로 사용하므로 삽입 정렬의 시간복잡도는 O(n^2)