C언어로 빠른 삼중 분할 퀵 정렬 구현하기

개요

Algorithms 4th edition (로버트 세지윅, 케빈 웨인 지음 | 권오인 옮김 | 길벗) 에서 소개된, 벤틀리(J. Bentley)와 세지윅(R. Sedgewick)이 고안한 빠른 삼중 분할 퀵 정렬 (연습문제 2.3.22) 을 직접 풀어보고자 함.

---

선 전체 코드

다만, 본 코드로는 직접 실행시키지 못한다. 커다란 데이터 파일을 읽고 실제 출력까지 어떻게 되는지 보기를 원한다면 프로젝트를 직접 실행해보도록 한다.

#include <string.h>

// 값을 서로 뒤바꾸는 함수
void exch(char** a, int i, int j)
{
	char* temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

void quick_fast3way_sort(char** a, int lo, int hi) {
	printf("%07d to %07d starts\n", lo, hi);
	if (lo >= hi) return;

	int p = lo, i = lo-1, q = hi, j = hi + 1;
	//while (strcmp(a[++p], a[lo])) 
	while (true) {
		while (++i <= hi) { //i가 hi보다 크다면 즉시 멈춘다.

			// 비교 실시
			int cmp = strcmp(a[i], a[lo]);
			
			// a[i] < a[lo] 일 때에는 아무것도 하지 않는다.
			// a[i] > a[lo] 이면 a[i]와 a[j]를 바꿀 준비를 해야 한다.
			if (cmp > 0 ) break;  

			// a[i] == a[lo] 이고, j가 먼저 검사를 안했다면 a[i]와 a[p++]를 교환한다.
			else if (cmp == 0 && i < j) exch(a, i, p++); 
		}
		while (--j >= lo) { // j가 lo보다 작다면 즉시 멈춘다.
			// 비교 실시
			int cmp = strcmp(a[lo], a[j]);

			// a[lo] < a[j] 일 때에는 아무것도 하지 않는다.
			// a[lo] > a[j] 이면 a[i]와 a[j]를 바꿀 준비를 해야 한다.
			if (cmp > 0) break; 
			
			// a[lo] == a[j] 이고, i가 먼저 검사를 안했다면 a[j]와 a[q--]를 교환한다.
			else if (cmp == 0 && i < j) exch(a, j, q--);
		}
		if (i >= j) break;
		exch(a, i, j);
	}
	int left_same_count = p - lo;
	int right_same_count = hi - q;
	int leftmove = min(j- p + 1, left_same_count);
	int rightmove = min(q - i + 1, right_same_count);

	int mj = j, mi = i;

	while (leftmove-- > 0 && mj >= lo) exch(a, lo + leftmove, mj--);
	while (rightmove-- > 0 && mi <= hi) exch(a, hi - rightmove, mi++);

	j -= left_same_count;
	i += right_same_count;
	
	quick_fast3way_sort(a, lo, j);
	quick_fast3way_sort(a, i, hi);
}

사용할 때에는 char*의 배열 strings이 있다 가정하고, 또 이 배열의 길이를 strings_length로 가정했을 때, quick_fast3way_sort(strings, 0, strings_length - 1);와 같이 실행하면 된다.

---

고안

빠른 삼중 퀵 정렬에 필요한 변수들

삼중 분할을 하는 이유는 중복된 키(같은 키)가 무엇인지만 알면 그것들은 더이상 정렬할 필요가 없다는 개념에서 출발한다. 본래의 퀵 정렬은 기준점이 되는 하나를 완벽한 위치에 꽂아넣고, 인덱스가 작은 쪽(이하 왼쪽)에는 그 기준점보다 작은 것들로, 인덱스가 큰 쪽(이하 오른쪽)에는 그 기준점보다 큰 것들로 구분하는 작업이었는데, 이제 그 기준점이 넓어진다고 보면 된다. 이를 알기 쉽게 정리하면 다음과 같다. lo는 정렬하고자 하는 첫번째 인덱스를, hi는 마지막 인덱스를 의미한다.

	일반 퀵정렬	삼중 퀵정렬
기준점	i	j 에서 i (j < i)
작은 부분	lo ~ i	lo ~ j
큰 부분	i ~ hi	i ~ hi
다음 탐색에서 제외	i	j ~ i

그렇다면, 중복되는 키에 대해서 따로 관리할 필요가 생기는데, 간단한 삼중 퀵정렬은 가운데에서 출발하여 점차 기준점이 넓어지도록 구현한다. 이 구현은 직접 해보지 않아서 잘 모르겠다. 이 글에서는 처음 개요에서 이야기한 두 명의 과학자가 고안한 방법대로 i와 j를 탐색해나가며 똑같은 키를 발견하는 그 때마다 양쪽 끝에 저장해두는 것으로 한다. 그림으로 표현하면 다음과 같다.

다루는 배열의 이름은 a이고 기준 값은 a[lo]와 같다. 기존에 퀵 정렬에서 사용하던 두 개의 변수에서, 두 개의 변수가 더 추가되어 총 4개의 변수를 다루게 된다. 각 변수의 역할은 다음과 같다.

• p : i가 탐색해나가며 키가 같은지 찾게 될텐데, 그 때 추가될 위치
• i : 기준 값과 lo로부터 차례로 비교해나가는 위치
• j : 기준 값을 hi로부터 차례로 비교해나가는 위치
• q : j가 탐색해나가며 키가 같은지 찾게 될텐데, 그 때 추가될 위치

큰 값에서 i가 멈추고, 작은 값에서 j가 멈춘 다음 a[i]와 a[j]가 교체된다. 따라서, 다음이 보장된다.

• lo ~ p-1 : 기준 값과 같다.
• p ~ i : 기준 값보다 작은 값이다.
• i+1 ~ j-1 : 아직 기준 값보다 큰지 작은지 알 수 없는 값이다.
• j ~ q : 기준 값보다 큰 값이다.
• q+1 ~ hi : 기준 값과 같다.

여기까지 고안한 후, 미시적인 상황에 대해 고려를 하지 않고 바로 코드 작성에 들어가니까 4~5 시간을 끙끙대도 풀지 못했다. 근데 공책에 어떻게 할지 적고 푸니까 30분 만에 풀리더라. 삼중 분할 퀵 정렬은 워낙에 가능한 상황이 많기 때문에 이를 모두 정리할 필요가 있었다. 이후 과정에서는 p, q가 별로 쓸모없으므로 표기하지 않는다.

---

중복 없는 중간 값

---

중복 있는 중간 값

---

중복 없는 최하위 값

---

중복 있는 최하위 값

---

중복 없는 최상위 값

---

중복 있는 최상위 값

---

중복 두 개

---

하위값 두 개

---

상위값 두 개

---

구현

위 9가지 상황에 대해 정리를 했다. 이제 정리하면서 코드를 만들어보자.

기본적으로는 i는 왼쪽에서 j는 오른쪽에서 출발하여, i는 있어서는 안될 큰 값을 바꾸기 위해 멈추고, j는 있어서는 안 될 작은 값을 바꾸기 위해 멈춘다. 그리고 이 둘을 교체한다. 이를 계속해서 반복한다.

i와 j의 앞으로의 탐색에서 나올 같은 값과 교체할 위치를, q와 p가 무조건 나타내도록 한다. 그래서 같은 값을 교체할 일이 있을 때에만, 교체 직후 p와 q는 증감/감소 하도록 한다. i와 j의 탐색이 끝나고, 다시 기준값을 가운데로 옮기는 과정에서는 단순히 얼마나 옮겨야 하는가만 보면 되기 때문에 p, q의 값은 변하지 않는다.

---

최종 i, j 위치 고려

• 모든 정렬을 완성시켰을 때 j ~ lo는 무조건 기준 값보다 작아야 한다. 이는 정렬한 모든 값이 같거나 클 때도 동일하게 작동한다. 즉 j가 lo보다 작아질 수도 있다.
• 마찬가지로 i도 모든 정렬을 시켰을 때에 i ~ hi는 무조건 기준 값보다 커야 한다. 이는 정렬한 것들이 모두 기준 값보다 작거나 같을 때도 동일하게 작동한다. 즉 i가 hi보다 클 수도 있다.
• i와 j가 범위를 벗어날 수 있기 때문에 범위를 벗어난 직후에 유효성을 체크하도록 한다. 이는 아래 코드로 설명될 수 있다.

while (++i <= hi) { // 우선 i를 증감시키고, 그 다음 hi보다 작거나 같은지 검사
    // 중략
}
while (--j >= lo) { // 우선 j를 가감시키고, 그 다음 lo보다 크거나 같은지 검사
    // 중략
}

또한 해당 루프의 종료 조건은 무조건 다음과 같아야 한다.

/* 중략 */

// 비교 실시
int cmp = strcmp(a[i], a[lo]);
			
// a[i] < a[lo] 일 때에는 아무것도 하지 않는다.
// a[i] > a[lo] 이면 a[i]와 a[j]를 바꿀 준비를 해야 한다.
if (cmp > 0 ) break;  

/* 중략 */

int cmp = strcmp(a[lo], a[j]);

// a[lo] < a[j] 일 때에는 아무것도 하지 않는다.
// a[lo] > a[j] 이면 a[i]와 a[j]를 바꿀 준비를 해야 한다.
if (cmp > 0) break; 

/* 중략 */

만약 i < j가 된다면 바로 루프를 종료하는 것이 하나의 방법이 아닌가? 불행히도 아니다. 왜냐하면 중복된 키가 아주 많을 수 있기 때문이다. i는 같은 기준값의 오른쪽을 의미하고, j는 왼쪽을 의미한다. i가 이미 오른쪽 끝에 가 있는 상태에서, j도 왼쪽 끝에 도달하기 위해 j는 계속 가감되어야 한다.

---

같은 값 자리 바꾸기

기본적으로 기준 값과 같다면, a[p]와 a[i]를 바꿔주면 된다.

자리바꿈이 중복이 되면 안 된다. 우선 키를 움직이고 비교를 하기 때문에 이미 검사한 항목이 다시 자리바꿈될 여지가 있다. 예를 들어 중복 없는 최하위 값을 보면 비교 값이 이미 최하위 값이기 때문에 i는 바로 앞에서 멈추어 버리고 j는 위에서 쏜살같이 내려온다. 이윽고 j가 첫번째에 도달했을 때, j가 오른쪽 첫째와 왼쪽 첫째를 바꾸어버린다면, 감시망에 공백이 생긴다. p 미만의 요소들은 무조건 기준 값과 같아야 하는데 그렇지 않게 된 것이다! 이를 위해 자리를 바꾸기 위한 조건으로 i < j 를 추가하였다. 아래 코드에서 확인할 수 있다.

/* 중략 */

// a[i] == a[lo] 이고, j가 먼저 검사를 안했다면 a[i]와 a[p++]를 교환한다.
else if (cmp == 0 && i < j) exch(a, i, p++); 

/* 중략 */

// a[lo] == a[j] 이고, i가 먼저 검사를 안했다면 a[j]와 a[q--]를 교환한다.
else if (cmp == 0 && i < j) exch(a, j, q--);

/* 중략 */

---

같은 값 제 위치로 이동하기

모든 루프가 끝났다면 j가 i보다 작아지게 된다. 그리고 p ~ q의 값들은 전부 기준 값이 된다. 이제 lo ~ p-1의 영역을 j에서부터 채워나가면 되고, q+1 ~ hi의 영역을 i에서부터 채워나가면 된다. 갑자기 교차가 되서 헷갈릴 수 있지만 그림을 계속 보면서 이해하려고 하면 천천히 이해된다…! i와 j는 범위 밖을 나가있을 수도 있지만 상관 없는 이유는 후술한다.

옮겨야 하는 개수를 최적화하기 위해 왼쪽 및 오른쪽에서 같은 값의 개수와 교체 횟수를 분리시킨다. 무슨 뜻이냐면, 예를 들어 8 8 8 8 8 8 2 3 의 배열과 8 8 2 3 4 5 6 7 을 비교하면 8의 개수는 차이가 나지만, 옮겨야 하는 건 양쪽 끝 2개 끼리만 교체하면 된다는 사실을 알 수 있다. 옮겨야 하는 횟수인 leftmove와 rightmove를 우선 구한다.

/* 중략 */

int left_same_count = p - lo;
int right_same_count = hi - q;
int leftmove = min(j - p + 1, left_same_count);
int rightmove = min(q - i + 1, right_same_count);

/* 중략 */

이후에 차례대로 바꾼다. 바꿔야 하는 횟수가 남아있음에도 바꾸면 안 되는 상황이 있다. 바로 모든 값이 같은 상황인 중복 두개를 살펴보자. 이 때에는 j가 lo보다 작은 상황이고, leftmove도 2로 계산된다. 중복 없는 최하위 값인 상황도 j는 lo보다 작고 leftmove는 1이다. 이런 상황에서는 교체하면 안 된다. i의 경우에는 이런 상황은 오지 않지만 똑같이 마음 편하게 while에 조건을 추가해주자. 그 다음 i와 j를 적절하게 이동시킨다.

int mj = j, mi = i;

while (leftmove-- > 0 && mj >= lo) exch(a, lo + leftmove, mj--);
while (rightmove-- > 0 && mi <= hi) exch(a, hi - rightmove, mi++);

j -= left_same_count;
i += right_same_count;

---

재귀적으로 정렬 반복하기

이제 j+1 ~ i-1 위치에 있는 값들은 평생동안 변하지 않는다! lo ~ j와 i ~ hi 부분에 대해서 다시 정렬해주자. j와 i가 범위를 벗어났다고 해서 걱정할 필요 없다. 바로 아래에서 살펴보듯이 정렬 함수가 본격적으로 실행하기 전에 유효범위를 체크하기 때문이다.

quick_fast3way_sort(a, lo, j);
quick_fast3way_sort(a, i, hi);

---

종료

종료는 간단하다. 범위가 유효하지 않다면 바로 return 하여 함수를 종료시키면 된다. 이 코드는 정렬 함수의 제일 앞부분에 놓도록 한다.

/* 중략 */

if (lo >= hi) return;

/* 중략 */

---

후기

직접 만들었는데 힘들었다. 다음은 결과가 나왔다.

... 중략
your your your your your your your your your your your your your your your 
your your your your your your your your your your your your your your your 
your your your your your your your your your your your your your your your 
your your your your your your your your your your your your your your your 
your your your your your your your your your your your your your your your 
your your your your your your your your your your your youre youre youre 
youre youre youre youre youre youre youre yourn yourn yours yours yours 
yours yours yours yours yours yours yours yours yours yours yours yours 
yours yourself yourself yourself yourself yourself yourself yourself 
yourself yourself yourself yourself yourself yourself yourself yourself 
yourself yourself yourself yourself yourself yourself yourself yourself 
yourself yourself yourself yourself yourself yourself yourself yourself 
yourself yourself yourself yourself yourself yourself yourself yourself 
yourself yourselfflung yourselfthat yourselves yourselves yourselves youth 
youth youth youth youth youth youth youth youth youthful youthful youthful 
youthfulness youths youties youunder youve youve youve youve youve youve 
youve zealous zealous

정렬에 1198 밀리초가 소요되었습니다.
count: 135643

대략 13만개가 넘는 단어들을 정렬하는 데 1초가 좀 더 걸렸다. 빠른 건진 잘 모르겠다.

---

바깥 고리

• 프로젝트