[알고리즘] 3-Way inPlaceQuickSort - 네덜란드 국기 알고리즘

서론

quick sort

quick sort는 기준 원소 pivot을 설정 후 기준 원소보다 작은 / 기준 원소와 같은 / 기준 원소보다 큰 리스트 3개로 분할하여 정렬한다.

따라서 입력 리스트의 모든 원소는 세 개의 부 리스트 중 하나에 삽입된다.

 

inPlaceQuickSort

quick sort는 제자리에서 수행되도록 구현이 가능하다. 

입력 리스트의 원소를 재배치할 때 값을 삽입하는 대신 대체 작업을 수행한다.

대체란 입력 리스트 내에서 재배치되어야 할 원소들의 자리를 맞바꾸는 것이다.

 

※ 지금부터 설명하는 부분은 inPlaceQuickSort를 구현할 때 배열로 구현한다고 가정한다.

연결리스트에서는 쉽게 해결이 가능한 문제이기에 고민할 필요가 없었다.

※ quicksort를 진행할 때 분할 과정에 집중한다.

 

2-way inPlaceQuickSort

보통 배열에서 inPlaceQuickSort를 구현하게 되면 2-way로 제자리 분할을 수행한다.

➡️  입력 배열이 유일한 원소들로만 구성된 것을 전제로 한 버전

 

위의 설명과 달리 2-way(2 분할)은 pivot을 기준으로 작은 / 큰 원소들의 부분으로 나누게 된다.

따라서 반환될 때 배열은 아래와 같은 상황이 되고 코드에서의 반환 값은 pivot의 위치를 반환하게 된다.

 

LT(pivot보다 작은 원소들)

pivot

GT(pivot보다 큰 원소들)

 

int inPlacePartition(int *arr, int l, int r, int k)
{
    int i = 0, j = 0, pivot = 0;

    pivot = arr[k];
    swap(arr, k, r);
    i = l;
    j = r - 1;

    while (i <= j)
    {
        while (i <= j && arr[i] <= pivot)
            i++;
        while (i <= j && arr[j] >= pivot)
            j--;
        if (i < j)
            swap(arr, i, j);
    }
    swap(arr, i, r);
    return i;
}

출처 : < 알고리즘 원리와 응용 - 국형준 > 책

 

하지만 입력 배열이 중복 원소들로 구성되었다면 ❓ 

2-way inPlaceQuickSort로도 해결이 가능하다.

하지만 QuickSort에서 원하는 방식처럼 기준 원소보다 작은 / 기준 원소와 같은 / 기준 원소보다 큰 리스트 3개로 분할하여 정렬하는 것이 아니라, 중복된 값이 pivot으로 설정될 수 있게 된다.

따라서 불필요한 연산이 실행되게 된다.

 

---

그렇다면 3-way inPlaceQuickSort는 어떻게 구현할 수 있을까?

이를 해결하기 위해 네덜란드 국기 알고리즘을 변형하여 사용할 수 있다.

네덜란드 국기 알고리즘 (Dutch national flag problem)

- 다익스트라가 제안한 계산 문제

- 네덜란드의 국기는 빨간색, 흰색, 파란색의 3가지 색상으로 구성되어 있다. 이 세 가지 색상의 공이 한 줄에 무작위로 배열되어 있는 경우, 동일한 색상의 모든 공이 함께 있고 집합적인 그룹이 올바른 순서가 되도록 정렬하는 것

 

아래의 수도코드를 보면 중간값을 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽으로 값이 swap 되어 최종적으로 정렬된다.

 

procedure three-way-partition(A : array of values, mid : value):
    i ← 0
    j ← 0
    k ← size of A - 1

    while j <= k:
        if A[j] < mid:
            swap A[i] and A[j]
            i ← i + 1
            j ← j + 1
        else if A[j] > mid:
            swap A[j] and A[k]
            k ← k - 1
        else:
            j ← j + 1

출처 : 위키피디아

 

네덜란드 국기 알고리즘은 원소가 3가지로 한정되어있다고 가정한다.

따라서 이 알고리즘을 한번 실행하면 아래와 같이 배열은 정렬된다.

(아래의 예시 숫자는 임의의 개수, 임의의 수로 작성해두었다.)

 

가장 작은 원소의 배열  (1, 1, 1, 1)

