자바 [JAVA] - 팀 정렬 (Tim Sort)
[정렬 알고리즘 모음]
- Tim Sort [팀 정렬]
이번 포스팅의 경우 병합 정렬과 삽입 정렬(그 중 이진 삽입 정렬) 메커니즘을 토대로 하기에 반드시 병합(합병) 정렬과 이진 삽입 정렬을 먼저 보고 오시기를 바란다. (참고로 여기서 다룰 병합 정렬은 Bottom-Up 방식임에 유의하시기를 바란다.)
팀 정렬은 무엇인지부터 알아보자.
일단 팀 정렬은 Tim Peter 에 의해 고안된 Merge Sort(합병 정렬), Insertion Sort(삽입 정렬)이 혼용 된 하이브리드 정렬 알고리즘이다. 좀 더 자세하게 말하자면, 합병정렬을 기반으로 구현하되, 일정 크기 이하의 부분 리스트에 대해서는 이진 삽입 정렬을 수행하는 것이다.
무슨 말인가 하면, 대략적으로 이런 느낌이다.
대략적인 모습은 위와 같다.
그러면 왜 퀵 정렬(Quick Sort)처럼 빠른 속도의 정렬이나 병합 정렬처럼 항시 안정적인 O(NlogN)의 정렬 알고리즘들이 있음에도 이러한 두 가지 정렬 알고리즘을 혼용한 정렬들이 나온 것일까?
일단, 이를 이해하기 위해서는 왜 정렬 알고리즘마다 속도의 차이가 나는지를 생각해보아야 한다.
크게 정렬 알고리즘에서 성능을 미치는 원인은 크게 3가지로 볼 수 있다.
1. 비교 및 스왑을 수행하기 위한 반복자(loop) = 반복자가 어떻게 구현되어있는가의 문제
2. 유효 접근 시간 (지역성)
3. 메모리 소비량
(추가적으로 병렬 작업이 가능한가 정도도 될 수 있다)
그럼 하나씩 한 번 살펴보자.
1번의 경우는 우리가 대표적으로 시간복잡도로 측정 되는 기준이 되기 때문에 크게 설명 할 것은 없을 것이다.
2번의 경우에는 아주아주 간단하게 말해서 CPU에서 참조하는 주소를 읽어들이는데 얼마나 소요되는가다. 쉽게 말해 지역성의 원리를 얼마나 잘 따라주냐에 따라 성능이 좌우된다고 보면 된다.
조금 더 구체적으로 말해보자면 이렇다.
캐시는 CPU 칩 안에 들어가는 매우 빠른 메모리라는 건 아마 대부분 알 것이다. 이 캐시 메모리가 중요한 이유는 프로세서가 매번 메인 메모리에 접근해 데이터를 받아오면 시간이 오래 걸리기 때문에 캐시(Cache)에 자주 참조되는 데이터를 담아두고, 해당 데이터가 필요할 때 메인 메모리 대신 캐시에 접근하도록해 처리 속도를 높인다. (물론 L1, L2, L3 캐시 메모리마다 역할이 조금씩 다른데, 이 부분은 여기서 다룰 내용은 아니니 개괄적으로만 이해하도록 하자)
그러면 캐시를 어떻게 효율적으로 관리하느냐의 문제인데, 결국 캐시에 들어있는 데이터가 얼마나 쓸모있는 데이터가 담겨져 있느냐에 따라 성능이 좌우된다는 것이다. 이를 적중률(Hit-rate)이라고 하는데, 이러한 적중률을 높이기 위한 메커니즘으로는 크게 3가지(혹은 2가지)로 볼 수 있다.
1) 공간 지역성 (군집화(밀도) 정도, 즉, 최근에 접근한 데이터의 주변 공간에 다시 접근하는 경향이 강할 수록 적중률이 높음)
2) 시간 지역성 (최근 접근한 데이터에 다시 접근하는 경향이 높을 수록 적중률이 높음)
3) 순차 지역성 (데이터가 연속적(순차적)으로 접근하려는 경향이 강할 수록 적중률이 높음. 이를 공간 지역성에 포함시키기도 한다)
이 때 우리는 정렬이 목적이지 않는가? 주로 참조되는 때는 비교 및 스왑 과정 일것이다. 이 말은 즉, 결국 같은 비교 및 스왑 횟수를 갖고 있더라도 비교하거나 스왑하는 이벤트 내에서 얼마나 지역성을 만족하는지(요소들이 근처에서 발생하는지)에 따라 성능이 좌우된다는 것이다.
지역성에 대한 예시들 중 대표적으로 행렬 곱의 최적화가 있다. (한 번 검색해서 찾아보시는 것을 강력 추천한다.)
그러면 위에 대한 내용의 연장선상에서 같은 시간 복잡도를 갖는 O(NlogN)의 정렬 알고리즘 중 Heap Sort보다 Quick Sort가 더 빠른지를 설명 할 수 있을 것이다.
Heap Sort는 힙 트리 구조를 활용하기 때문에 부모 혹은 자식 노드를 찾기 위해서는 현재 노드의 절반(1/2) 혹은 두 배씩 이동해야한다. 또한 정렬을 위해 하위 트리부터 루트 트리까지 Heap을 만족하도록 해야하기 때문에 이동하지 않아도 될 불필요한 요소들도 교체될 가능성이 매우 높다.
반면에 Quick Sort(middle pivot 기준)의 경우 피벗을 기준으로 양쪽에서 순차적으로 접근하면서 데이터를 비교하기 때문에 지역성이 높을 뿐더러 교환이 불필요한 요소들을 거의 교환하지 않아 swap비용 자체는 높더라도 교환 횟수의 이점 때문에 평균적으로 성능이 뛰어나다.
필자의 Heap Sort 구현과, Quick Sort 구현 포스팅에서도 정렬되는 과정 영상을 올렸지만, 일단 다시 한 번 갖고와서 봐보도록 하자.
[Heap Sort]
[Quick Sort]
보다시피 Heap정렬은 참조 위치가 연속적이거나 인접성을 띄고 있지 않고, Quick 정렬은 한 라운드마다 하나의 피벗을 두고 양쪽에서 순차접근 하는 방식으로 지역성이 높은 것을 볼 수 있다.
그리고 세 번째로 메모리 소비량이다.
Merge Sort의 경우에는 일반적으로 Quick Sort에 비해 30%정도 비교 횟수는 적지만, 새 Buffer을 생성해야 하기 때문에 메모리 접근이 분산 될 수 밖에 없으며 이동 횟수가 많다는 한계점이 있다. 또한 이미 정렬 된 부분 리스트도 탐색하며 쪼개 들어가야하기 때문에 최선의 시간 복잡도 또한 O(NlogN)을 갖는다.
(물론 Scanning 을 통해 O(N)으로도 만들 수 있지만, 여기서는 일반적인 구현에 대해 이야기하도록 하자.)
그렇다고 Merge Sort가 Quick Sort에 비해 항상 성능이 떨어진다는 것은 아니다. 위 Merge Sort의 특성을 거꾸로 생각해본다면 만약 비교비용이 비쌀 경우에는 Merge Sort가 Quick Sort에 비해 빠를 수도 있기 때문이다. 이 말은, 만약 매우 비싼 비교비용을 갖고있는 대용량 데이터에서는 Merge Sort가 성능상 이점을 볼 수도 있다는 의미다.
또한, Quick Sort에서는 해당 포스팅에서도 다뤘지만, 이미 정렬 된 상태에서의 성능은 O(N2)의 시간 복잡도를 갖게 된다는 단점 또한 존재한다.
이러한 이유로 같은 O(NlogN) 시간복잡도를 갖는 정렬알고리즘이어도 정렬 수행시간이 다르게 된다.
그러면 왜 Tim Sort가 필요한지 대략적으로나마 설명 할 수 있다.
Tim Sort가 만들어진 목적을 먼저 말하자면 현실 데이터들의 종류와 상관 없이 최적으로 정렬을 잘 수행하기 위해서 개발 된 방식이다.
그래서 Java에서 Arrays.sort 를 통해 정렬 할 때 primitive 1차원 배열 타입의 경우 Quick Sort의 심화 구현인 dual-pivot Quick Sort알고리즘으로 정렬이 되고, primitive 타입이 아닌 객체 타입의 배열을 정렬하게 되면 Tim Sort로 정렬되는 이유가 위와 같은 이유다. (참고로 Collections.sort()의 경우 내부에서 List를 Object 배열로 만들어서 Arrays.sort()로 보낸다.)
그래서 Tim Sort가 뭐야?
즉, 현실 데이터들을 잘 정렬하기 위해 개발 된 병합 정렬 + 삽입 정렬(그 중 이진 삽입 정렬)을 혼합 한 하이브리드 정렬이라는 것이다.
위 장단점에서 나왔지만, Quick Sort의 경우 분명 일반적으로 빠르긴 하지만, 특정 상태(정렬 된 상태)에서는 급격히 성능이 떨어지게 된다. 그렇다고 Heap Sort를 쓰자니 지역성이 떨어져 데이터가 얼마나 클지 모르니, 가장 안정적이면서 비교비용이 비쌀 경우에도 이득을 볼 수 있는 병합 정렬이 적절해 보인다.
더군다나 Merge Sort는 안정(stable) 정렬이 가능하기 때문에 현실 데이터에 대해 더욱 알맞은 정렬 방법이기도 하다.
이진 삽입 정렬은 O(N2) 알고리즘임에도 왜 사용되는 것일까? 삽입 정렬의 메커니즘은 각 수행 단계에서 자기가 들어갈 위치를 잡아주게 되는데 구현 자체를 보면 알겠지만, 이미 정렬 된 상태에서는 O(N)의 시간 복잡도를 갖게 된다는 장점과 더불어 매우 작은 리스트에서는 O(NlogN) 정렬 알고리즘들 못지 않게 매우매우 빠른 정렬 수행 속도를 보이기 때문이다.
이유야 당연하긴 하지만, 시간 복잡도는 수행 시간의 점근적 성장도를 나타내는 것이다. 그렇기에 정렬해야 할 리스트가 작을 수록 오버헤드가 상당히 작기 때문에 매우 작은 리스트에서는 정렬 수행시간의 비중이 점근적 시간 복잡도보다 오버헤드가 더 크다.
예로들어 Quick Sort의 경우 O(NlogN)의 같은 정렬 알고리즘 중에서도 매우 빠른 정렬 알고리즘이지만 재귀를 사용하기 때문에 매우 작은 리스트에서는 pivot을 기준으로 재귀적 호출을 하는 과정 자체가 추가적인 오버헤드가 발생하기 때문에 삽입정렬에서 리스트를 정렬하는 비용보다 더 커지기도 한다.
그래서 Tim Sort에서는 일정 사이즈의 부분 리스트를 얻고(divide), 각각의 부분리스트들에 대해 삽입정렬을 수행하며 정렬을 하며(sort), 정렬 된 부분리스트들을 다시 합치는 방식(conqure)을 사용하게 된다.
일단, 지역성이 높으면서, 추가적인 메모리를 최소화 하고, 시간복잡도가 O(NlogN) 이하의 알고리즘을 갖을 수 있도록 해야 정렬이 효율적으로 된다는 건 알았다.
그럼 어떻게 구현해야할지 하나씩 살펴보자.
참고로 이 번 포스팅에서는 처음 보는 개념이 많이 나올 것이다. 최대한 쉽게 설명 해보려고 노력은 하지만, 기본적인 메커니즘을 제대로 이해하지 못한다면 어려울 수 밖에 없으니, 만약 이해가 안된다면 언제든 댓글로 남겨주시기를 바란다.
또한 이전처럼 원소를 하나하나 이미지로 이동하는 과정을 그릴 수는 없다. 그렇기 때문에 이 번 포스팅에서 올라가는 이미지들은 대체로 추상적일 것이다. 이 점 유의하시기를 바란다.
그리고 자바에서 제공하는 Tim Sort의 경우 사소한 것 까지 최적화가 되어있다. 하지만, 이러한 사소한 부분까지 다 다루려고 하면 오히려 Tim Sort의 메커니즘을 이해하는데 방해가 될 것 같아서 크게 중요한 것들 위주로만 구현을 할 예정이다.
- 정렬 방법
앞서 Tim Sort의 정렬 메커니즘에 대해 이미지로 올렸었다.
다시 한 번 보자면 이렇다.
이건 어디까지나 이해를 돕기 위한 대략적인 이미지긴 하지만, 앞으로의 이해를 위해 위 과정을 머리속에 그려놓으면 좋겠다.
다시 한 번 복기해보자면, 분할 작업을 통해 일정 이하의 사이즈가 된다면 이진 삽입 정렬(Binary Insertion Sort)를 사용하여 정렬 하고, 그렇게 정렬 된 여러 부분리스트들을 다시 병합 작업을 하는 것이다.
아주 대략적으로 뼈대만 보자면 이렇다.
void sort(int[] a, int lo, int hi) {
/**
* 처음 들어온 배열이 일정 크기 이하의 배열이라면
* binaryInsertionSort로 정렬해버리고 끝내기
* 보통 해당 임계점(THRESHOLD)은 32정도가 됨.
*/
if(size < THRESHOLD) {
BinarySort(a);
return;
}
while(lo >= hi) {
int size = getSubList(a, lo); // 부분 배열의 길이 구하기 (divide)
// 부분 배열을 이진삽입 정렬로 정렬
BinarySort(a, lo, lo + size);
// 병합해야 할 리스트에 push하고 push 된 목록에 있는 부분리스트들을 합친다. (conqure)
push(a);
merge();
lo += size;
}
}
아주아주 대략적으로 이렇다는 것이다. 대강 느낌만 잡을 수 있게 생략한 것일 뿐이니 전체적으로 이런 구조구나~ 하고만 보시면 된다.
여기서 오늘 우리는 위 분할 과정에서 발생한 부분리스트를 'run'이라고 부르도록 하자. 즉, 쉽게말해 각 쪼개진 덩어리를 run이라고 보는 것이다.
그러면 한 가지 의문점이 들 수 있다. 대체 어느정도 사이즈에서 이진 삽입 정렬을 수행하면 좋은가요?
일반적으로는 10개 정도 내외의 사이즈에 대해 삽입 정렬이 효율이 좋다고 한다. 다만, 이후에 사용 할 병합정렬의 특성상 2x 개의 run이 생성 되는 것이 이상적이기 때문에(이후 설명) 적절하게 32 미만의 리스트에 대해서는 이진삽입 정렬을 수행하고 종료하도록 임계점을 잡도록 하자. (어디까지나 경험적 측정치라 사용자의 환경에 따라 달라질 수 있긴 하다.)
그러면 우리가 필요한 정렬 방식은 크게 두 가지 방식인 것을 확인 할 수 있다.
바로 Merge Sort와 Binary Insertion Sort라는 것이다.
왜 삽입 정렬이 아닌, 이진 삽입 정렬인가 궁금 하실 수도 있을 것 같아 짧게 답해드리자면, 앞서 Tim Sort의 목적은 현실 데이터를 정렬하고자 하는 목적으로 고안되었다고 했다. 이는 결국 비교비용이 상대적으로 비쌀 가능성이 높다는 의미이기도 하다.
일반적인 primitive 타입의 배열에서는 삽입 정렬이 이진 삽입 정렬에 비해 빠르지만, 비교 비용이 비쌀 수록 이진 삽입 정렬이 오히려 성능상 이점을 갖고오기 때문이다.
(이에 대한 내용은 이진 삽입 정렬 구현 부분의 정렬 방법에서 그 차이를 보여주고 있으니 참고하시기를 바란다.)
일단, 가장 작은 단위에서는 이진 삽입 정렬을 사용하니, 필자가 구현했었던 이진 삽입 정렬, 그 중 '심화 구현' 코드를 그대로 갖고 사용 할 것이다. 코드는 다음과 같다.
[이진 삽입 정렬 코드]
public static void BinaryInsertionSort(int[] a) {
if(a.length < 2) {
return;
}
int incLength = getAscending(a, 0, a.length);
binaryInsertionSort(a, 0, a.length, incLength);
}
/**
*
* @param a 정렬 할 배열
* @param lo 정렬 할 배열 구간의 하한선(a[lo] 포함)
* @param hi 정렬 할 배열 구간의 상한선(a[hi] 미포함)
* @param start 정렬 할 배열의 원소 탐색 시작점
*/
private static void BinaryInsertionSort(int[] a, int lo, int hi ,int start) {
// 만약 start와 lo가 같다면 이분 탐색 시작점은 lo + 1부터이므로 start을 1 증가시킨다.
if(lo == start) {
start++;
}
/*
* start 이전 원소들은 이미 오름차순으로 정렬 된 상태이므로
* start부터 시작하여 이분 탐색 및 시프팅을 통해 삽입정렬을 해준다.
*/
for (; start < hi; start++) {
// 타겟 넘버
int target = a[start];
int loc = binarySearch(a, target, lo, start);
int j = start - 1;
// 타겟이 들어갈 위치보다 큰 원소들을 뒤로 미룬다.
while (j >= loc) {
a[j + 1] = a[j]; // 이전 원소를 한 칸씩 뒤로 미룬다.
j--;
}
/*
* 위 반복문에서 탈출 하는 경우 앞의 원소가 타겟보다 작다는 의미이므로
* 타겟 원소는 j번째 원소 뒤에 와야한다. 그러므로 타겟은 j + 1 에 위치하게 된다.
*/
a[loc] = target;
}
}
// 이분 탐색
private static int binarySearch(int[] a, int key, int lo, int hi) {
int mid;
while (lo < hi) {
mid = lo + ((hi - lo) / 2);
// 안장 정렬을 위해 key가 a[mid]보다 작을 때만 상한선을 옮긴다.
if (key < a[mid]) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return lo;
}
// lo 부터 몇 개의 원소가 오름차순 혹은 내림차순인지를 반환하는 메소드
private static int getAscending(int[] a, int lo, int hi) {
int limit = lo + 1;
if (limit == hi) { // lo + 1 == hi 라는 것은 결국 정렬 할 원소가 a[lo] 1개 뿐이라는 의미다.
return 1;
}
// 오름차순 일 경우 (안정 정렬을 위해 같은 경우까지 포함)
if (a[lo] <= a[limit]) {
// 오름차순일 때까지 반복한다. (limit이 hi 범위를 벗어나면 안된다.)
while (limit < hi && a[limit - 1] <= a[limit]) {
limit++;
}
}
// 내림차순 일 경우
else {
while (limit < hi && a[limit - 1] > a[limit]) {
limit++;
}
reversing(a, lo, limit); // 내림차순의 경우엔 오름차순으로 변경해주어야 함
}
return limit - lo;
}
// 원소를 뒤집어준다.
private static void reversing(int[] a, int lo, int hi) {
// a[lo] <= a[i] < a[hi] 범위이므로 마지막 인덱스는 hi - 1부터 시작된다.
hi--;
while (lo < hi) {
int temp = a[lo];
a[lo] = a[hi];
a[hi] = temp;
lo++;
hi--;
}
}
그러면 각 run에 대해 이진 삽입 정렬을 한다는 건 위 코드를 사용하면 된다는 것은 알겠다. 그러면 가장 중요한 과제인 'run을 어떻게 나눌 것이며, 각 정렬 된 run을 어떻게 병합할 것인지'를 구현하는 문제가 남아있다.
먼저 하나의 서브리스트, 즉 run을 만드는 방법부터 알아보자.
[Run 만들기]
우리는 결국 병합정렬에 쓰일 하나의 블럭을 만들어야 한다.
이 떄, 앞서 필자가 계속 언급했던 것이 있다. 바로 최적화다. Merge Sort의 단점이 무엇일까?
첫 번째로 정렬 된 상태와 상관 없이 항상 일정한 방식으로 쪼개가면서 탐색한다는 것이다. 결국 이미 정렬 된 상태에 대해서도 블럭을 쪼갠다는 것인데, 굳이 우리는 그럴 필요가 있을까? 이 점에 대해서 어떻게 해결해야 할 것인지를 고려해보아야 한다.
두 번째로 추가 배열(buffer)을 별도로 선언해야 하기 때문에 공간 복잡도가 O(N)이라는 것이다. (물론 이 부분도 Linked 형식으로 공간복잡도를 O(1)로 줄일 수 있지만, 이 마저도 오히려 linked 형식은 메모리 엑세스가 느리다는 단점과 제대로 구현되지 않는다면 오히려 시간 복잡도가 증가하여 더욱 성능이 나빠질 수 밖에 없다.)
즉, 우리는 추가적인 배열을 사용하더라도 최소한으로 할당 할 수 있는 방법을 찾아야 할 것이다.
그러면 위 두가지를 유념하면서 어떻게 하면 최적화를 할 수 있을지 함께 고민해보자.
일단, 위 문제를 풀기 전에 우리가 최소로 할 run의 사이즈를 정해야 한다. 그래서 일정 이상의 사이즈 이하로는 이진 삽입 정렬로 정렬해야하지 않겠는가?
어느 값이 적당한가는 각자의 판단에 따라 다르기는 하겠지만, merge sort의 기본 메커니즘을 생각하면 어떤 값들을 사용하면 좋은지를 판단 할 수 있다.
Merge Sort가 왜 O(NlogN)의 시간 복잡도를 갖는가? 바로 전체 리스트를 '절반씩' divide하고 conqure하기 때문이다. 이는 조금만 생각해보자면 부분리스트 개수는 (여기서는 run) 2𝑥 에 가깝게 갖는다는 것이다.
즉, run의 최소 사이즈도 전체 배열에 대해 최소 사이즈로 나누었을 때 2𝑥 에 가깝게 갖는 것이 최악의 상황에서도 O(NlogN)의 시간 복잡도를 유지할 수 있을 것이다.
자바에서 또한 24~25((THRESHOLD / 2) ≤ minRun ≤ THRESHOLD)사이의 최소 run의 길이를 갖도록 설계되어 있으며 얻어진 minRun을 전체 배열로 나눌 때 나오는 부분리스트의 개수가 2𝑥 를 초과하지 않게 한다.
그러면 최소 run의 size를 구하는 메소드를 먼저 만들어보자.
원리 자체는 간단하다. 전체 배열의 사이즈에 대해 2로 나누어 들어가면서 16 ~ 32 사이의 값에 안착할 때 까지 반복해주면 된다.
/*
* arrayLength / runSize 이 2의 제곱근에 가까울수록 좋음(병합정렬 특성)
* 즉, 나오는 수는 (THRESHOLD / 2) <= runSize <= THRESHOLD 사잇값이 됨.
*
* 이를 구하기 위해 runSize을 THRESHOLD(32) 보다 작을 떄 까지 2씩 매 번 나눠가며
* runSize 로 나눴을 때 근접하도록 한다.
*
* arrayLength / runSize 이 2의 제곱근에 가까울수록 좋기 떄문에
* runSize로 나눴을 때 2의 거듭제곱 값을 초과하지 않는게 좋다.
*/
public static int minRunLength(int runSize) {
/*
* 이 때 만약 연산 과정 중
* 홀수로 떨어지는 경우에는 runSize 를 1 증가시켜야 한다.
* 즉, (runSize + 1)의 사이즈를 갖고있어야
* 배열의 길이 / runLength 가 2^n을 초과하지 않는다.
*
* ex)
* array Length : 434
*
* [1을 더하지 않을 경우]
* (과정 : 434 -> 217 -> 108 -> 54 -> 27)
* result runSize : 27
* 434 / 27 = 16 and 나머지 : 2
* 나머지도 결국 정렬되어야 하기 때문에 총 17개의 블럭이 생김
*
* [1을 더 할 경우]
* (과정 : 434 -> 217 -> 108 -> 54 -> 27)
* 217에서 홀수가 되었기 때문에 결과값에 1 을 더함
* result runSize : 27 + 1 = 28
* 434 / 28 = 15 and 나머지 : 14
* 나머지를 포함하면 총 16개의 블럭이 생김
*
* [test code]
```
for(int arrayLength = 16; arrayLength < 12345; arrayLength++) {
System.out.println("arrays length = " + arrayLength +
"\tminRunLength = " + minRunLength(arrayLength) +
"\tarrayLength/runLength = " + (arrayLength / minRunLength(arrayLength)));
}
```
*/
int r = 0; // 홀 수가 발생할 때 2^x가 초과되지 않도록 하는 여분의 수
while(runSize >= THRESHOLD) {
if(runSize % 2 == 1) {
r = 1;
)
runSize /= 2;
}
return runSize + r;
}
위 주석에서도 설명했지만, 2로 나누어 들어갈 때 우리는 최악의 경우에도 2의 제곱수의 개수의 run이 생성 될 수 있도록 만들어야 한다.
여기서 2로 나눈 나머지가 발생한다는 것은 무엇일 까?
쉽게 이해해보자면 이렇다.
11개의 요소를 갖는 리스트가 있다. 이 때 2로 나누어 run의 길이를 찾는다고 한다면, (11 / 2) = 5 -> (5 / 2) = 2 으로 run의 길이가 2가 되었다고 가정해보자. 그러면 총 5개의 run이 생성되는 것처럼 보이지만, 사실 나머지가 발생했다는 건 결국 리스트가 부분적으로 남는다는 의미랑 같다.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 의 리스트를 2개씩 쪼개면 다음과 같이 쪼개진다는 것이다.
[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11]
즉, run의 개수는 6개로 2의 제곱수 4 혹은 8과는 거리가 멀다.
이러한 것을 가장 쉽게 보정하는 방법으로는 run의 길이를 1 늘려주는 것이다.
만약 run의 사이즈가 3이라면 다음과 같이 쪼개질 것이다.
[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11]
이렇게 되면 run의 개수는 4개로 2x 조건에 알맞게 된다.
즉, 2𝛂-1 ≤ (arrayLength / minRun) ≤ 2𝛂 범위에서 2𝛂 을 초과하지 않으면서 2𝛂-1 혹은 2𝛂 에 가깝게 만들고자 하기 위한 목적이다.
필자가 주석으로 test code도 포함했으니 한 번 테스트를 해보셔도 좋을 것 같다.
위 코드를 좀 더 간결하고 훨씬 빠르게 만드는 방법도 있다.
비트연산자를 조금만 생각해보면 쉽다.
/**
* 최소 길이의 run 크기, 즉 minRun을 구하기 위한 메소드
*
* @param runSize minRun을 구하고자 하는 초기 배열의 길이
*/
public static int minRunLength(int runSize) {
int r = 0; // 홀 수가 발생할 때 2^x가 초과되지 않도록 하는 여분의 수
/*
* (runSize & 1) 을 하면, runSize의 가장 오른쪽 비트가 1일 경우에는
* 홀수이므로 1이 반환 될 것이고, r = r | (runSize & 1) 에서 r은 1로 될 것이다.
* 한 번 r이 1로 되면 OR 연산자의 특성상 이 값은 바뀌지 않는다.
*/
while(runSize >= THRESHOLD) {
r |= (runSize & 1);
runSize >>= 1;
}
return runSize + r;
}
위 처럼 최소 run의 길이를 만들어주는 메소드를 만들었다.
이제 본격적으로 먼저 첫 번째 문제점을 보자. 이미 정렬 된 상태에 대해서도 블럭을 쪼갠다는 점이 문제였는데, 이는 조금만 돌려서 말하면 불필요하게 병합해야할 부분리스트들이 많이 생성된다는 것이다.
즉, 이 문제의 포인트는 '병합 해야 할 부분 리스트를 최소화' 해야 한다는 점이다.
이를 어떻게 해결해야 할까? 이 부분은 필자가 이진 삽입 정렬 중 심화 구현에서 다루었던 오름차순 부분 배열을 얻어내는 방식으로 해결하면 된다. 즉, 앞서 이진 삽입 정렬 코드 부분에서 getAscending() 메소드를 사용하면 된다. (내림차순의 경우에는 해당 구간을 뒤집어 오름차순으로 만들어준다.)
위에서 만든 minRunLength() 메소드에 의해 구해진 최소 run의 길이를 갖게 하되, 만약 해당 run 이후의 원소들까지 정렬상태라면 해당 부분까지 포함시켜서 run을 최대한 크게 만들어 병합 해야할 run의 개수를 최대한 줄이는 것이다.
좀 더 쉽게 말하자면, 먼저 리스트에 대해 최대한 오름차순, 혹은 내림차순으로 되어있는 부분을 구한다.
만약에 구해진 정렬 된 구간이 minRun보다 크다면 해당 부분은 정렬 할 필요없이 바로 병합 정렬의 대상으로 해당 구간을 run으로 잡는다.
반대로 정렬 된 구간이 minRun보다 작다면 정렬 된 구간을 포함하여 minRun의 길이만큼 run을 잡은 뒤, 해당 run을 이진 삽입 정렬로 정렬한 뒤에 병합정렬의 대상으로 만든다는 것이다.
예로들어 minRun이 6이라고 가정할 때, 그림으로 보면 다음과 같다.
[정렬 된 구간이 minRun보다 작을 때]
[정렬 된 구간이 minRun보다 클 때]
위와 같이 정렬 된 구간과 minRun의 길이 중 큰 쪽으로 run의 사이즈를 잡아 하나의 run을 만들어주는 것이다.
이 때, 만약 정렬 된 구간이 minRun보다 작을 때의 해당 run은 정렬 된 상태가 아니다. 그러므로 해당 run은 이진삽입정렬로 정렬해주어야 한다.
코드로 보면 다음과 같다.
public static void sort(int[] a, int lo, int hi) {
int remain = hi - lo;
// 정렬해야 할 원소가 1개 이하일 경우 정렬 할 필요가 없다.
if(remain < 2) {
return;
}
/**
* 일정 크기(여기선 32) 미만의 배열이라면
* binaryInsertionSort로 정렬 뒤 바로 반환
*
* @see BinaryInsertionSort.BinaryInsertionSort
*/
if(remain < THRESHOLD) {
int increaseRange = getAscending(a, lo, hi);
BinarySort(a, lo, hi, lo + increaseRange);
return;
}
IntMergeStack ims = new IntMergeStack(a); // 추후 구현
int minRun = minRunLength(remain); // run의 최소 길이
do {
/*
* 정렬 된 구간의 길이를 구한다.
*/
int runLen = getAscending(a, lo, hi);
/*
* 만약 정렬 된 부분의 길이가 minRun 보다 작다면
* 정렬 된 부분 길이를 포함한 부분 배열에 대해
* 이진 삽입 정렬을 시행한다.
*/
if(runLen < minRun) {
/*
* [lo : lo+minRun] 구간에 대해 정렬
*
* counts : run에 있는 요소의 총 개수
* 이 때 최소 run 크기가 남은 원소 개수보다 클 수 있으므로 이를 처리해준다.
*/
int counts = remain < minRun ? remain : minRun;
/*
* BinarySort(array, lo, hi, start);
* index[lo] ~ index[lo + counts] 구간을 삽입 정렬을 하되,
* index[lo + runLen] 부터 삽입정렬을 시작함.
* (앞서 구한 오름차순 길이인 runLen에 의해 lo + runLen의 이전 인덱스는 이미 오름차순 상태임)
*/
BinarySort(a, lo, lo + counts, lo + runLen);
// 이진 삽입 정렬이 수행되었기에 증가하는 길이는 endPoint가 된다.
runLen = counts;
}
// stack에 run의 시작점과 해당 run의 길이를 스택에 push한다. (추후 구현)
ims.pushRun(lo, runLen);
ims.merge();
lo += runLen; // 다음 시작점을 가리켜야 하므로 runLen만큼 증가
remain -= runLen; // 정렬 해야 할 원소 개수를 줄여야 하므로 runLen만큼 감소
} while(remain != 0); // 정렬 해야 할 원소가 0개가 될 때 까지 반복
ims.mergeForce(); // 추후 구현
}
/*
[ BinaryInsertionSort 메소드들 모두 중략 ]
*/
위와 같이 작성 된다.
여기서 IntMergeStack의 경우 바로 다음 부분에서 구현해야 할 부분이므로 일단 무시하고 run의 길이를 잡는 원리 위주로 보시면 된다.
이 때 주의해야 할 점은, run을 잡을 때 최소 길이가 있을 것이다. 하지만 남은 원소 개수보다 클 경우도 발생할 수 있다.
무슨 말인가 하면 이렇다.
만약에 minRun이 4라고 가정해보고 아래 배열을 분할해보자.
[3, 1, 4, 7, 6, 5, 8]
첫 번째 run은 다음과 같이 분할 될 것이다.
run A = [3, 1, 4, 7]
그 다음에는 나머지 원소들이 하나의 run으로 분할 된다.
run B = [6, 5, 8]
위에서 보면 run B는 남은 원소의 개수가 minRun(4)보다 작다. 이럴 경우 만약 minRun과 remain 중 작은 것으로 run을 잡아주지 않게 된다면 기존 배열 인덱스 범위 밖을 참조하게 되어 IndexOutOfBoundsException이 발생할 수 있다. 그러므로 반드시 위 과정을 거쳐주도록 하자.
이제 두 번째로 run에 대한 관리, 즉 Merge를 어떠한 방식으로 사용해야할지를 고민해야 한다.
앞서 코드로 잠깐 보여주긴 했지만, Stack 형식으로 run을 Merge하는 방식으로 구현된다. 그러면 왜 stack 방식을 사용할까 한 번 알아보자.
Merge Sort의 단점을 다시 한 번 복기해보자. 바로 추가적인 메모리를 많이 소비하게 된다는 것이다. 합병 정렬을 구현해보면 각 서브 리스트들은 정렬 된 상태이지만, 이는 독립 된 각 서브리스트에 대해 정렬 된 상태일 뿐 전체가 정렬 된 상태는 아니라 두 개의 서브리스트를 합치는 과정에서 두 개의 서브리스트를 훑어가면서 임시 배열에 담았다가 원본 배열로 다시 copy 하는 과정을 거쳐간다.
혹은 한 개의 서브리스트를 임시배열에 담고, 원본 배열에 담는 방식으로도 가능하지만, 어떤 방식이든 O(N)의 추가적인 메모리를 소비하게 되고, 앞서 말했던 메모리 접근이 분산 되게 되어버린다.
그렇다고 병합정렬을 하기 위해서는 추가적인 메모리를 안쓸수도 없는 노릇이다. 그러면 어떻게 추가 메모리를 최소화 할 수 있을까?
의외로 답은 간단하다. 병합해야 할 배열 자체를 넣는 것이 아니라 병합해야 할 지점(index)만 기록하는 것이다.
쉽게 말해 '각 run의 시작점'과 '각 run의 길이'를 차례대로 스택에 기록하면서 쌓아두는 것이다.
예로들어 다음과 같이 말이다.
위와 같이 두 개의 stack을 생성하여 여기에 각 run의 시작점(base)과 길이(length)를 두는 것이다.
" 그러면... stack 원리를 이용한다는 것은 알겠는데, 얼마만큼의 스택 크기를 갖고있어야 하는 건가요? "
혹은
" 만약 최소길이로만 모든 run이 구성 되면 결국 stack도 커지는 거 아닌가요? "
라는 질문이 있을 수 있겠다.
맞다. 위와 같이 쌓이는 기준 없이 그냥 stack에 쌓아두면 앞서 원했던 추가적인 메모리를 최소화 하는 것과는 거리가 멀어진다. 그러면 어떻게 하라는 걸까?
일단, 위에서 run을 새로 만들어서 stack에 push할 때마다 병합을 할지 말지를 결정하게 되는데, TimSort에서는 stack의 크기를 최소화하면서 이 후에 있을 최종적인 병합을 매우 효율적으로 하기 위해 다음과 같은 기준을 정의하고 있다.
이게 무슨 말일까? 좀 더 직관적으로 이해하기 쉽게 이미지로 한 번 보도록 하자.
(runLength는 정수 값만 갖고 있다. 하지만, 이해를 돕기 위해 값에 대해 길이로 표현 한 것이니 오해 없길 바란다.)
위와 같이 상위 스택 3개의 원소에 대해 위와 같은 기준을 만족하도록 쌓는 것이다.
만약 만족하지 못하면 이 때 '병합'을 하는 것이다. 즉, 위 두 가지 조건을 모두 만족시키지 못할 경우 병합 과정을 통해 위 조건을 만족할 때 까지 병합하는 것이 포인트다.
이 때 병합 하는 과정에서 이후 설명하겠지만, 최대한 비슷한 크기끼리 뭉치도록 만들어야 한다.
조건 2는 바로 직관적으로 이해하기 쉽고 단일 경우의 수라 크게 어렵진 않으나, 3개의 run을 비교해야하는 조건 1의 경우 크게 두 가지 경우가 발생한다. 일단 가장 일반적인 경우의 수다.
[경우 1]
(물론 위 과정에서 끝나지는 않는다. A+B 는 또다시 C와 D를 갖고 두 가지 조건을 만족하는지를 반복하는데, 위 경우도 만족하지 못하므로 또 다시 병합 될 것이다.)
그리고 새로 push 된 run이 C보다 클 수도 있다.
[경우 2]
보면 run A와 C의 대소 관계에 따라 병합하는 두 run이 다르다는 것을 알 수 있다. 이 부분은 일단 이렇다는 것 까지만 알아두고 이후 merge 구현에서 자세하게 알아보도록 하자.
결과적으로 정리하자면, 새로운 run이 스택에 추가되면 위 조건에 맞는지를 검사하고 맞지 않다면, stack 조건을 만족시키면서 최대한 유사한 크기 끼리 병합을 할 수 있게 만드는 것이다.
그러면 왜 위 과정이 stack의 크기를 줄일 수 있느냐는 질문이 있을 수 있다.
생각해보자.
runLength[i - 3] > runLength[i - 2] + runLength[i - 1]
이 공식이 무언가랑 비슷해보이지 않은가? 바로 '피보나치 수 공식'과 매우 닮아있다.
an = an-1 + an-2 이라는 공식과 같은 원리다.
그러면 실제로 minRunLength() 메소드에 의해 아무리 작아도 run의 길이는 16부터 갖을 수 있다.
이를 토대로 runLength[i - 3] > runLength[i - 2] + runLength[i - 1] 이 공식에 맞게 최악의 경우를 구해본다면 이렇다.
16, 17, 34, 52, ...
실제로 위 최악의 수를 모두 구해보면 다음과 같다.
void test() {
long f = 16;
long t = 17;
long sum = 0;
for(int i = 1; i < 50; i++) {
sum += f;
System.out.println(i + " : " + f + "\t\tsum : " + sum);
long temp = f;
f = t ++;
t += temp;
}
}
[결과]
1 : 16 sum : 16
2 : 17 sum : 33
3 : 34 sum : 67
4 : 52 sum : 119
5 : 87 sum : 206
6 : 140 sum : 346
7 : 228 sum : 574
8 : 369 sum : 943
9 : 598 sum : 1541
10 : 968 sum : 2509
11 : 1567 sum : 4076
12 : 2536 sum : 6612
13 : 4104 sum : 10716
14 : 6641 sum : 17357
15 : 10746 sum : 28103
16 : 17388 sum : 45491
17 : 28135 sum : 73626
18 : 45524 sum : 119150
19 : 73660 sum : 192810
20 : 119185 sum : 311995
21 : 192846 sum : 504841
22 : 312032 sum : 816873
23 : 504879 sum : 1321752
24 : 816912 sum : 2138664
25 : 1321792 sum : 3460456
26 : 2138705 sum : 5599161
27 : 3460498 sum : 9059659
28 : 5599204 sum : 14658863
29 : 9059703 sum : 23718566
30 : 14658908 sum : 38377474
31 : 23718612 sum : 62096086
32 : 38377521 sum : 100473607
33 : 62096134 sum : 162569741
34 : 100473656 sum : 263043397
35 : 162569791 sum : 425613188
36 : 263043448 sum : 688656636
37 : 425613240 sum : 1114269876
38 : 688656689 sum : 1802926565
39 : 1114269930 sum : 2917196495
40 : 1802926620 sum : 4720123115
41 : 2917196551 sum : 7637319666
42 : 4720123172 sum : 12357442838
43 : 7637319724 sum : 19994762562
44 : 12357442897 sum : 32352205459
45 : 19994762622 sum : 52346968081
46 : 32352205520 sum : 84699173601
47 : 52346968143 sum : 137046141744
48 : 84699173664 sum : 221745315408
49 : 137046141808 sum : 358791457216
보면 run의 총 길이, 쉽게 말해 총 배열의 길이가 생성할 수 있는 최대 길이인 약 21억의 길이를 갖고있는 상태에서 모든 부분 런이 stack 조건을 만족하여 최악으로 모두 쌓이더라도 필요한 스택은 40개를 넘지 않게 된다.
즉, 우리는 runBase와 runLength 배열 모두 40 크기로 생성만 해주면 된다.
그러면 한 번 int형 배열에 대한 병합정렬 역할을 하는 stack 구조 클래스를 하나 만들어서 생성해보자. (필자의 경우 TimSort 클래스 내에 생성 할 것이기 때문에 static 클래스로 만들어 줄 것이다.)
private static class IntMergeStack {
private int[] array;
private int[] runBase;
private int[] runLength;
private int stackSize = 0; // run 스택의 원소 개수를 가리킬 변수
public IntMergeStack(int[] a) {
this.array = a;
int len = a.length;
runBase = new int[40];
runLength = new int[40];
}
}
그러면 앞서 이진삽입 정렬에서 크게 두 가지 메소드를 볼 수 있었다.
runPush() 메소드와, 바로 위에서 설명한 merge()에 대한 것이다.
일단, runPush()의 경우 우리가 들어가야 할 것은 각 런의 시작점과 길이였다. 즉, 다음과 같이 만들면 되겠다.
private static class IntMergeStack {
private int[] array;
private int[] runBase;
private int[] runLength;
private int stackSize = 0; // run 스택의 원소 개수를 가리킬 변수
public IntMergeStack(int[] a) {
this.array = a;
int len = a.length;
runBase = new int[40];
runLength = new int[40];
}
public void pushRun(int runBase, int runLen) {
this.runBase[stackSize] = runBase;
this.runLength[stackSize] = runLen;
stackSize++;
}
}
이쯤이면 글이 길어져서 도대체 뭘 한거지? 싶을 수 있을 것 같아 run을 만들고 관리하는 방법까지 작성한 코드들을 한 번 정리해보자.(merge 과정만 뺀 나머지)
[중간 코드]
public class TimSort {
private static final int THRESHOLD = 32;
/**
* 최소 길이의 run 크기, 즉 minRun을 구하기 위한 메소드
*
* @param runSize minRun을 구하고자 하는 초기 배열의 길이
*/
public static int minRunLength(int runSize) {
int r = 0; // 홀 수가 발생할 때 2^x가 초과되지 않도록 하는 여분의 수
/*
* (runSize & 1) 을 하면, runSize의 가장 오른쪽 비트가 1일 경우에는
* 홀수이므로 1이 반환 될 것이고, r = r | (runSize & 1) 에서 r은 1로 될 것이다.
* 한 번 r이 1로 되면 OR 연산자의 특성상 이 값은 바뀌지 않는다.
*/
while(runSize >= THRESHOLD) {
r |= (runSize & 1);
runSize >>= 1;
}
return runSize + r;
}
// merge에 대해 관리할 내부 정적 클래스
private static class IntMergeStack {
private int[] array;
private int[] runBase;
private int[] runLength;
private int stackSize = 0; // run 스택의 원소 개수를 가리킬 변수
public IntMergeStack(int[] a) {
this.array = a;
int len = a.length;
runBase = new int[40];
runLength = new int[40];
}
public void pushRun(int runBase, int runLen) {
this.runBase[stackSize] = runBase;
this.runLength[stackSize] = runLen;
stackSize++;
}
// merge 구현 필요
}
public static void sort(int[] a) {
sort(a, 0, a.length);
}
public static void sort(int[] a, int lo, int hi) {
int remain = hi - lo;
// 정렬해야 할 원소가 1개 이하일 경우 정렬 할 필요가 없다.
if(remain < 2) {
return;
}
/**
* 일정 크기 이하의 배열이라면
* binaryInsertionSort로 정렬 뒤 바로 반환
*
* @see BinaryInsertionSort.BinaryInsertionSort
*/
if(remain < THRESHOLD) {
int increaseRange = getAscending(a, lo, hi);
BinarySort(a, lo, hi, lo + increaseRange);
return;
}
// run을 관리하고 merge 할 클래스 객체 생성
IntMergeStack ims = new IntMergeStack(a);
int minRun = minRunLength(remain); // run의 최소 길이
do {
/*
* 정렬 된 구간의 길이를 구한다.
*/
int runLen = getAscending(a, lo, hi);
/*
* 만약 정렬 된 부분의 길이가 minRun 보다 작다면
* 정렬 된 부분 길이를 포함한 부분 배열에 대해
* 이진 삽입 정렬을 시행한다.
*/
if(runLen < minRun) {
/*
* [lo : lo+minRun] 구간에 대해 정렬
*
* counts : run에 있는 요소의 총 개수
* 이 때 최소 run 크기가 남은 원소 개수보다 클 수 있으므로 이를 처리해준다.
*/
int counts = remain < minRun ? remain : minRun;
/*
* BinarySort(array, lo, hi, start);
* index[lo] ~ index[lo + counts] 구간을 삽입 정렬을 하되,
* index[lo + runLen] 부터 삽입정렬을 시작함.
* (앞서 구한 오름차순 길이인 runLen에 의해 lo + runLen의 이전 인덱스는 이미 오름차순 상태임)
*/
BinarySort(a, lo, lo + counts, lo + runLen);
// 이진 삽입 정렬이 수행되었기에 증가하는 길이는 endPoint가 된다.
runLen = counts;
}
// stack에 run의 시작점과 해당 run의 길이를 스택에 push한다.
ims.pushRun(lo, runLen);
ims.merge();
lo += runLen;
remain -= runLen;
} while(remain != 0); // 정렬 해야 할 원소가 0개가 될 때 까지 반복
ims.mergeForce(); // 추후 구현
}
// 이진 삽입 정렬 코드
private static void BinarySort(int[] a, int lo, int hi ,int start) {
if(lo == start) {
start++;
}
for (; start < hi; start++) {
int target = a[start];
int loc = binarySearch(a, target, lo, start);
int j = start - 1;
while (j >= loc) {
a[j + 1] = a[j];
j--;
}
a[loc] = target;
}
}
private static int binarySearch(int[] a, int key, int lo, int hi) {
int mid;
while (lo < hi) {
mid = (lo + hi) >>> 1;
if (key < a[mid]) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return lo;
}
private static int getAscending(int[] a, int lo, int hi) {
int limit = lo + 1;
if (limit == hi) {
return 1;
}
if (a[lo] <= a[limit]) {
while (limit < hi && a[limit - 1] <= a[limit]) {
limit++;
}
}
else {
while (limit < hi && a[limit - 1] > a[limit]) {
limit++;
}
reversing(a, lo, limit);
}
return limit - lo;
}
private static void reversing(int[] a, int lo, int hi) {
hi--;
while (lo < hi) {
int temp = a[lo];
a[lo++] = a[hi];
a[hi--] = temp;
}
}
}
(이진 삽입 정렬 코드는 이전 포스팅에서 그대로 갖고왔기 때문에 실제로 구현한 것은 아직 그렇게 많은 것은 아니지만 뭔가 많아보이는 느낌...)
일단, 한 번 정리하고 넘어가보자.
1. 일정 크기의 run을 잡고 만약 run이 정해진 크기 이하일 경우에는 이진 삽입 정렬(Binary Insertion Sort)를 수행한다.
2. 해당 run을 stack에 push한다.
3. stack에서는 두 가지 조건을 만족하도록 쌓여야 하며, 조건을 만족하지 못할경우 병합을 해둔다.
그러면 우리가 1번 2번은 구현이 끝났으니 이제 merge()를 하는 과정을 한 번 살펴보자.
[Merge 구현하기]
일단 스택에 쌓일 수 있는 조건부터 다시 한 번 보자.
run이 새로 push되면 다음으로 merge() 메소드를 실행하게 될 것인데, 이 때 위 두 가지 조건을 만족할 때 까지 merge를 해주는 것이다. 위 예시에서는 한 개만 병합하는 과정을 보여주었지만, 경우 1에서도 보았듯, 사실 두 run을 병합하게 되더라도 위 조건을 항상 만족하지는 않기 때문이다.
위로 스크롤 하기 불편하실 것 같아 더 보기로 1번 조건에 따른 두 가지 경우의 수를 남겨두겠다.
[경우 1]
[경우 2]
위 두 경우의 수에서 차이점은 A와 C의 대소 관계에서 merge하는 두 run이 달라졌다. 이렇게 최대한 병합하여 최소한으로 병합하면서 상위 스택의 두 run이 서로 비슷한 run의 크기를 갖도록 만드는 과정을 거치는 것이다.
그러면 다음과 같이 조건식을 작성 할 수 있겠다.
private static class IntMerge {
// ... 생성자 및 pushRun 등 생략 ... //
public void merge() {
/*
기본 적인 메커니즘
1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
2. runLen[i - 2] > runLen[i - 1]
*/
while (stackSize > 1) {
// 1번 조건 C > B + A 에 위배 될 경우 (== C <= B + A 일 경우)
if (stackSize > 2 && runLength[stackSize - 3] <= runLength[stackSize - 2] + runLength[stackSize - 1]) {
// C < A가 크다면 (B, C)를 병합
if (runLength[stackSize - 3] < runLength[stackSize - 1]) {
merge(stackSize - 3);
}
else { // A, B 병합
merge(stackSize - 2);
}
}
// 2번 조건 B > A 에 위배 될 경우 (== B <= A 일 경우)
else if (runLength[stackSize - 2] <= runLength[stackSize - 1]) {
merge(stackSize - 2); // A, B 병합
}
// 그 외의 경우는 위 두 조건을 만족한다는 의미이므로 종료
else {
break;
}
}
}
}
하지만, 여기서 주의할 점이 있다. 위 코드의 경우 얼핏 보면 올바른 것 같아 보이지만, 사실 그렇지 않다. 한 가지 특수한 경우가 발생하기 때문이다.
예로들어보자.
stack[] = {120, 80, 25, 20} 이렇게 있다고 가정해보자.
그리고 새로운 run 30이 스택에 push 되었다고 해보자.
그러면 stack[] 의 상태는 {120, 80, 25, 20, 30} 이 될 것이고 stack은 위 두 가지 조건을 만족할 때 까지 병합 과정을 거칠 것이다.
첫 번째 병합에서 C(25) > B(20) + A(30) 를 만족하지 못하면서 C(25) < A(30) 이므로, run B(20) 와 run C(25) 가 병합 될 것이다.
그러면 stack[]의 상태는 {120, 80, 45, 30} 이 된다.
그 다음 다시 병합 조건을 검사할텐데, C(80) > B(45) + A(30) 도 만족하고, B(45) > A(30) 도 만족하게 되면서 while문은 종료 될 것이다.
어..? 그러면 문제 없는 거 아닌가요? 할 수도 있겠지만, 생각해보자.
우리가 stack[] 을 40으로 잡은 이유가 무엇인가? 피보나치 수와 비슷한 과정처럼 최악의 과정에서도 자바에서 생성할 수 있는 배열의 최대 크기를 모두 담을 수 있기 때문이다.
즉, 좀 더 확장해서 보자면 모든 stack의 원소는 다음을 만족해야 하는 것이다.
stack[] = { ... , 139, 87 ,52 ,34, 17 ,16 } 이렇게 있다고 할 때가 가장 최악의 경우의 수인데, 해당 이 말은 즉, 임의의 k번째 원소의 관점에서 stack[k - 3] > stack[k - 2] + stack[k - 1] 을 만족하며, stack[k - 2] > stack[k - 1] 을 만족한다는 의미다.
하지만 우리가 얻은 {120, 80, 45, 30} 을 보자.
(80, 45, 30) 의 경우에는 만족하지만, (120, 80, 45) 의 경우에는 만족하는가? 120 < 125 로 만족하지 못하면서 stack의 규칙이 깨져버리게 된다.
이러한 특수한 경우로 인해 실제로 Java에서도 이슈가 보고되어 9버전에서 수정되었다.
(해당 관련 이슈 관련 내용은 아래 더보기를 눌러 참고하시면 될 것 같다.)
그러면 어떻게 고쳐야 할까?
아주 간단하다. 우리가 runLength[i - 3] > runLength[i - 2] + runLength[i - 1] 에 대해서만 검사했었지만, 위 예시에서는 한 칸 더 내려가서도 검사해야한다는 것을 볼 수 있다.
즉, runLength[i - 4] > runLength[i - 3] + runLength[i - 2] 도 만족하는지를 추가하면 된다.
private static class IntMerge {
// ... 생성자 및 pushRun 등 생략 ... //
public void merge() {
/*
기본 적인 메커니즘
1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
2. runLen[i - 2] > runLen[i - 1]
while (stackSize > 1) {
// 1번 조건 C > B + A 에 위배 될 경우 (== C <= B + A 일 경우)
if (stackSize > 2 && runLength[stackSize - 3] <= runLength[stackSize - 2] + runLength[stackSize - 1] {
// C < A가 크다면 (B, C)를 병합
if (runLength[stackSize - 3] < runLength[stackSize - 1]) {
merge(stackSize - 3);
}
else { // A, B 병합
merge(stackSize - 2);
}
}
// 2번 조건 B > A 에 위배 될 경우 (== B <= A 일 경우)
else if (runLength[stackSize - 2] <= runLength[stackSize - 1]) {
merge(stackSize - 2); // A, B 병합
}
// 그 외의 경우는 위 두 조건을 만족한다는 의미이므로 종료
else {
break;
}
}
위 방식을 그대로 조건식으로 구현할 경우 stack 규칙이 깨짐
예로들어 120, 80, 25, 20이 스택에 있고, 30이 스택에 추가되었다고 가정.
즉, stack[] = {120, 80, 25, 20, 30}
첫 번째 반복문에서 첫 번째 merge() 시
첫 번째 조건문의 runLen[pivot − 1] <= runLen[pivot] + runLen[pivot + 1])
즉, 25 <= (20 + 30) 을 만족시키며, 해당 하위 조건문 runLen[pivot − 1] < runLen[pivot + 1] 인
25 < 30 도 만족시키기 때문에 25와 20이 병합된다.
그러면 결과는, {120, 80, 45, 30} 이 된다.
다음 반복문으로 넘어가게 되면 다음과 같이 된다.
80 > 45 + 30 이기 때문에 첫 번째 조건문을 만족하지 못하며,
그 다음 조건문인 runLen[pivot] <= runLen[pivot + 1] 또한 45 > 30이라
stack의 유지의 두 조건을 모두 만족한다는 의미로 반복문이 종료된다.
하지만, 전체 남아있는 스택을 볼 때, 120 <= 80 + 45 을 만족하는게 있음에도 merge되지 않기에
stack의 규칙이 깨지게 된다.
즉, 상위 3개만 아니라 그 다음 아래의 3개의 요소에 대해서도 검사를 해야한다.
*/
while (stackSize > 1) {
/*
* 1번 조건 C > B + A 에 위배 될 경우 (== C <= B + A 일 경우)
* 혹은, D > C + B 에 위배 될 경우 (== D <= C + B 일 경우)
*/
if (stackSize > 2 && runLength[stackSize - 3] <= runLength[stackSize - 2] + runLength[stackSize - 1]
|| stackSize > 3 && runLength[stackSize - 4] <= runLength[stackSize - 3] + runLength[stackSize - 2]) {
if (runLength[stackSize - 3] < runLength[stackSize - 1]) {
merge(stackSize - 3);
}
else {
merge(stackSize - 2);
}
}
// 2번 조건 B > A 에 위배 될 경우 (== B <= A 일 경우)
else if (runLength[stackSize - 2] <= runLength[stackSize - 1]) {
merge(stackSize - 2);
}
// 그 외의 경우는 위 두 조건을 만족한다는 의미이므로 종료
else {
break;
}
}
}
}
위와 같이 되면 기본적으로 run은 0개부터 하나씩 쌓이기 때문에 stack원소가 5개 이상일 때, 혹은 그 이상에서 조건을 검사해줄 필요가 없다.
(병합 되는 경우는 상위 3개중 하나고, stack에서 규칙을 따르지 않는 예외의 수는 상위 4개의 원소에 대해서만 발생한다는 것이다.)
그리고 하나. merge() 이외에 mergeForce() 메소드가 있다.
이는 우리가 stack에 유지시키면서 run을 쌓고, 병합한 뒤 모든 run 생성이 끝나는 시점이 있을 것이다. 이 때는 최종적으로 run을 모두 합쳐 병합정렬을 해주어야 하기 때문에 stack을 유지시킬 필요가 없다.
즉, 위 1번과 2번 조건식 자체는 필요로 하지는 않는다. 다만, 병합 효율성을 위해(최대한 비슷한 것 끼리 병합할 수 있도록 하기 위해) 2번 조건만 검사하면서 병합 위치를 넘겨주도록 한다.
코드를 보면 바로 이해는 갈 것이다.
private static class IntMerge {
// ... 생성자 및 pushRun 등 생략 ... //
public void mergeForce() {
// 나머지 모든 run을 병합한다.
while (stackSize > 1) {
// 모든 run을 병합 할 것이기 때문에 2번 조건인 runLen[i - 2] > runLen[i - 1] 만 체크해주면서 병합한다.
if (stackSize > 2 && runLength[stackSize - 3] < runLength[stackSize - 1]) {
merge(stackSize - 3);
}
else {
merge(stackSize - 2);
}
}
}
}
즉, merge() 메소드는 'stack의 조건을 유지하기 위한 최소한의 병합 과정' 이 중점이라면, mergeForce() 는 최종적으로 이루어지는 '모든 run의 병합 과정'이라는 점이 차이 점이다.
그러면 이제 실질적으로 인수로 전달 받는 merge(int idx) 을 구현해보도록 하자.
일단, idx로 넘어오게 된다면, idx에 기록 된 run에 대한 정보와 idx + 1에 기록된 run에 대한 정보를 토대로 병합을 진행하게 된다.
즉, runBase[idx], runLength[idx]를 통해 하나의 run에 대한 정보와, runBase[idx + 1], runLength[idx + 1] 을 통해 또 다른 run에 대한 정보를 갖고오게 되는 것이다.
여기서 Tim Sort는 한 번 더 최적화를 하게 된다.
한 번 무엇을 최적화 하는지 보도록하자.
우리가 병합하기 전에 생각해봐야할 것이 있다. 앞서 run을 스택에 쌓기 위한 이유가 무엇이었는가? run을 각각의 배열 형태로 두게 되면 결국 전체 배열이 차지하는 메모리만큼 모든 run에 대한 메모리 또한 그만큼 생성되기 때문이다.
그래서 run에 대한 시작점을 runBase라는 배열에, run에 대한 길이를 runLength에 두 가지 조건식을 만족하면서 쌓이는 stack 구조로 두었다.
그래서 총 필요한 배열 공간은 40(runBase) + 40(runLength) = 80으로 매우 많이 줄어들었다.
여기까진 병합하기 전 블럭에 대한 메모리 관리였다면 실제 병합하는 과정에서는 어떻게 해야할까?
만약 필자의 병합 정렬 포스팅을 보고오셨다면 알겠지만, 병합 정렬에서 두 개의 리스트를 병합하는 과정은 다음과 같았다.
위 정렬 되는 리스트에 대해 추가적인 메모리가 사용된다.
여기서 하나 생각해볼 수 있다.
"저 방식이 아니라 좀 더 메모리를 더욱 적게 쓰는 방법은 없을까?"
우리가 그동안 거쳐온 과정을 보자.
1. Binary Insertion Sort를 거친 run이 생성된다.
2. run을 stack에 push한다.
3. stack이 조건식에 맞으면서 최대한 비슷한 run끼리 병합하도록 한다.
(여기서 우리는 3번의 '병합'과정을 구현하고자 하고 있다.)
run의 특징은 무엇인지를 한 번 생각해보자. 바로 각각의 run은 정렬 되어 있는 상태라는 것이다. 두 개의 run을 병합하고자 할 때, 이미 정렬되어 더이상 움직일 필요가 없는 요소가 있지 않을까?
어쩌면 이진 삽입 정렬 전에 'getAscending()' 메소드를 통해 이미 오름차순(혹은 내림차순)으로 정렬 된 부분을 탐색해서 그 다음부터 이진 삽입 정렬을 수행하도록 하는 것과 유사한 메커니즘이기도 하다. 글로만 읽으면 이해하기 어려울테니 한 번 아래 이미지를 보도록 하자.
위 이미지에서도 볼 수 있듯, 각 run은 정렬되어 있는 상태고, 양쪽에서 두 개가 병합 될 때 정렬 할 필요가 없는 요소들을 제외하게 된다면 병합해야 하는 부분이 감소하게 될 기대를 할 수 있다.
어떻게 정렬할 필요가 없는 상태인지를 알아내는 것은 그리 어렵지 않다.
merge(int idx)에서 idx로 넘어온 idx번째 스택(runBase[idx], runLength[idx])의 run인 왼쪽 run을 A라고 하고, idx + 1 번째 스택의 run인 오른쪽 run을 B라고 할 때, 다음과 같이 표현 할 수 있다.
이 때 run A에서 '병합에 필요 없는 부분'이라 함은 어디까지일까? 앞서 봤던 이미지를 한 번 자세히 봐보자.
바로 runA에서 b0 보다 작은 원소들에 대한 부분이다.
반대로 run B에서 '병합에 필요 없는 부분'이라 함은 어디까지일까?
바로 run B에서 ai-1 보다 크거나 같은 원소들에 대한 부분이다. (안장정렬을 하기 위해서는 같은 원소들까지 포함해야한다.)
그럼 각 run에서 제외되는 부분을 다음과 같이 정의 할 수 있다.
좀 더 이미지로 쉽게 보면 이렇다.
그러면 결국 저 제외되는 지점을 찾는 것이 중요할 것 같다.
여기서 우리는 Tim Sort의 최적화 기법 중 가장 대표적인 Galloping Mode(질주 모드)에 대해 이해를 할 필요가 있다.
위 예제에서는 매우 작은 배열을 예시로 들고 있지만, 실제로는 단일 run이 훨씬 더 클 가능성이 더 높다. 그러면 저 지점을 찾기 위해 하나하나 검색하면서 찾아보아야 할까?
이러한 부분에서 착안한 것이 바로 질주 모드다. 쉽게 말해서 두 배씩 건너 뛰면서 찾는 것이다.
위 그림에서 보면 run B의 첫 번째 원소보다 작은 부분(= run A에서 제외되는 부분)을 찾는 것과, run A의 마지막 원소보다 큰 부분(= run B에서 제외되는 부분)을 찾는 것 이렇게 두 가지가 있다.
즉, 두 가지 지점을 찾아야 하는데, 간단하게 run A에서 제외되어야 할 지점을 찾는 과정을 먼저 간단하게 이미지로 보도록 하자.
위 이미지에서 볼 수 있듯, 두 배씩 건너 뛰면서 key값인 37보다 큰 원소를 찾을 때 까지 이를 반복한다.
그리고 37보다 큰 값이 나올 경우 이전의 탐색 지점과 현재 탐색 지점 사이에 대해 이분탐색(binary search)를 진행하여 Upper Bound 로 37를 초과한 첫 인덱스, 즉 37 이하의 값들을 갖는 리스트의 길이를 반환해준다.
이를 코드로 작성하면 다음과 같다.
private static class IntMerge {
// ... 생성자 및 pushRun IntMerge 메소드들 생략 ... //
/**
* gallop_right() 함수를 수행하여 RUN B 의 첫번째 원소보다
* 큰 원소들이 첫번째 출현하는 위치를 RUN A 에서 찾는다.
*
* @param key run B의 startPoint key
* @param array 배열
* @param base run A의 startPoint
* @param lenOfA run A 의 길이
* @return 제외되어야 할 부분의 위치 다음 인덱스를 반환
*/
private int gallopRight(int key, int[] array, int base, int lenOfA) {
int lo = 0; // 이전 탐색(gallop) 지점
int hi = 1; // 현재 탐색(gallop) 지점
/*
* RUN B의 시작지점 값(key)이 RUN A의 시작지점 값보다 작을 경우
* 제외 될 원소는 없으므로 0 리턴
*/
if(key < array[base]) {
return 0;
}
else {
/*
gallopRight ->
RUN A key RUN B
______________________________ ______________________________
[ | | || | | |MAX] [MIN| | | | || | ]
------------------------------ ------------------------------
|___________| |______________| |___________________| |______|
less than MIN RUN A' RUN B' greater than MAX
|____________________________________|
merge RUN A' and RUN B'
*/
int maxLen = lenOfA; // galloping을 하여 가질 수 있는 최대 한계값
while (hi < maxLen && array[base + hi] <= key) {
lo = hi;
hi = (hi << 1) + 1;
if (hi <= 0) { // overflow 발생시 run A의 끝 점으로 초기화
hi = maxLen;
}
}
if (hi > maxLen) {
hi = maxLen;
}
}
lo++;
// binary search (Upper Bound)
while(lo < hi) {
int mid = lo + ((hi - lo) >>> 1);
if(key < array[base + mid]) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return hi;
}
}
반대로 오른쪽 끝 부터 제외 해야할 지점을 찾아내기 위해 위와는 정 반대의 탐색 알고리즘 또한 작성 되어야 할 것이다.
private static class IntMerge {
// ... 생성자 및 pushRun IntMerge 메소드들 생략 ... //
/**
* gallop_left() 함수를 수행하여 RUN A 의 첫번째 원소(오른쪽 끝)보다
* 큰 원소들이 첫번째로 출현하는 위치를 RUN B 에서 찾는다.
*
* @param key run A의 key
* @param array 배열
* @param base run B의 시작 지점
* @param lenOfB run B 의 길이
* @return 제외되어야 할 부분의 위치 다음 인덱스를 반환
*/
private int gallopLeft(int key, int[] array, int base, int lenOfB) {
int lo = 0;
int hi = 1;
/*
* key가 B의 탐색의 첫 위치(오른쪽 끝)보다 크면 제외되어야 할 부분은 없으므로
* run B의 길이를 반환
*/
if (key > array[base + lenOfB - 1]) {
return lenOfB;
}
else {
/*
<- gallopLeft
RUN A RUN B
______________________________ ______________________________
[ | | || | | |MAX] [MIN| | | | || | ]
-------------------------------------------------------------
|___________| |______________| |___________________| |______|
less than MIN RUN A' RUN B' greater than MAX
|____________________________________|
merge RUN A' and RUN B'
*/
// run B의 오른쪽부터 시작해야하므로 뒤쪽 시작점을 가리키는 변수
int startPointOfRun = base + lenOfB - 1;
int maxLen = lenOfB; // galloping을 하여 가질 수 있는 최대 한계값
while (hi < maxLen && key <= array[startPointOfRun - hi]) {
lo = hi;
hi = (hi << 1) + 1;
// overflow가 발생시 runB의 끝점(왼쪽 끝)으로 초기화
if (hi <= 0) {
hi = maxLen;
}
}
if (hi > maxLen) {
hi = maxLen;
}
/*
* 뒤에서부터 탐색했기 때문에 실제 가리키는 인덱스는 lo > hi 이므로
* 이분 탐색을 하기 위해 run B에 대해 가리키는 지점을 서로 바꿔준다.
*/
int temp = lo;
lo = lenOfB - 1 - hi;
hi = lenOfB - 1 - temp;
}
lo++;
// binary search (lower bound)
while (lo < hi) {
int mid = lo + ((hi - lo) >>> 1);
if (key <= array[base + mid]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return hi;
}
}
이렇게 각 방향에서 탐색 할 수 있는 두 개의 galloping 메소드가 완성 되었다.
이제 다시 돌아와서 merge 부분을 보자. 우리가 앞서 구현 한 galloping 메소드를 통해 양 run에서 제외되고 시작해야 할 부분(인덱스)를 얻을 수 있을 것이다.
예로들어 위 그림에서 본다면, gallopRight() 메소드를 통해 얻는 값은 22를 가리키는 위치(index) 7를 얻을 것이고 gallopLeft() 메소드를 통해 얻는 값은 28를 가리키는 4가 될 것이다.
(참고로 4가 되는 이유는 앞서 gallopLeft 메소드에서 보면 마지막에 lower bound를 했다. 이는 key값보다 '크거나 같은' 인덱스를 가리키기 때문에 run B에 대해서 가리키는 지점은 26보다 크거나 같은 28을 가리키는 지점인 index 4가 되는 것이다.)
그러면 다시 돌아가서 merge(int idx)로 넘어가보자.
idx의 경우에는 stack에 있는 run의 정보를 기준으로 stack[idx] 와 stack[idx + 1]을 병합한다고 했다. 그 과정안에서 병합하는 과정에 메모리를 최소화 하기 위해 galloping이라는 기법을 사용한다고 했고, 이는 바로 위에서 다루었다.
그럼 과정을 훑어보면 이렇다.
run A의 시작점은 runBase[idx]이고, run A의 길이는 runLength[idx] 이며, run B의 시작점은 runBase[idx + 1] 이고, 길이는 runLength[idx + 1] 이라는 것이다.
이렇게 보면 이해가 어려울 수 있으니, 바로 위 이미지를 예시로 들어보자.
run A는 전체 배열(array)에서 0 부터 시작한다고 가정한다면, 이렇다.
run A의 시작점은 0이고, 길이는 9다.
run B의 시작점은 9이고, 길이는 9다.
그리고 우리는 병합량을 줄이기 위해 양쪽에서 제외시키고자 galloping 을 통해 인덱스를 얻는다.
그러면 먼저 run A에서 제외되어야 할 부분을 얻기 위해 gallopRight() 메소드를 사용하게 되면 7을 얻게 되며, run A 에서 병합 해야 할 시작점은 (0 + 7) 인 7이 될 것이고, 길이는 (9 - 7)인 2가 될 것이다.
마찬가지로 run B에서 제외되어야 할 부분을 얻기 위해 gallopLeft() 메소드를 사용하게 되면, 4를 얻게 된다. 이 때 run B는 상대적으로 오른쪽 부분이 제외되는 것이기 때문에 시작점은 그대로인 9가 될 것이고, 길이는 (9 - 4)가 제외되는 개수이고 병합해야 하는 끝점은 run의 길이에서 제외되는 부분을 빼우저야 하므로 9 - (9 - 4) = 4, 즉 gallopLeft()를 통해 얻는 값 자체가 run B의 병합해야 할 길이가 된다.
이를 토대로 코드를 작성해보자면 다음과 같다.
private static class IntMerge {
// ... 생성자 및 pushRun IntMerge 메소드들 생략 ... //
/**
* run[idx] 와 run[idx + 1]이 병합 됨
*
* @param idx 병합되는 두 서브리스트(run) 중 낮은 인덱스
*/
private void merge(int idx) {
int start1 = runBase[idx];
int length1 = runLength[idx];
int start2 = runBase[idx + 1];
int length2 = runLength[idx + 1];
// idx 와 idx + 1 번째 run을 병합
runLength[idx] = length1 + length2;
/*
* 상위 3개 (A, B, C)에서 A, B가 병합 할 경우 C를 당겨온다.
*
* ex)
* stack [[A], [B], [C]]
*
* runLen[idx] = length1 + length2
* stack[[A + B], [B], [C]]
*
* C를 B위치로 당겨온다.
* stack[[A + B], [C], [C]]
*
* 이 때 마지막 [C](stack[i - 1])는 어차피 더이상 참조될 일 없음
*/
if (idx == (stackSize - 3)) {
runBase[idx + 1] = runBase[idx + 2];
runLength[idx + 1] = runLength[idx + 2];
}
stackSize--;
/*
gallopRight -> <- gallopLeft
RUN A RUN B
______________________________ ______________________________
[ | | || | | |MAX] [MIN| | | | || | ]
------------------------------ -----------------------------
|___________| |______________| |___________________| |______|
less than MIN RUN A' RUN B' greater than MAX
|____________________________________|
merge RUN A' and RUN B'
*/
// start point (RUN B의 시작점보다 작으면서 RUN A 에서 merge를 시작할 위치)
int lo = gallopRight(array[start2], array, start1, length1);
/*
* 만약 RUN A의 길이와 merge를 시작할 지점이 같을 경우
* 이미 정렬되어있는 상태로 정렳 할 필요 없음
*/
if (length1 == lo) {
return;
}
start1 += lo;
length1 -= lo;
// end point (RUN A의 끝 점보다 크면서 RUN B에서 merge가 끝나는 위치)
int hi = gallopLeft(array[start1 + length1 - 1], array, start2, length2);
if (hi == 0) {
return;
}
length2 = hi;
if (length1 <= length2) {
mergeLo(start1, length1, start2, length2);
}
else {
mergeHi(start1, length1, start2, length2);
}
}
}
여기 부분 자체는 그리 어려운 부분은 아닐 것이다.
다만 주의해야 할 점이 있다면, 앞서 우리가 merge() 과정에서 조건문을 뒀었다.
상위 스택 3개에 대해서 병합되는 경우의 수는 두 가지로 runLength[stackSize - 2] 와 runLength[stackSize - 1] 이 병합되는 경우와 runLength[stackSize - 3] 과 runLength[stackSize - 2]가 병합되는 경우였다.
이 때 runLength[stackSize - 3] 과 runLength[stackSize - 2] 이 병합 될 경우 runLength[stackSize - 3]으로 병합되게 되는데, 그러면 runLength[stackSize - 1] 과 runLength[stackSize - 3] 사이에 공백이 생기게 된다.
그렇기 때문에 반드시 runLength[stackSize - 1] 을 runLength[stackSize - 2] 로 땡겨와주어야 한다는 점만 유의하도록 하자.
이제 마지막으로 실제 원소를 병합하는 과정만 남았다.
여기서도 TimSort는 한 번 더 최적화를 하는데, run A와 run B 각각의 병합해야 할 길이를 비교해서 작은 쪽을 기준으로 mergeLo와 mergeHi로 나뉜다.
왜 이렇게 나뉘는지는 아래 merge 과정을 보면 된다.
위 처럼 temp 배열에 임시 복사를 하는 과정이 필요한데, 여기서도 한 번 더 최적화하여 병합해야 하는 두 run중 짧은 것을 temp 배열에 복사하여 메모리를 최소화 하는 것이다.
위의 예시의 경우 run A가 더 짧으므로 run A을 임시 배열인 temp 배열에 복사하여 임시 배열과 run B를 순회하면서 배치를 하는 과정이다.
이는 mergeLo() 메소드의 예시가 된다.
반대로 run B의 길이가 더 짧다면 mergeLo 방식과 정 반대로 다음과 같이 진행하면 된다.
이렇게 두 가지의 병합 방식을 볼 수 있다.
위 예시는 이해를 돕기 위해 총 8개의 원소를 갖는 배열을 예로 들었지만, 실제로는 훨씬 긴 배열에서 병합이 이루어 질 것이다. 이 때 각 run의 길이 중 짧은 것을 임시 배열에 복사해둠으로 인해 메모리를 절약할 수 있는 것이다.
그러면 mergeLo와 mergeHi를 구현해보면 다음과 같이 작성 할 수 있다.
private static class IntMerge {
// ... 생성자 및 pushRun IntMerge 메소드들 생략 ... //
/**
* 상대적으로 낮은 인덱스에 위치한 run을 기준으로 복사하여
* 실제 배열 원소를 병합하는 메소드
*
* @param start1 RUN A에서의 병합 시작 지점
* @param length1 RUN A에서의 병합해야 할 길이(개수)
* @param start2 RUN B에서의 병합 시작 지점
* @param length2 RUN B에서의 병합해야 할 길이(개수)
*/
private void mergeLo(int start1, int length1, int start2, int length2) {
// RUN A 를 담을 임시 복사 배열
int[] temp = new int[length1];
System.arraycopy(array, start1, temp, 0, length1); // RUN A를 temp 배열에 복사
int insertIdx = start1; // 재배치 되는 위치
int runBIdx = start2; // RUN B의 탐색 위치
int tempIdx = 0; // 복사한 RUN A의 탐색 위치
int leftRemain = length1; // 배치해야 할 RUN A의 원소 개수
int rightRemain = length2; // 배치해야 할 RUN B의 원소 개수
// 두 원소 중 먼저 소진 될 때 까지 반복
while (leftRemain != 0 && rightRemain != 0) {
// RUN B < RUN A 라면 RUN B 원소 삽입
if (array[runBIdx] < temp[tempIdx]) {
array[insertIdx++] = array[runBIdx++];
rightRemain--;
} else {
array[insertIdx++] = temp[tempIdx++];
leftRemain--;
}
}
// 왼쪽 부분 리스트가 남아있을 경우
if (leftRemain != 0) {
System.arraycopy(temp, tempIdx, array, insertIdx, leftRemain);
}
else { // 오른 쪽 부분 리스트가 남아있을 경우
System.arraycopy(array, runBIdx, array, insertIdx, rightRemain);
}
}
/**
* 상대적으로 높은 인덱스에 위치한 run을 기준으로 복사하여
* 실제 배열 원소를 병합하는 메소드
*
* @param start1 RUN A에서의 병합 시작 지점
* @param length1 RUN A에서의 병합해야 할 길이(개수)
* @param start2 RUN B에서의 병합 시작 지점
* @param length2 RUN B에서의 병합해야 할 길이(개수)
*/
private void mergeHi(int start1, int length1, int start2, int length2) {
// RUN B 를 담을 임시 복사 배열
int[] temp = new int[length2];
System.arraycopy(array, start2, temp, 0, length2);
int insertIdx = start2 + length2 - 1; // 재배치되는 위치
int runAIdx = start1 + length1 - 1; // run A의 탐색 위치
int tempIdx = length2 - 1; // 복사한 run B의 탐색 위치
int leftRemain = length1; // 배치해야 할 RUN A의 원소 개수
int rightRemain = length2; // 배치해야 할 RUN B의 원소 개수
while (leftRemain != 0 && rightRemain != 0) {
// RUN A' > RUN B' 라면 RUN A' 원소 삽입 (내림차순이기 때문)
if (array[runAIdx] > temp[tempIdx]) {
array[insertIdx--] = array[runAIdx--];
leftRemain--;
} else {
array[insertIdx--] = temp[tempIdx--];
rightRemain--;
}
}
// 오른쪽 부분 리스트가 남아있을 경우
if (rightRemain != 0) {
System.arraycopy(temp, 0, array, start1, rightRemain);
} else {
System.arraycopy(array, start1, array, start1, leftRemain);
}
}
}
드디어 길고 길었던 TimSort의 모든 코드 구현 과정이 끝났다.
아마 이쯤이면 도대체 무엇을 구현한 것이지? 라고 생각이 들 수도 있을 것 같다. 그도 그럴 것이.. 워낙 Tim Sort 자체가 구현 과정 자체가 매우 세분화되어있으면서 복잡하기 때문에...
특히나 Binary Insertion Sort, Merge Sort에 대한 기본적인 이해와 Stack 자료구조 원리를 바탕으로 여러 최적화 기법이 들어가기 때문에 구현 난이도 자체가 높은 정렬 방식이라 아마 이에 대한 정확한 이해가 없다면 이 글을 이해하는데 어려움을 겪을 수 있다고 본다. (혹은 필자의 설명 능력의 부족일 수도 있다고 본다..)
최대한 이해를 위해 필자가 자바에서 구현하고 있는 Tim Sort에서 너무 디테일한 심화 내용은 최대한 걷어내면서 Tim Sort의 본질은 유지하도록 노력했다.
이렇다보니 아마 실제 Tim Sort와는 부분적으로 차이가 있을 것이니, 만약 여기서 한 단계 더 나아가고 싶다면, 어디서 좀 더 시간을 줄일지 고민해보셔도 좋을 것 같다.
일단은 최대한 이해를 돕기 위한 목적이 크기 때문에 그동안 정리했던 내용들을 압축해서 그 과정을 그려보도록 하겠다.
위와 같은 과정을 거쳐 정렬이 되는 것이다. 아마 이 그림이 좀 더 이해하기 편하지 않을까 싶긴 하다.
그러면 그동안 작성했던 코드들을 하나로 모아 보면 다음과 같이 된다.
[Tim Sort 전체 코드]
public class TimSort {
private static final int THRESHOLD = 32;
/**
* 최소 길이의 run 크기, 즉 minRun을 구하기 위한 메소드
*
* @param runSize minRun을 구하고자 하는 초기 배열의 길이
*/
public static int minRunLength(int runSize) {
int r = 0; // 홀 수가 발생할 때 2^x가 초과되지 않도록 하는 여분의 수
/*
* (runSize & 1) 을 하면, runSize의 가장 오른쪽 비트가 1일 경우에는
* 홀수이므로 1이 반환 될 것이고, r = r | (runSize & 1) 에서 r은 1로 될 것이다.
* 한 번 r이 1로 되면 OR 연산자의 특성상 이 값은 바뀌지 않는다.
*/
while(runSize >= THRESHOLD) {
r |= (runSize & 1);
runSize >>= 1;
}
return runSize + r;
}
// run을 스택에 담아 둘 내부 정적 클래스
private static class IntMergeStack {
private int[] array;
private int[] runBase;
private int[] runLength;
private int stackSize = 0; // run 스택의 원소 개수를 가리킬 변수
public IntMergeStack(int[] a) {
this.array = a;
int len = a.length;
runBase = new int[40];
runLength = new int[40];
}
public void pushRun(int runBase, int runLen) {
this.runBase[stackSize] = runBase;
this.runLength[stackSize] = runLen;
stackSize++;
}
public void mergeForce() {
// 나머지 모든 run을 병합한다.
while (stackSize > 1) {
// 모든 run을 병합 할 것이기 때문에 2번 조건인 runLen[i - 2] > runLen[i - 1] 만 체크해주면서 병합한다.
if (stackSize > 2 && runLength[stackSize - 3] < runLength[stackSize - 1]) {
merge(stackSize - 3);
} else {
merge(stackSize - 2);
}
}
}
public void merge() {
/*
기본 적인 메커니즘
1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
2. runLen[i - 2] > runLen[i - 1]
스택에 요소가 5개 있을 때 기본 pivot은 상위 3개 요소 중 가운데를 지정
ex) A, B, C, D, E (A = Bottom, E = Top)
pivot = D (== stackSize - 2)
runLen[pivot - 1] = C, runLen[pivot] = D, runLen[pivot + 1] = E를 스택의 상위 세 요소로 한다.
메커니즘상 루프는 다음과 같은 경우에 기초한다.
1. C <= D + E 및 C < E일 경우 C 과 D 병합. 즉, pivot - 1 과 pivot 병합
2. C <= D + E 및 C >= E일 경우, D와 E 병합. 즉, pivot 과 pivot + 1 병합
3. C > D + E 및 D <= E일 경우, D와 E 병합. 즉, pivot 과 pivot + 1 병합
4. C > D + E 및 D > E일 경우 루프 종료
while (stackSize > 1) {
// 1번 조건 C > B + A 에 위배 될 경우 (== C <= B + A 일 경우)
if (stackSize > 2 && runLength[stackSize - 3] <= runLength[stackSize - 2] + runLength[stackSize - 1] {
// C < A가 크다면 (B, C)를 병합
if (runLength[stackSize - 3] < runLength[stackSize - 1]) {
merge(stackSize - 3);
}
else { // A, B 병합
merge(stackSize - 2);
}
}
// 2번 조건 B > A 에 위배 될 경우 (== B <= A 일 경우)
else if (runLength[stackSize - 2] <= runLength[stackSize - 1]) {
merge(stackSize - 2); // A, B 병합
}
// 그 외의 경우는 위 두 조건을 만족한다는 의미이므로 종료
else {
break;
}
}
위 방식을 그대로 조건식으로 구현할 경우 stack 규칙이 깨짐
예로들어 120, 80, 25, 20이 스택에 있고, 30이 스택에 추가되었다고 가정.
즉, stack[] = {120, 80, 25, 20, 30}
첫 번째 반복문에서 첫 번째 merge() 시
첫 번째 조건문의 runLen[pivot − 1] <= runLen[pivot] + runLen[pivot + 1])
즉, 25 <= (20 + 30) 을 만족시키며, 해당 하위 조건문 runLen[pivot − 1] < runLen[pivot + 1] 인
25 < 30 도 만족시키기 때문에 25와 20이 병합된다.
그러면 결과는, {120, 80, 45, 30} 이 된다.
다음 반복문으로 넘어가게 되면 다음과 같이 된다.
80 > 45 + 30 이기 때문에 첫 번째 조건문을 만족하지 못하며,
그 다음 조건문인 runLen[pivot] <= runLen[pivot + 1] 또한 45 > 30이라
stack의 유지의 두 조건을 모두 만족한다는 의미로 반복문이 종료된다.
하지만, 전체 남아있는 스택을 볼 때, 120 <= 80 + 45 을 만족하는게 있음에도 merge되지 않기에
stack의 규칙이 깨지게 된다.
즉, 상위 3개만 아니라 그 다음 아래의 3개의 요소에 대해서도 검사를 해야한다.
*/
while (stackSize > 1) {
/*
* 1번 조건 C > B + A 에 위배 될 경우 (== C <= B + A 일 경우)
* 혹은, D > C + B 에 위배 될 경우 (== D <= C + B 일 경우)
*/
if (stackSize > 2 && runLength[stackSize - 3] <= runLength[stackSize - 2] + runLength[stackSize - 1]
|| stackSize > 3 && runLength[stackSize - 4] <= runLength[stackSize - 3] + runLength[stackSize - 2]) {
if (runLength[stackSize - 3] < runLength[stackSize - 1]) {
merge(stackSize - 3);
}
else {
merge(stackSize - 2);
}
}
// 2번 조건 B > A 에 위배 될 경우 (== B <= A 일 경우)
else if (runLength[stackSize - 2] <= runLength[stackSize - 1]) {
merge(stackSize - 2);
}
// 그 외의 경우는 위 두 조건을 만족한다는 의미이므로 종료
else {
break;
}
}
}
/**
* run[idx] 와 run[idx + 1]이 병합 됨
*
* @param idx 병합되는 두 서브리스트(run) 중 낮은 인덱스
*/
private void merge(int idx) {
int start1 = runBase[idx];
int length1 = runLength[idx];
int start2 = runBase[idx + 1];
int length2 = runLength[idx + 1];
// idx 와 idx + 1 번째 run을 병합
runLength[idx] = length1 + length2;
/*
* 상위 3개 (A, B, C)에서 A, B가 병합 할 경우 C를 당겨온다.
*
* ex)
* stack [[A], [B], [C]]
*
* runLen[idx] = length1 + length2
* stack[[A + B], [B], [C]]
*
* C를 B위치로 당겨온다.
* stack[[A + B], [C], [C]]
*
* 이 때 마지막 [C](stack[i - 1])는 어차피 더이상 참조될 일 없음
*/
if (idx == (stackSize - 3)) {
runBase[idx + 1] = runBase[idx + 2];
runLength[idx + 1] = runLength[idx + 2];
}
stackSize--;
/*
gallopRight -> <- gallopLeft
RUN A RUN B
______________________________ ______________________________
[ | | || | | |MAX] [MIN| | | | || | ]
------------------------------ ------------------------------
|___________| |______________| |___________________| |______|
less than MIN RUN A' RUN B' greater than MAX
|____________________________________|
merge RUN A' and RUN B'
*/
// start point (RUN B의 시작점보다 작으면서 RUN A 에서 merge를 시작할 위치)
int lo = gallopRight(array[start2], array, start1, length1);
/*
* 만약 RUN A의 길이와 merge를 시작할 지점이 같을 경우
* 이미 정렬되어있는 상태로 정렳 할 필요 없음
*/
if (length1 == lo) {
return;
}
start1 += lo;
length1 -= lo;
// end point (RUN A의 끝 점보다 크면서 RUN B에서 merge가 끝나는 위치)
int hi = gallopLeft(array[start1 + length1 - 1], array, start2, length2);
if (hi == 0) {
return;
}
length2 = hi;
if (length1 <= length2) {
mergeLo(start1, length1, start2, length2);
}
else {
mergeHi(start1, length1, start2, length2);
}
}
/**
* gallop_right() 함수를 수행하여 RUN B 의 첫번째 원소보다
* 큰 원소들이 첫번째 출현하는 위치를 RUN A 에서 찾는다.
*
*
* @param key run B의 key
* @param array 배열
* @param base run A의 시작지점
* @param lenOfA run A 의 길이
* @return 제외되어야 할 부분의 위치 다음 인덱스를 반환
*/
private int gallopRight(int key, int[] array, int base, int lenOfA) {
int lo = 0; // 이전 탐색(gallop) 지점
int hi = 1; // 현재 탐색(gallop) 지점
/*
* RUN B의 시작지점 값(key)이 RUN A의 시작지점 값보다 작을 경우
* 제외 될 원소는 없으므로 0 리턴
*/
if(key < array[base]) {
return 0;
}
else {
/*
gallopRight ->
RUN A key RUN B
______________________________ ______________________________
[ | | || | | |MAX] [MIN| | | | || | ]
------------------------------ ------------------------------
|___________| |______________| |___________________| |______|
less than MIN RUN A' RUN B' greater than MAX
|____________________________________|
merge RUN A' and RUN B'
*/
int maxLen = lenOfA; // galloping을 하여 가질 수 있는 최대 한계값
while (hi < maxLen && array[base + hi] <= key) {
lo = hi;
hi = (hi << 1) + 1;
if (hi <= 0) { // overflow 발생시 run A의 끝 점으로 초기화
hi = maxLen;
}
}
if (hi > maxLen) {
hi = maxLen;
}
}
lo++;
// binary search (Upper Bound)
while (lo < hi) {
int mid = lo + ((hi - lo) >>> 1);
if (key < array[base + mid]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return hi;
}
/**
* gallop_left() 함수를 수행하여 RUN A 의 첫번째 원소(오른쪽 끝)보다
* 큰 원소들이 첫번째로 출현하는 위치를 RUN B 에서 찾는다.
*
*
* @param key run A의 key
* @param array 배열
* @param base run B의 시작 지점
* @param lenOfB run B 의 길이
* @return 제외되어야 할 부분의 위치 다음 인덱스를 반환
*/
private int gallopLeft(int key, int[] array, int base, int lenOfB) {
int lo = 0;
int hi = 1;
/*
* key가 B의 탐색의 첫 위치(오른쪽 끝)보다 크면 제외되어야 할 부분은 없으므로
* run B의 길이를 반환
*/
if (key > array[base + lenOfB - 1]) {
return lenOfB;
}
else {
/**
<- gallopLeft
RUN A RUN B
______________________________ ______________________________
[ | | || | | |MAX] [MIN| | | | || | ]
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
|___________| |______________| |___________________| |______|
less than MIN RUN A' RUN B' greater than MAX
|____________________________________|
merge RUN A' and RUN B'
*/
// run B의 오른쪽부터 시작해야하므로 뒤쪽 시작점을 가리키는 변수
int startPointOfRun = base + lenOfB - 1;
int maxLen = lenOfB; // galloping을 하여 가질 수 있는 최대 한계값
while (hi < maxLen && key <= array[startPointOfRun - hi]) {
lo = hi;
hi = (hi << 1) + 1;
// overflow가 발생시 runB의 끝점(왼쪽 끝)으로 초기화
if (hi <= 0) {
hi = maxLen;
}
}
if (hi > maxLen) {
hi = maxLen;
}
/*
* 뒤에서부터 탐색했기 때문에 실제 가리키는 인덱스는 lo > hi 이므로
* 이분 탐색을 하기 위해 run B에 대해 가리키는 지점을 서로 바꿔준다.
*/
int temp = lo;
lo = lenOfB - 1 - hi;
hi = lenOfB - 1 - temp;
}
lo++;
// binary search (lower bound)
while (lo < hi) {
int mid = lo + ((hi - lo) >>> 1);
if (key <= array[base + mid]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return hi;
}
/**
* 상대적으로 낮은 인덱스에 위치한 run을 기준으로 복사하여
* 실제 배열 원소를 병합하는 메소드
*
* @param start1 RUN A에서의 병합 시작 지점
* @param length1 RUN A에서의 병합해야 할 길이(개수)
* @param start2 RUN B에서의 병합 시작 지점
* @param length2 RUN B에서의 병합해야 할 길이(개수)
*/
private void mergeLo(int start1, int length1, int start2, int length2) {
// RUN A 를 담을 임시 복사 배열
int[] temp = new int[length1];
System.arraycopy(array, start1, temp, 0, length1); // RUN A를 temp 배열에 복사
int insertIdx = start1; // 재배치 되는 위치
int runBIdx = start2; // RUN B의 탐색 위치
int tempIdx = 0; // 복사한 RUN A의 탐색 위치
int leftRemain = length1; // 배치해야 할 RUN A의 원소 개수
int rightRemain = length2; // 배치해야 할 RUN B의 원소 개수
// 두 원소 중 먼저 소진 될 때 까지 반복
while (leftRemain != 0 && rightRemain != 0) {
// RUN B < RUN A 라면 RUN B 원소 삽입
if (array[runBIdx] < temp[tempIdx]) {
array[insertIdx++] = array[runBIdx++];
rightRemain--;
} else {
array[insertIdx++] = temp[tempIdx++];
leftRemain--;
}
}
// 왼쪽 부분 리스트가 남아있을 경우
if (leftRemain != 0) {
System.arraycopy(temp, tempIdx, array, insertIdx, leftRemain);
}
else { // 오른 쪽 부분 리스트가 남아있을 경우
System.arraycopy(array, runBIdx, array, insertIdx, rightRemain);
}
}
/**
* 상대적으로 높은 인덱스에 위치한 run을 기준으로 복사하여
* 실제 배열 원소를 병합하는 메소드
*
* @param start1 RUN A에서의 병합 시작 지점
* @param length1 RUN A에서의 병합해야 할 길이(개수)
* @param start2 RUN B에서의 병합 시작 지점
* @param length2 RUN B에서의 병합해야 할 길이(개수)
*/
private void mergeHi(int start1, int length1, int start2, int length2) {
// RUN B 를 담을 임시 복사 배열
int[] temp = new int[length2];
System.arraycopy(array, start2, temp, 0, length2);
int insertIdx = start2 + length2 - 1; // 재배치되는 위치
int runAIdx = start1 + length1 - 1; // run A의 탐색 위치
int tempIdx = length2 - 1; // 복사한 run B의 탐색 위치
int leftRemain = length1; // 배치해야 할 RUN A의 원소 개수
int rightRemain = length2; // 배치해야 할 RUN B의 원소 개수
while (leftRemain != 0 && rightRemain != 0) {
// RUN A' > RUN B' 라면 RUN A' 원소 삽입 (내림차순이기 때문)
if (array[runAIdx] > temp[tempIdx]) {
array[insertIdx--] = array[runAIdx--];
leftRemain--;
} else {
array[insertIdx--] = temp[tempIdx--];
rightRemain--;
}
}
// 오른쪽 부분 리스트가 남아있을 경우
if (rightRemain != 0) {
System.arraycopy(temp, 0, array, start1, rightRemain);
} else {
System.arraycopy(array, start1, array, start1, leftRemain);
}
}
} // IntMergeStack class
public static void sort(int[] a) {
sort(a, 0, a.length);
}
public static void sort(int[] a, int lo, int hi) {
int remain = hi - lo;
// 정렬해야 할 원소가 1개 이하일 경우 정렬 할 필요가 없다.
if(remain < 2) {
return;
}
/**
* 일정 크기 이하의 배열이라면
* binaryInsertionSort로 정렬 뒤 바로 반환
*
* @see BinaryInsertionSort.BinaryInsertionSort
*/
if(remain < THRESHOLD) {
int increaseRange = getAscending(a, lo, hi);
BinarySort(a, lo, hi, lo + increaseRange);
return;
}
IntMergeStack ims = new IntMergeStack(a);
int minRun = minRunLength(remain); // run의 최소 길이
do {
/*
* 정렬 된 구간의 길이를 구한다.
*/
int runLen = getAscending(a, lo, hi);
/*
* 만약 정렬 된 부분의 길이가 minRun 보다 작다면
* 정렬 된 부분 길이를 포함한 부분 배열에 대해
* 이진 삽입 정렬을 시행한다.
*/
if(runLen < minRun) {
/*
* [lo : lo+minRun] 구간에 대해 정렬
*
* counts : run에 있는 요소의 총 개수
* 이 때 최소 run 크기가 남은 원소 개수보다 클 수 있으므로 이를 처리해준다.
*/
int counts = remain < minRun ? remain : minRun;
/*
* BinarySort(array, lo, hi, start);
* index[lo] ~ index[lo + counts] 구간을 삽입 정렬을 하되,
* index[lo + runLen] 부터 삽입정렬을 시작함.
* (앞서 구한 오름차순 길이인 runLen에 의해 lo + runLen의 이전 인덱스는 이미 오름차순 상태임)
*/
BinarySort(a, lo, lo + counts, lo + runLen);
// 이진 삽입 정렬이 수행되었기에 증가하는 길이는 endPoint가 된다.
runLen = counts;
}
// stack에 run의 시작점과 해당 run의 길이를 스택에 push한다.
ims.pushRun(lo, runLen);
ims.merge();
lo += runLen;
remain -= runLen;
} while(remain != 0); // 정렬 해야 할 원소가 0개가 될 때 까지 반복
ims.mergeForce(); // 마지막으로 스택에 있던 run들 모두 병합
}
// ============ 아래는 Binary Insertion Sort에서 구현했던 내용들임 ================ //
private static void BinarySort(int[] a, int lo, int hi ,int start) {
if(lo == start) {
start++;
}
for (; start < hi; start++) {
int target = a[start];
int loc = binarySearch(a, target, lo, start);
int j = start - 1;
while (j >= loc) {
a[j + 1] = a[j];
j--;
}
a[loc] = target;
}
}
private static int binarySearch(int[] a, int key, int lo, int hi) {
int mid;
while (lo < hi) {
mid = (lo + hi) >>> 1;
if (key < a[mid]) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return lo;
}
private static int getAscending(int[] a, int lo, int hi) {
int limit = lo + 1;
if (limit == hi) {
return 1;
}
if (a[lo] <= a[limit]) {
while (limit < hi && a[limit - 1] <= a[limit]) {
limit++;
}
}
else {
while (limit < hi && a[limit - 1] > a[limit]) {
limit++;
}
reversing(a, lo, limit);
}
return limit - lo;
}
private static void reversing(int[] a, int lo, int hi) {
hi--;
while (lo < hi) {
int temp = a[lo];
a[lo++] = a[hi];
a[hi--] = temp;
}
}
}
(코드가 매우 길긴 하다...)
- 팀 정렬의 장점 및 단점
[장점]
1. 최상의 시간복잡도는 O(N)이다.
2. 객체 참조 및 비교 비용이 비싼 경우 Quick Sort에 비해 빠르다는 이점이 있다.
3. 안정정렬이 가능하다.
[단점]
1. 오버헤드가 O(NlogN) 알고리즘에 비해 큰 편이기 때문에 간단한 정렬에서는 비효율적이다.
2. 고도로 최적화 된 정렬 알고리즘인 만큼 구현 과정이 복잡하며 제대로 된 검증이 이루어지지 않을 경우 Bug가 발생할 여지가 높다.
이에 대한 참고 영상으로는 아래 영상을 보면 위의 과정을 이해하는데 도움이 될 것 같다.
시간복잡도에 대해 먼저 분석해보자면 최상의 경우 O(N)의 시간 복잡도를 보인다. 왜 일까?
앞서 우리는 오름차순, 혹은 내림차순으로 되어있는 길이를 반환하는 getAscending()메소드를 활용했다. 만약 전체 배열이 이미 정렬되어있는 상태라면 당연히 getAscending() 을 통해 얻는 값 또한 그 배열의 길이가 될 것이고, 결국 run은 한 개만 생성되어 종료되게 된다.
반대로 최악의 경우에도 병합정렬 기반의 알고리즘이기 때문에 O(NlogN)의 시간복잡도를 갖게 된다.
- 정리
드디어 Tim Sort(팀 정렬)에 대한 정리가 끝났다.
아마 구현 난이도가 높아 이해하는데 어려웠을 것 같긴 하다. 실제로도 앞서 언급했던 것 처럼 Tim Sort 구현에 버그가 있어 발견된 사례가 있기도 했다.
이에 대해 테스트를 해볼 수 있는 소스파일들도 제공해주고 있는데 한 번 테스트 해보시는 것도 좋아보인다.
http://envisage-project.eu/timsort-specification-and-verification/
OpenJDK’s java.utils.Collection.sort() is broken: The good, the bad and the worst case | Envisage: Engineering Virtualized Ser
On this website we provide the material referenced in the paper “OpenJDK’s java.utils.Collection.sort() is broken: The good, the bad and the worst case” in particular the test generator, which breaks TimSort, as well as the source and proof of the
envisage-project.eu
자바에서는 Tim Sort가 객체 정렬일 때 쓰이기 때문에 위 테스트 소스 파일도 모두 객체 배열을 생성하여 쓰고 있기 때문에, TimSort 구현에 Comparable 혹은 Comparator 구현까지 확장해주거나, 혹은 테스트 파일에서 정렬하고자 하는 배열 타입을 바꿔서 테스트 해보아도 좋다.
만약 둘 다 귀찮으시다면 필자의 경우 깃허브에 올라가는 정렬알고리즘들은 모두 객체정렬까지 구현하고 있으니 해당 파일을 가지고 테스트해보셔도 된다.
이처럼 구현 난이도도 높은데 필자가 명필가가 아니라서 더욱 이해하기 어려울 수도 있다...
아래 글에서도 Tim Sort에 대한 이론적 내용을 잘 다뤄주고 있기 때문에 아래 글을 참고해보시는 것도 좋을 것 같아 링크를 남겨두도록 하겠다.
https://d2.naver.com/helloworld/0315536
필자가 Tim Sort를 자주 언급하는 이유가 알고있으면 도움되는 정렬 알고리즘이기 때문에 적어도 메커니즘 정도는 이해를 하고 넘어가면 좋을 것 같아서인 것도 있다.. 특히 안정정렬이면서도 충분한 최적화를 이룬 정렬알고리즘이기에 Java의 객체 정렬, python의 정렬 메소드, Swift의 정렬 메소드 등에서도 많이 차용되는 알고리즘이다.
여기서는 다루지 않고 넘어가지만, 참고로 자바 내부에선 필자처럼 병합 과정을 거치다가 일정 이상 탐색 횟수가 넘어가게 되면 병합과정 또한 내부에서 getAscending()을 써서 비교 횟수를 줄이기 위한 것도 구현되어 있다. 하지만, 해당 내용까지 구현하기에는 전반적인 정렬 과정을 넘어 오히려 이해하는데 방해가 될 것 같아 생략할 부분은 생략했다는 점도 알아두셨으면 한다.
이렇듯 완전한 구현까진 아니기에 여러분들이 한 번 직접 더 최적화를 시키는 것도 좋은 방법인 것 같다.
각 정렬 알고리즘 별 시간 복잡도와 평균 정렬 속도는 다음과 같다.
혹여 부족한 부분이 있거나 궁금한 점, 모르거나 이해가 가지 않는 부분이 있다면 언제든 댓글 달아주시면 감사하겠다.
그 외에 필자가 여러 타입들에 대해 구현 한 정렬 알고리즘 소스 코드들을 자세히 보고싶다면 아래 깃허브 repo에 업로드되어있으니 이를 참고하시길 바란다.
https://github.com/kdgyun/Sorting_Algorithm.git
kdgyun/Sorting_Algorithm
Contribute to kdgyun/Sorting_Algorithm development by creating an account on GitHub.
github.com
여담으로 근래 바쁘다보니 포스팅 속도가 매우 느려졌다...(죄송합니다.) 그렇다고 더 쉬운 알고리즘 문제 풀이만 계속 하게 되면 Tim Sort를 기약없이 미루게 될 것 같아 일단 시작하고 봤는데, Java의 내부 구현을 최대한 쉽게 풀어내는 과정부터가 매우 오래걸린 포스팅이었다.
매일 어떻게든 시간을 투자하려고 두어시간씩 보고 읽고 구현하고 했지만, 거의 이 글만 일주일 넘게 붙잡은 것 같다... 아무래도 내용이 길다보니 필자도 혹여 잘못 된 내용이 있을까 걱정되긴 한다.
혹여 어렵거나 잘못 된 내용이 있는 경우 언제든 댓글 남겨주시면 감사하겠다.
'알고리즘 > Java' 카테고리의 다른 글
| 자바 [JAVA] - 이진 삽입 정렬 (Binary Insertion Sort) (8) | 2021.08.01 |
|---|---|
| 자바 [JAVA] - 퀵 정렬 (Quick Sort) (29) | 2021.05.19 |
| 자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort) (24) | 2021.03.31 |
| 자바 [JAVA] - 힙 정렬 (Heap Sort) (31) | 2021.03.14 |
| 자바 [JAVA] - 셸 정렬 (Shell Sort) (18) | 2021.02.18 |