[Sorting] 3. Insertion Sort

What is insertion sort?

insertion sort는 pseudo code를 통해 설명드리겠습니다.

1. i = 1;
2. j = i; t = a[i];
3. while a[j-1] > t && j > 0 ---> 1) a[j] = a[j-1], 2) j--;
4. a[j] = t;
5. i++ and go to step 2

위에 순서대로 진행이 됩니다.  그림으로 확인해보자면

위의 그림처럼 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬하는 소팅입니다. 앞에서 배운 selection, bubble과 마찬가지로 간단한 소팅으로 분류됩니다.

코드를 확인하면,

void insert_sort(int *a, int N)
{
	int i, j, t;

	for (i = 1; i < N; i++)
	{
		t = a[i];
		j = i;

		while (j > 0 && a[j - 1] > t)
		{
			a[j] = a[j - 1];
			j--;
		}

		a[j] = t;
	}
}

정말 간단합니다... 

뒤에 배울 Quick Sort에서 한번 더 사용할 것이기 때문에 기억해두고 generalized version을 미리 만들어두었습니다.

void gen_insert_sort(void *base, size_t nelem, size_t width, int(*fcmp)(const void *, const void*)) {
	void *t;
	int i, j;
	t = malloc(width);

	for (i = 0; i < nelem; i++) {
		memcpy(t, (char *)base + i*width, width);
		j = i;

		while (fcmp((char *)base + (j - 1)*width, t)>0 && j > 0) {
			memcpy((char *)base + j*width, (char *)base + (j - 1)*width, width);
			j--;
		}
		memcpy((char *)base + j*width, t, width);
	}
	free(t);
}

 

이번까지 selection, bubble, insertion이라는 간단한 sorting을 배웠습니다.

다음 포스팅에서는 shell, quick, heap라는 재밌는 소팅들에 대해서 배울 것입니다. 여기서 insertion sort는 quick에서 사용할 것이기 때문에 기억해두면 좋습니다.

질문은 댓글로