Dual-Pivot Quick Sort ( Arrays.sort() 내부 정렬 알고리즘 )

Arrays.sort()는 내부적으로 3개의 Sorting을 쓴다.

1. Insertion Sort

2. Merge Sort

3. QuickSort

예전에는 3개를 분리하여서 각각의 경우에 따로 사용을 했지만

지금은 1,2  1,3을 섞어서 사용한다.

Insertion Sort와 Merge Sort를 섞은 것은 Tim Sort

Insertion Sort와 QuickSort를 섞은 것은 Dual-Pivot Quick Sort라고 한다.

여기서는 Insertion Sort를 합치지않은, 오로지 Dual-Pivot Quick Sort를 다룬다.

기존의 Quick Sort는 Pivot이 한개 였지만 Dual-Pivot Quick Sort는 Pivot을 2개를 써서

Pivot 1보다 낮은 그룹 / Pivot1 ~ Pivot2 사이의 그룹(Pivot1, Pivot2는 제외) / Pivot2 보다 큰 그룹

이렇게 3가지 그룹을 왼쪽, 중간, 오른쪽의 부분 리스트로 나눈다.

이때 주의할 점은 pivot1 < pivot2가 성립되어야 한다.

소팅에 사용되는 변수는 l, k, g가 있다. 각 변수의 역할은 다음과 같다.

이 3가지 변수에 대한 역할을 아주 잘 이해해야하고 Dual Pivot Quick Sort의 핵심인 부분이 된다.

l : 소팅이 진행 중일 때는 pivot1보다 작은 값이 들어갈 다음 위치를 지정한다.

정확히 말하자면, l변수의 역할은 left+1부터 시작하고,

(이미 k에 의해 pivot1보다 작은 값이라 판정되어 왼쪽으로 온 값들 중 가장 나중에 온 값의 인덱스 +1)의 위치를 가리킨다.

이 l의 위치는, k에 의해 pivot1보다 작은 값이 탐지될 경우 arr[k]와 arr[l]을 교환한다.

이후에 +1이 되어, 아직 검증되지 않은 요소들 중 pivot1보다 작은 값이 들어갈, 다음 위치를 지정하게 된다.

자신의 자리가 아닌 k인덱스의 값(pivot1보다 작으므로 pivot1의 최종위치 보다 왼쪽에 가야 한다)을 제대로 배치시키기 위한 인덱스인 것이다.

만약, k인덱스의 값이 pivot1보다 크다면 이 요소는 중간 서브 리스트의 요소로서 제대로된 자리를 차지하고 있는 것이므로 교환하지 않고 k값만 증가하여 다음 요소를 확인하는 과정으로 넘어간다.

마지막에 소팅이 끝나면 -1을 하여 pivot1의 최종적인 위치를 가리킨다.

그리고 (l-1) 인덱스는 왼쪽 서브 리스트의 right값이 되며 (l+1)인덱스는 중간 서브 리스트의 left값이 된다.

g : 소팅이 진행 중일때는 pivot2보다 큰 값이 들어갈 다음 위치를 지정한다.

정확히 말하자면, g변수의 역할은 right-1부터 시작하고,

(이미 k에 의해 pivot2보다 큰 값이라 판정되어 오른쪽으로 온 값을 중 가장 나중에 온 값의 인덱스 -1)의 위치를 가리킨다.

이 g의 위치는, k에 의해 pivot2보다 큰 값이 탐지될 경우 arr[k]와 arr[g]를 교환한다.

이후에 -1이 되어, 아직 검증되지 않은 요소들 중 pivot2보다 큰 값이 들어갈, 다음 위치를 지정하게 된다.

자신의 자리가 아닌 k인덱스의 값(pivot2보다 크므로 pivot2의 최종 위치보다 오른쪽에 가야 한다)을 제대로 배치시키기 위한 인덱스인 것이다.

