4. 삽입 정렬(Insertion Sort)

ㆍ각 숫자를 적절한 위치에 삽입하는 방법.

ㆍ버블정렬이나 선택정렬같은 시간복잡도 O(n^2) 방법들중엔 제일  빠르다.

 

ㆍ 앞에 있는 숫자들이 이미 정렬돼있다고 가정한다.

ㆍ 앞에 있는 숫자들중에 들어갈 위치를 생각해서 들어가는 방법이다.

 

앞에 있는 숫자가 나보다 더 작으면 위치바꿈을 멈춘다.

최악의 경우 연산 속도는 O(n^2)이다.(반복문이 두 번 들어가있다.)

거의 정렬이 돼있는 경우에는 속도가 아주 빠르기 때문에 삽입 정렬이 가장 효율적이다.

 

자세한 수행 과정 :

만약 [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] 의 숫자들을 오름차순으로 정렬할 때 삽입 정렬의 순서는

1. 앞에 있는 숫자들이 정렬되어 있다고 가정한다.

  1은 앞으로 갈 자리가 없으니 10부터 보면

  _ 1 _ 10 

  으로 1의 앞과 1의 뒤로 갈 수 있는데 10은 1보다 크기 때문에 그대로 있는다.

2. 그 다음 5를 보면

  _ 1 _ 10 _ 5

  으로 자리가 있는데 5는 10과 비교했을 때 10보다 작고, 1보다는 크기 때문에 1과 10 사이에 들어간다.

3. 이러한 방식으로 계속 진행하며 만약 6의 경우에는

  _ 1 _ 5 _ 7 _ 8 _ 10 _ 6 에서

  6보다 큰 값이 왼쪽에 있다면 적절한 위치에 들어간다 (10, 8, 7만 확인하여 7의 왼쪽에 들어감)

  그래서 1, 5 와 같은 모든 숫자를 확인할 필요가 없다.

#include <stdio.h>

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

 

출력 결과