3-Way 퀵 정렬(네덜란드 국기 알고리즘) 개념과 C++ 구현

이번 글에서는 퀵 정렬(QuickSort)의 변형인 3-Way 퀵 정렬에 대해 알아보겠습니다. 기본적인 퀵 정렬은 배열에서 하나의 원소를 피벗(pivot)으로 선택한 뒤, 피벗을 기준으로 배열을 분할하고, 피벗의 좌측과 우측 하위 배열에 대해 재귀적으로 정렬을 수행하는 방식입니다.

반면 3-Way 퀵 정렬은 이를 확장하여 배열을 세 개의 구역으로 나눕니다. 즉, 배열 arr[1..n]이 다음과 같은 세 부분으로 분할됩니다.

• arr[1..i] : 피벗보다 작은 원소들
• arr[i+1..j] : 피벗과 같은 원소들
• arr[j+1..n] : 피벗보다 큰 원소들

이 방식은 특히 중복된 값이 많은 배열에서 성능이 크게 향상되며, 네덜란드 국기의 빨강·흰색·파랑 세 색깔 영역으로 구분하는 모습과 유사하다고 하여 '네덜란드 국기(Dutch National Flag) 알고리즘'이라고도 불립니다.

알고리즘

partition(arr, left, right, i, j)

begin
    if right – left <= 1, then
        if arr[right] < arr[left], then
            swap arr[right] and arr[left]
        i := left
        j := right
        return
    end if
    mid := left, pivot = arr[right]
    while mid <= right, do
        if arr[mid] < pivot, then
            swap arr[left], arr[mid]
            increase left and mid by 1
        else if arr[mid] = pivot, then increase mid by 1
        else
            swap arr[mid], arr[right]
            decrease right by 1
    done
    i := left – 1
    j := mid
end

quicksort(arr, left, right)

begin
    if left >= right, then
        return
    end if
    define i and j
    partition(arr, left, right, i, j)
    quicksort(arr, left, i)
    quicksort(arr, j, right)
end

C++ 구현 예제

#include<iostream>
#include<vector>
using namespace std;
void partition(int arr[], int left, int right, int &i, int &j) {
    if (right - left <= 1) {
        if (arr[right] < arr[left])
            swap(arr[right], arr[left]);
        i = left;
        j = right;
        return;
}
int mid = left;
int pivot = arr[right];
while (mid <= right) {
    if (arr[mid]<pivot)
        swap(arr[left++], arr[mid++]);
        else if (arr[mid]==pivot)
            mid++;
        else if (arr[mid] > pivot)
            swap(arr[mid], arr[right--]);
    }
    i = left-1;
    j = mid;
}
void quicksort(int arr[], int left, int right) {
    if (left >= right) //원소가 0개 또는 1개인 경우
        return;
    int i, j;
    partition(arr, left, right, i, j);
    quicksort(arr, left, i);
    quicksort(arr, j, right);
}
void display(int arr[], int n) {
    for (int i = 0; i < n; ++i)
    cout << " " << arr[i];
    cout << endl;
}
int main() {
    int a[] = {4, 9, 4, 3, 1, 9, 4, 3, 9, 4, 3, 1, 4};
    int n = sizeof(a) / sizeof(int);
    display(a, n);
    quicksort(a, 0, n - 1);
    display(a, n);
}

실행 결과

4 9 4 3 1 9 4 3 9 4 3 1 4
1 1 3 3 3 4 4 4 4 4 9 9 9

위 예제에서 볼 수 있듯이, 중복 값이 많은 입력 배열 {4, 9, 4, 3, 1, 9, 4, 3, 9, 4, 3, 1, 4}가 오름차순으로 올바르게 정렬되었습니다. 일반 퀵 정렬에서는 중복 원소가 많을 경우 불균형한 분할로 인해 성능이 저하될 수 있지만, 3-Way 퀵 정렬은 같은 값을 한 번에 묶어 처리하므로 이러한 경우에도 안정적이고 효율적인 성능을 보여줍니다.