만약, k인덱스의 값이 pivot2보다 작다면 이 요소는 중간 서브 리스트의 요소로서 제대로 된 자리를 차지하고 있는 것이므로 교환하지 않고 k값만 증가하여 다음 요소를 확인하는 과정으로 넘어간다.

소팅이 끝나면 +1을 하여 pivot2의 최종적인 위치를 가리킨다.

그리고 (g-1) 인덱스는 중간 서브 리스트의 left값이 되며 (g+1)인덱스는 오른쪽 서브 리스트의 left값이 된다.

k : 소팅이 진행 중일때는 배열을 지나가면서 각 요소의 인덱스를 지정하는 역할을 한다.

이 과정에서 arr[k]가 pivot1보다 작은지 pivot2보다 큰지 확인한다.

만약 arr[k]가 pivot1보다 작다면 arr[l]과 교환하여 제자리 그룹에 찾아가게 하고

만약 arr[k]가 pivot2보다 크면 arr[g]와 교환하여 제자리 그룹에 찾아가게 한다.

#include <stdio.h>
#include <Windows.h>

void SWAP(int* arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void DualPivotQuickSort(int* arr, int left, int right) {

    // right가 left보다 낮으면 안된다.
    if(left <= right) {
    
        // pivot1은 무조건 pivot2보다 낮은 값이어야 한다.
        if (arr[left] > arr[right])
            SWAP(arr, left, right);
        
        int pivot1 = arr[left], pivot2 = arr[right];
        int l, k, g;
        
        l = k = left + 1;
        g = right - 1;
        
        while (k <= g) {
            if (arr[k] < pivot1) {
                SWAP(arr, k, l);
                l++;
            }
            else {
                if(arr[k] > pivot2) {
                    while ( (arr[g] > pivot2) && (k < g)) g--;
                    
                    SWAP(arr, k, g);
                    g--;
                    
                    if (arr[k] < pivot1) {
                        SWAP(arr, k, l);
                        l++;
                    }
                }
            }
            k++;
        } // end while
        
        l--; g++;
        
        SWAP(arr, left, l);
        SWAP(arr, right, g);
        
        DualPivotQuickSort(arr, left, l - 1);
        DualPivotQuickSort(arr, l + 1, g - 1);
        DualPivotQuickSort(arr, g + 1, right);
    }
}

void main() {
    int arr[] = { 3, 1, 2, 4, 9, 6, 8, 7, 10, 5 };
    
    printf_s("정렬 전 : \n");
    
    for (int i = 0; i < 10; i++)
        printf_s("%d ", arr[i]);
    
    printf_s("\n");
    
    DualPivotQuickSort(arr, 0, 9);
    
    printf_s("정렬 후: \n");
    
    for (int i = 0; i < 10; i++)
        printf_s("%d ", arr[i]);
    
    printf_s("\n");
    
    system("pause");
}

전체적인 로직을 말로 풀면 다음과 같다. 소스코드에 있는 라인넘버와 설명을 같이보면 된다.

13 - 배열의 길이에 대한 오류를 걸러내기 위해 사용

16 - pivot1은 무조건 pivot2보다 작아야한다. 그렇지 않을 경우 정렬이 되지 않는다.

19 - pivot1과 pivot2를 각각 left, right로 설정한다. (양끝 2개 요소를 각각 left, right로)

21~23 - l,k 변수를 left+1 인덱스번호로 시작하게 설정, g 변수를 right-1인덱스 번호로 시작하게 설정

25 - k가 g보다 작거나 같은 경우 반복문 실행. 즉, pivot2보다 큰 값이 들어갈 자리인 g변수와, 현재 인덱스 비교를 하는 k변수가 교차되면 모든 인덱스에 대한 검사를 마친 것이므로 종료한다.

26~28 - 만약 현재 검사하는 요소(arr[k])가 pivot1보다 작다면 arr[k]는 자기 자리가 아니다. 왜냐하면 pivot1 오른쪽에는 pivot1보다 큰 자리가 되어야 하기 때문이다. 따라서, (현재 pivot1보다 작은 값이 다음에 들어가야할 자리를 가리키는 l)과 arr[k]를 교환한다.

이후, 다음으로 pivot1보다 작은 값을 넣을 자리를 l++를 통하여 세팅한다. (42번 라인으로 점프)

30 - 만약 현재 검사하는 요소(arr[k])가 pivot1보다 작은 것이 아니라면

31 - 그리고 현재 검사하는 요소(arr[k])가 pivot2보다 큰것이라면 -> 오른쪽 서브 리스트그룹에 들어갈 요소라면

 * 현재 k의 위치는 중간 서브 리스트에 들어갈 그룹의 자리에 있는 것이다.

 * 만약 현재 검사하는 요소(arr[k])가 pivot1보다 작은 것도 아니고(30번라인),

pivot2보다 큰 것도 아니라면(23번 조건문), 중간 서브 리스트 그룹에 잘 들어있는 것이므로 42번 라인으로 점프하여 k를 증가시키고 다음 요소를 검사

32~33 - 1번 조건과 2번 조건이 맞는 동안 g를 감소시킨다.

(1번조건) 변수 g가 가리키는 값(arr[g])이 pivot2보다 큰 경우

   -> (arr[g])가  pivot2보다 큰 경우는 오른쪽 서브 리스트의 요소로서 제자리 그룹에 존재하는 것이므로)

