삽입정렬(Insertion Sort)

삽입정렬은 각 원소를 필요할 때만 적절한 위치에 삽입하는 것이다.

 

1 10 5 8 7 6 4 3 2 9 --> 가장 앞에 있는 1이 가장 작은 수이기 때문에 넘어간다.

 

1 10 5 8 7 6 4 3 2 9 --> 10은 앞에 있는 원소인 1보다 크기 때문에 유지하고 넘어간다.

 

1 10 5 8 7 6 4 3 2 9 --> 1 5 10 8 7 6 4 3 2 9 --> 5는 앞에 있는 원소 중 1과 10 사이에 들어가야 적절하기 때문에 삽입한다.

1 5 10 8 7 6 4 3 2 9 --> 1 5 8 10 7 6 4 3 2 9 --> 8은 앞에 있는 원소 중 5와 10 사이에 들어가야 적절하기 때문에 삽입한다.

.

.

.

1 2 3 4 5 6 7 8 10 9 --> 1 2 3 4 5 6 7 8 9 10 --> 9는 앞에 있는 원소 중 8과 10 사이에 들어가야 적절하기 때문에 삽입한다.

 

=> 최종적으로 1 2 3 4 5 6 7 8 9 10 이 이루어진다. 

 

[예제]

#include <stdio.h>

int main() {
    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(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]);
	}
}

 

왼쪽 원소와 비교하여 값이 더 작다면 두 원소의 자리를 바꿔준다. 바꿔준 후 그 다음 왼쪽 원소와 다시 비교해서

 

값이 더 작다면 또 두 원소의 자리를 바꿔주는 방식을 반복한다.

 

[결과]

삽입정렬(Insertion Sort) 결과

 

[삽입 정렬의 시간 복잡도]

삽입 정렬의 시간 복잡도는 O(N^2) 이다.

 

과정을 표현하면 선택 정렬, 버블 정렬과 마찬가지로 10 + 9 + 8 + ... + 1 =55 이며, 10 * (10+1) / 2 와 같은 공식으로

풀 수 있다. 10 * (10 + 1) / 2 와 같은 공식을 수식으로 표현하면 N * (N+1) / 2 로 표현된다.

수식을 쉽게 표현하면 N*N 이며, 시간 복잡도는 O(N^2)를 만족하는 것이다.

삽입 정렬은 데이터가 이미 거의 정렬된 상태에 한해서는 어떠한 알고리즘보다도 빠르다는 특징이 있다.

 

[소감]

삽입 정렬도 선택 정렬과 버블 정렬과 동일한 시간 복잡도를 가지고 있지만 실제로 삽입정렬의 연산횟수가 가장

 

적게 일어난다는 점에서 세 가지의 정렬 방식 중 가장 효율적인 알고리즘이라는 것을 알 수 있었다.

---

출처

https://blog.naver.com/ndb796/221226806398

4. 삽입 정렬(Insertion Sort)