삽입정렬(Insert Sort)

가장 작은 범위를 만든 후 해당 범위에서 가장 작은 수를 왼쪽으로 이동시키고, 점점 범위를 넓혀가며 범위 내에서 작은 수를 점차적으로 왼쪽으로 이동시키는 방법.

말로 설명하기엔 역시나 어려움이 따른다. -_-

하지만 직접 그림을 보거나 코드를 보면 금방 이해가 갈 것이다.

1. 처음에는 가장 최소 단위인 2개의 블록만 범위로 잡는다. 기존의 3이란 값에 8을 비교해야 하는 상황이다.

3과 8을 비교하면 8이 더 크기 때문에 따로 swap이 일어나지 않는다.

2. 범위를 3개로 넓힌다. 0이란 값이 새로 첨가된 상황이다. 0과 8을 비교한다. 0이 더 작기 때문에 0 위치에 8을 집어넣는다.

3. 0을 3과 비교한다. 0이 더 작으므로 0 위치에 3을 집어 넣는다. 범위 마지막 위치이기 때문에 현재 위치에 0 값을 집어 넣는다.

4. 범위를 하나 더 늘린다. 이번에는 2와 8을 비교한다. 2 위치가 8로 교체되고, 2는 3과 비교가 된다.

역시 2위치에 3이 써지고 0과 2를 비교하면 2가 더 크기 때문에 현재 위치에 2을 삽입한다.

이런식으로 정렬을 진행하는 방식이 삽입 정렬이다.

삽입 정렬은 이미 정렬되어 있는 상태에선 가장 빠른 속도를 자랑한다. (이게 무슨 소용??)

하지만 역순으로 정렬을 해야 할 상황이 온다면 가장 최악의 속도를 나타낼 것이다.

	const int ITEMSIZE = 6;
	void insertion_sort(int array[]){
	int i,j;
	int key;
	for(i=1; i<ITEMSIZE; i++){
	key=array[i];
	for(j=i-1; j>=0; j--){
	if(array[j]>key){
	array[j+1]=array[j];
	}else{
	break;
	}
	}
	array[j+1]=key;
	}
	}
	int main(void){
	int array[itemSize] = {3, 8, 0, 2, 1, 4};
	insertion_sort(array);
	return 0;
	}

view raw gistfile1.c hosted with ❤ by GitHub