(2번조건) 아직 모든 요소의 검사가 끝나지 않은 경우

   -> (k는 요소를 검사하는 인덱스, g는 pivot2보다 큰 값이 들어갈 다음 자리를 가리키는 인덱스 이므로)

한마디로, 이는 현재 검사하는 요소(arr[k])가 pivot2보다 큰 경우 제자리 이고, k<g라면 아직 모든 인덱스가 검사된 것이 아니므로 교환하지 않고 g만 감소시켜 다음 자리를 찾아가게 하는 것

24 - 만약 현재 g가 가리키는 요소(arr[g])가 pivot2보다 같거나 작다면(많은 경우 1번째 조건이 false가 되어 나오게 될 것이다.),

arr[k]는 pivot2보다 커서 오른쪽 서브 리스트에 들어가야 하고(31번 라인)

arr[g]는 pivot2보다 작아서 중간 서브 리스트에 들어가야 하므로(42번 라인의 1번째 조건 false)

이 둘을 바꾸면 arr[k]는 제대로 된 그룹 자리로 들어간다.

단, arr[g]는 pivot2보단 작은 그룹으로 이동하긴 하였으나 아직 pivot1보다 작은지 큰지를 안따졌다.

35 - pivot2보다 큰 값이 새로 들어갈 자리(g인덱스)가 채워졌으니 -1을 하여, 새로운, pivot2보다 큰 수가 들어갈 자리를 세팅

36~38 - 26번에서 자리를 바꾼, 현재 k인덱스의 값(기존의 g인덱스 자리에 있었는데, pivot2보다 작아서 바뀌어서 중간 그룹 자리인 k로 온 인덱스의 값)이 혹시 pivot1보다 작다면 자신의 자리가 아니므로 pivot1보다 작은 값이 들어갈 다음 자리인 l과 교환한다. 그리고 pivot1보다 작은 값이 들어갈 다음 자리인 l의 값을 1 증가시켜 다음 값이 들어올 수 있게 한다.

 *25~42번 까지의 로직을 k<=g인 경우까지 진행한다. k와 g가 같아진다면, 현재 검사하는 요소(arr[k])가 곧 pivot2보다 큰 값이 들어갈 다음 자리 인덱스의 값(arr[g])과 동일하게 되는 경우이다. 검사는 k에서 g방향으로 하므로, 아직 arr[g]에 대한 검증이 끝난 것이 아니기 때문에, k<g가 아니라 k<=g 조건을 걸어야 마지막 요소까지 잘 확인하게 된다.

마지막 요소(k==g일때의 arr[g]의 값)까지 검사가 끝난다면 k가 g보다 커질 것이고 이는 모든 요소의 검사의 끝을 의미한다.

