개요
Algorithms 4th edition (로버트 세지윅, 케빈 웨인 지음 | 권오인 옮김 | 길벗) 에서 소개된, 벤틀리(J. Bentley)와 세지윅(R. Sedgewick)이 고안한 빠른 삼중 분할 퀵 정렬 (연습문제 2.3.22) 을 직접 풀어보고자 함.
선 전체 코드
다만, 본 코드로는 직접 실행시키지 못한다. 커다란 데이터 파일을 읽고 실제 출력까지 어떻게 되는지 보기를 원한다면 프로젝트를 직접 실행해보도록 한다.
사용할 때에는 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가 별로 쓸모없으므로 표기하지 않는다.
중복 없는 중간 값
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 3 | p |
2 | ||
1 | ||
5 | ||
hi | 4 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
lo | 3 | |
2 | p | |
1 | j | |
5 | i | |
hi | 4 | q |
이후
id | 값 | 변수 |
---|---|---|
lo | 1 | |
2 | j | |
3 | ||
5 | i | |
hi | 4 | |
중복 있는 중간 값
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 3 | p |
2 | ||
3 | ||
1 | ||
5 | ||
3 | ||
3 | ||
hi | 4 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
lo | 3 | |
3 | ||
2 | p | |
1 | j | |
5 | i | |
4 | q | |
3 | ||
hi | 3 | |
이후
id | 값 | 변수 |
---|---|---|
lo | 2 | |
1 | j | |
3 | ||
3 | ||
3 | ||
3 | ||
5 | i | |
hi | 4 | |
중복 없는 최하위 값
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 3 | p |
5 | ||
4 | ||
7 | ||
hi | 6 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
j | ||
lo | 3 | |
5 | p, i | |
4 | ||
7 | ||
hi | 6 | q |
이후
id | 값 | 변수 |
---|---|---|
j | ||
lo | 3 | |
5 | i | |
4 | ||
7 | ||
hi | 6 | |
아무 것도 움직이지 않는다.
중복 있는 최하위 값
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 3 | p |
5 | ||
3 | ||
4 | ||
7 | ||
3 | ||
6 | ||
hi | 3 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
j | ||
lo | 3 | |
5 | p, i | |
6 | ||
4 | ||
7 | q | |
3 | ||
3 | ||
hi | 3 | |
이후
id | 값 | 변수 |
---|---|---|
j | ||
lo | 3 | |
3 | ||
3 | ||
3 | ||
5 | i | |
6 | ||
4 | ||
hi | 7 | |
중복 없는 최상위 값
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 8 | p |
5 | ||
7 | ||
3 | ||
hi | 4 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
lo | 8 | |
5 | ||
7 | ||
3 | ||
hi | 4 | j, q |
i |
이후
id | 값 | 변수 |
---|---|---|
lo | 4 | |
5 | ||
7 | ||
3 | j | |
hi | 8 | |
i |
중복 있는 최상위 값
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 8 | p |
5 | ||
8 | ||
7 | ||
8 | ||
3 | ||
4 | ||
hi | 8 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
lo | 8 | |
8 | ||
8 | ||
8 | ||
5 | p | |
3 | ||
4 | ||
hi | 7 | q, j |
i |
이후
id | 값 | 변수 |
---|---|---|
lo | 5 | |
3 | ||
4 | ||
7 | j | |
8 | ||
8 | ||
8 | ||
hi | 8 | |
i |
중복 두 개
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 3 | p |
hi | 3 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
j | ||
lo | 3 | |
hi | 3 | |
i, p, q |
이후
id | 값 | 변수 |
---|---|---|
j | ||
lo | 3 | |
hi | 3 | |
i |
아무 것도 움직이지 않는다.
하위값 두 개
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 3 | p |
hi | 4 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
j | ||
lo | 3 | |
hi | 4 | i, p, q |
이후
id | 값 | 변수 |
---|---|---|
j | ||
lo | 3 | |
hi | 4 | i |
아무 것도 움직이지 않는다.
상위값 두 개
이전
id | 값 | 변수 |
---|---|---|
i | ||
lo | 3 | p |
hi | 2 | q |
j |
중간 과정
id | 값 | 변수 |
---|---|---|
lo | 3 | |
hi | 2 | j, p, q |
i |
이후
id | 값 | 변수 |
---|---|---|
lo | 2 | j |
hi | 3 | |
i |
구현
위 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
가 범위를 벗어날 수 있기 때문에 범위를 벗어난 직후에 유효성을 체크하도록 한다. 이는 아래 코드로 설명될 수 있다.
또한 해당 루프의 종료 조건은 무조건 다음과 같아야 한다.
만약 i < j
가 된다면 바로 루프를 종료하는 것이 하나의 방법이 아닌가? 불행히도 아니다. 왜냐하면 중복된 키가 아주 많을 수 있기 때문이다. i
는 같은 기준값의 오른쪽을 의미하고, j
는 왼쪽을 의미한다. i
가 이미 오른쪽 끝에 가 있는 상태에서, j
도 왼쪽 끝에 도달하기 위해 j
는 계속 가감되어야 한다.
같은 값 자리 바꾸기
기본적으로 기준 값과 같다면, a[p]
와 a[i]
를 바꿔주면 된다.
자리바꿈이 중복이 되면 안 된다. 우선 키를 움직이고 비교를 하기 때문에 이미 검사한 항목이 다시 자리바꿈될 여지가 있다. 예를 들어 중복 없는 최하위 값을 보면 비교 값이 이미 최하위 값이기 때문에 i
는 바로 앞에서 멈추어 버리고 j
는 위에서 쏜살같이 내려온다. 이윽고 j
가 첫번째에 도달했을 때, j
가 오른쪽 첫째와 왼쪽 첫째를 바꾸어버린다면, 감시망에 공백이 생긴다. p
미만의 요소들은 무조건 기준 값과 같아야 하는데 그렇지 않게 된 것이다! 이를 위해 자리를 바꾸기 위한 조건으로 i < j
를 추가하였다. 아래 코드에서 확인할 수 있다.
같은 값 제 위치로 이동하기
모든 루프가 끝났다면 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
를 우선 구한다.
이후에 차례대로 바꾼다. 바꿔야 하는 횟수가 남아있음에도 바꾸면 안 되는 상황이 있다. 바로 모든 값이 같은 상황인 중복 두개를 살펴보자. 이 때에는 j
가 lo
보다 작은 상황이고, leftmove
도 2
로 계산된다. 중복 없는 최하위 값인 상황도 j
는 lo
보다 작고 leftmove
는 1
이다. 이런 상황에서는 교체하면 안 된다. i
의 경우에는 이런 상황은 오지 않지만 똑같이 마음 편하게 while
에 조건을 추가해주자. 그 다음 i
와 j
를 적절하게 이동시킨다.
재귀적으로 정렬 반복하기
이제 j+1 ~ i-1
위치에 있는 값들은 평생동안 변하지 않는다! lo ~ j
와 i ~ hi
부분에 대해서 다시 정렬해주자. j
와 i
가 범위를 벗어났다고 해서 걱정할 필요 없다. 바로 아래에서 살펴보듯이 정렬 함수가 본격적으로 실행하기 전에 유효범위를 체크하기 때문이다.
종료
종료는 간단하다. 범위가 유효하지 않다면 바로 return
하여 함수를 종료시키면 된다. 이 코드는 정렬 함수의 제일 앞부분에 놓도록 한다.
후기
직접 만들었는데 힘들었다. 다음은 결과가 나왔다.
대략 13만개가 넘는 단어들을 정렬하는 데 1초가 좀 더 걸렸다. 빠른 건진 잘 모르겠다.