[Algorithm] [Sort] Insertion Sort

spring·2020년 11월 9일

삽입 정렬이란 데이터가 들어가야할 위치를 찾아 그곳에 삽입하여 정렬을 한다.

이 글은 기본적으로 삽입정렬이 뭔지 아는 사람들을 위해 작성되었다.

삽입정렬이 정렬이 되는 원리를 말해보자면

데이터가 N개 있을떄 N-1개만 위치를 잡아주면 나머지 1개는 알아서 정렬이 될테고,

자신이 삽입될 위치에 삽입하게되면, 나머지 원소들의 연산에 의해 정렬이 완료된다.

기본적인 삽입정렬 코드는 다음과 같다.

void InsertionSort2(int* arr, int sz) {
	int i, j;
	int temp;
	for (i = 1; i < sz; i++) {
		j = i - 1;
		temp = arr[i];
		while (j >= 0 && arr[j]>temp) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = temp;
	}
}

너무 간단한 부분이라 넘어가겠다.

손수 직접 배열을 밀어주는데, memcpy나 memmove를 이용해서 작성한 소스는 다음과 같다.

void InsertionSort3(int* arr, int sz) {
	int i, j;
	int temp;
	for (i = 1; i < sz; i++) {
		j = i - 1;
		temp = arr[i];
		while (j >= 0 && arr[j]>temp) {
			j--;
		}
		memcpy(arr + j + 2, arr + j + 1, (i - j - 1) * sizeof(int));
		arr[j + 1] = temp;
	}
}

하지만 역시 그게 그거다.

실제로 속도갱신도 그렇게 빨라지지 않는다.

왜냐면 바로 배열을 미는것이 아닌, 밀어야할 시작점을 찾는데 while이 돌기 때문.

여기서 , 위의 소스들에서 i 가 반복자인데, 반복문을 돌때 0부터 i까지 는 정렬이 완료되어있음을 증명할 수 있다.

정렬이 되어있으면, 원소가 삽입될 위치를 이진탐색으로 찾을 수 있고,

같은 방법으로 memcpy나 memmove로 밀면 더욱 속도가 개선될것이라 생각된다.

하지만, 일반적인 이진탐색이 아닌 마치 C++ 의 std::lower_bound 를 구현하면된다.

lower_bound는 해당 원소가 삽입되야할 위치를 반환한다.

이를 구현해보면 다음과 같다.

int lower_bound1(int* arr, int sz, int key) {
	int L = 0;
	int R = sz - 1;
	int M = (L + R) >> 1;
	if (arr[0] > key)return 0;
	if (arr[R] < key)return sz;
	while (L <= R) {
		if (arr[M] == key)return M;
		else if (arr[M] < key)L = M + 1;
		else R = M - 1;
		M = (L + R) >> 1;
	}
	return M + 1;
}
void InsertionSort1(int* arr, int sz) {
	int i = 0;
	int temp = 0;
	int idx = 0;
	while (i < sz) {
		temp = arr[i];
		idx = lower_bound1(arr, i, temp);
		memcpy(arr + idx + 1, arr + idx, (i - idx) * sizeof(int));
		arr[idx] = temp;
		++i;
	}
}