삽입 정렬이란?

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 출처 : 위키

각 숫자를 적절한 위치에 삽입한다고 생각하자.

삽입정렬은 앞의 원소가 이미 정렬되었다고 가정을 하면
버블정렬, 선택정렬보다 효율적인 정렬이 될 수 있다.

왜냐하면

앞에서 이미 정렬을 해 놓았기 때문에 연산을 할 필요가 없이
건너뛰고 정렬이 되지 않은 부분만 연산을 수행하면 되기 때문이다.

버블정렬과 선택정렬은 계속해서 비교를 해야하기 때문에 삽입 정렬보다 효율성이 떨어진다.

과정설명

1. 처음 값이 제일 작은 값이라 가정 (효율성을 위해)
2. j의 값을 감소시키면서 바로 옆의 원소와 비교
3. j의 값이 바로 옆 원소보다 작을 시 swap

C언어 코드

#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--;
			if (j < 0) {
				break;
			}
		}
	}
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
}

시간 복잡도 (Big O)

삽입은 선택정렬,버블정렬 과 마찬가지로 시간복잡도가 N^2 이다. 가장 비 효율적인 알고리즘이라고 할 수 있다.
하지만 맨 앞이 정렬이 되어있다고 가정하면 버블정렬, 선택정렬보다 효율적이라고 말할 수 있다.