중간 원소의 배열 (2, 2, 2)

가장 큰 원소의 배열 (3, 3, 3)

 

위의 코드를 3가지 원소가 들어있는 배열로 한 번 실행했을 경우 mid값이 2일 때 아래 그림과 같이 진행된다.

첫 번째와 두번째 줄은 각각 원소 개수 / 배열 원소 값 입력이다. (start = i, end = j)

 

3-way inPlaceQuickSort

네덜란드 국기 알고리즘을 활용하여 3-way inPlaceQuickSort 코드를 작성할 수 있다.

 

EQ inPlacePartition(int *arr, int start, int end, int k)
{
    EQ equal;
    int mid = start;
    int pivot = arr[k];

    while (mid <= end)
    {
        if (arr[mid] < pivot){
            swap(arr, start, mid);
            start += 1;
            mid += 1;
        }
        else if (arr[mid] > pivot){
            swap(arr, end, mid);
            end -= 1;
        }
        else
            mid += 1;
    }
    equal.left = start;
    equal.right = mid - 1;
    return equal;
}

 

위의 코드를 중복 원소가 들어있는 배열로 한 번 실행했을 경우 pivot 값(mid)이 5일 때 아래와 같은 결과가 출력된다.

첫 번째와 두번째 줄은 각각 원소 개수 / 배열 원소 값 입력이다.

 

결과에서 볼 수 있듯이 pivot값인 5를 기준으로 5보다 작은 값 / 5로 이루어진 값 / 5보다 큰 값으로 배열이 분할되었다.

 

 

typedef struct EQUAL{
    int left;   //pivot 그룹의 처음 인덱스
    int right;  //pivot 그룹의 마지막 인덱스
}EQ;

 

3-way inPlaceQuickSort 함수는 2-way inPlaceQuickSort과 달리 pivot으로 이루어진 그룹의 처음 인덱스와 끝 인덱스 변수로 이루어진 구조체를 반환한다.

네덜란드 국기 알고리즘에서의 최종 결과에서 볼 수 있듯이 mid의 마지막 위치는 pivot 그룹의 인덱스 + 1을 가리킨다.

 

 

 

그래서 마지막 부분에 아래와 같이 구조체의 변수들에 값을 대입해준다.

 

equal.left = start;
equal.right = mid - 1;

 

이 과정을 재귀적으로 반복하게 되면 중복 원소들로 구성된 배열을 inPlaceQuickSort로 처리할 수 있게 된다.

 

---

최종 코드

 

// 퀵정렬 - 중복키 ver

#include <stdio.h>
#include <stdlib.h>

typedef struct EQUAL{
    int left;
    int right;
}EQ;

int findPivot(int l, int r);
EQ inPlacePartition(int *arr, int l, int r, int k);
void inPlaceQuickSort(int *arr, int left, int right);
void swap(int *arr, int i, int j);
void printArray(int *arr, int n);

int main()
{
    int n = 0;
    int *arr = NULL;

    scanf("%d", &n);
    arr = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
        scanf("%d", arr + i);
    inPlaceQuickSort(arr, 0, n-1);
    printArray(arr, n);
    return (0);
}

int findPivot(int l, int r)
{
    return rand()%(r - l + 1) + l;
}

EQ inPlacePartition(int *arr, int start, int end, int k)
{
    EQ equal;
    int mid = start;
    int pivot = arr[k];

    while (mid <= end)
    {
        if (arr[mid] < pivot){
            swap(arr, start, mid);
            start += 1;
            mid += 1;
        }
        else if (arr[mid] > pivot){
            swap(arr, end, mid);
            end -= 1;
        }
        else
            mid += 1;
    }
    equal.left = start;
    equal.right = mid - 1;
    return equal;
}

void inPlaceQuickSort(int *arr, int left, int right)
{
    int k;
    EQ equal;

    if (left >= right)
        return ;
    k = findPivot(left, right);
    equal = inPlacePartition(arr, left, right, k);
    inPlaceQuickSort(arr, left, equal.left - 1);
    inPlaceQuickSort(arr, equal.right + 1, right);
}

void printArray(int *arr, int n)
{
    for(int i = 0; i < n; i++)
        printf(" %d", arr[i]);
    printf("\n");
}

void swap(int *arr, int i, int j)
{
    int tmp;

    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}