46 - 끝에서 l와 g에 대해서 각각 -1과 +1을 수행한다. 그 이유는,

l의 역할은 pivot1보다 작은 값이 들어갈 "다음" 위치를 가리키는 인덱스이고

g의 역할은 pivot2보다 큰 값이 들어갈 "다음" 위치를 가리키는 인덱스이다.

예를 들어서, left가 0일 경우에서 소팅이 끝난 직후를 가정하겠다.

현재 l값이 3이라면, 3번 인덱스는 pivot1보다 작은 값이 들어갈 "다음"자리가 되는 것이다. 아직 들어온 것이 아니라는 말이다.

즉, 현재 l의 값에는 pivot1보다 큰 값이 들어있고 이는 중간 부분 리스트에 들어갈 요소가 제대로 들어간 것이다.

그러나 이미 연산은 끝나버려서 더 이상 확인할 요소가 없다.

0번 인덱스(left)는 현재 pivot1의 값이 있고, l은 분명 left+1(0+1 = 1번 인덱스)부터 시작을 한다.

따라서 1번 인덱스 ~ 2번 인덱스 (총 2개)는 분명 pivot1보다 작은 값들이다.

하지만 l은 pivot1보다 작은 값이 들어갈 "다음" 자리를 가리키고 있으므로 이를 1을 빼줘야 한다.

지금까지 설명한 것을 표로 그리면 다음과 같다

pivot1	pivot1보다 작은 값 1	pivot1보다 작은 값 2	pivot1보다 큰 값 1	pivot1보다 큰 값 2	...
0 (left)	1	2	3 ( 변수 l )	4	...

여기서 l에서 -1을 하면 다음과 같아진다.

pivot1	pivot1보다 작은 값 1	pivot1보다 작은 값 2	pivot보다 큰 값 1	pivot1보다 큰 값 2	...
0 (left)	1	2 ( 변수 l )	3	4	...

여기 까지가 44번 라인을 실행한 것이다.

l과 g를 각각 -1, +1을 했다면 이제 l인덱스(위 그림에서 2번 인덱스)에 해당하는 자리가 pivot1, g인덱스에 해당하는 자리가 pivot2의 자리가 해당된다.

48~49 - 그러므로 left인덱스(0번 인덱스)와 l인덱스(2번 인덱스)를 교환한다. 이렇게 하면 다음 그림이 된다.

pivot1보다 작은 값 2	pivot1보다 작은 값 1	pivot1	pivot1보다 큰 값 1	pivot1보다 큰 값 2	...
0 (left)	1	2 ( 변수 l )	3	4	...

결국 2번 인덱스는 pivot1의 최종 위치가 된다. (이후 추가적인 소팅 연산에서 아예 연산에서 제외되도록 인덱스 인자를 준다.)

g도 비슷하니까 잘 생각해보기 바란다.

위 문장이 이해가 안된다면 이해가 될 때까지 보기 바란다. "다음"이라는 글자가 키워드이다.

51~53 - pivot1, pivot2의 자리가 정해졌으므로 이제 왼쪽, 중간, 오른쪽 부분 리스트를 다시 Dual Pivot Quick Sort를 사용하여 정렬한다.

인자는 left(0번 인덱스) ~ (l-1)(1번 인덱스)가 되어 2개를 비교할 것이다.

만약 여기서도 소팅이 끝나면 결국 DualPivotQuickSort(arr, 0, 0); 과 DualPivotQuickSort(arr, 1, 1) 2개의 함수가 호출될 것이고

길이가 1인 알고리즘은 자기 자신을 바꿔  제자리를 찾은 것이 된다.

*참고로 위 로직은 인터넷 서핑하다가 찾은 로직을 가져다가 오류만을 수정한 소스이므로 속도&가독성에 있어서 완벽하게 최적화된 소스는 아니다.​ 

참조 : https://www.youtube.com/watch?v=yRJ1Zb4pCM4