[알고리즘] 삽입 정렬

삽입 정렬 : 각 숫자를 적절한 위치에 삽입하는 정렬 방법

​

1 10 5 8 7 6 4 3 2 9 를 오름차순으로 정렬하시오

int main(void) {  
			
	int i, j, tmp;
	int array[10] = { 1,10,5,8,7,6,4,3,2,9 };

	for (int i = 0; i < 9; i++) {
		j = i;
		while (j < 0 && array[j] > array[j + 1]) {
			tmp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = tmp;

			j--;
		}
	}

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

삽입 정렬은 필요할 때만 위치를 바꾸는 특성이 있다.

​

삽입정렬은 비교 연산을 할때 자신 앞에 있는 수 들은

이미 정렬이 되어있다고 생각하기 때문에 자신이 왼쪽에 있는 것 보다 클 경우에만 멈추면 된다는 장점이 있다.

이러한 장점으로 인해 삽입 정렬은 버블 정렬이나 선택 정렬보다 효율이 좋다.

​

하지만 소스코드 상에서 반복문이 2개 사용되고 있다는 점에서 마찬가지로

1 + 2 + 3 + ... + 10

=> O(N * N) => O(N ^ 2)

​

삽입 정렬의 시간 복잡도

O(N ^ 2)

​

이지만 실제로는 삽입 정렬이 연산 횟수가 가장 적게 일어난다는 점에서 3개의 정렬 중에는 가장 효율적이다.

​

삽입 정렬은 앞서 말한 것처럼 '정렬이 되어 있다고 가정'을 한 점에서 특정한 경우 굉장히 빠른 속도를 자랑한다.

ex) 2 3 4 5 6 7 8 9 10 1

이것을 오름차순으로 정렬한다면 10까진 다른 연산을 수행하지 않고 1번만 연산을 하고 끝난다.

마지막에 1만 적절한 위치로 이동하기 위해 연산을 하기 때문에 삽입 정렬이 효율적이다.

-> 선택 정렬, 버블 정렬은 거의 정렬된 상태라도 그 사실을 알지못하고 끝까지 정렬을 수행하기 때문에 느리다.

​

즉 데이터가 거의 정렬된 상태하면 어떤 알고리즘보다 삽입 정렬이 가장 효율적이다.

​

1 3 5 2 4

​

1 3 2 5 4

​

1 2 3 5 4

​

1 2 3 4 5

​

삽입 정렬의 비교 횟수와 이동 횟수

비교 횟수는 O(N ^ 2)이고

이동 횟수는 정렬이 역순으로 되어있는 최악의 경우에는 비교 횟수와 마찬가지로

3(N * (N + 1) /2)번 이동하기 때문에 이동 횟수는 O(N ^ 2)이다

단 최악의 경우를 제외하고는 다른 정렬( 선택 정렬, 버블 정렬) 보단 효율적이다