네덜란드 국기(Dutch National Flag) 알고리즘이란

정의

네덜란드 국기(Dutch National Flag) 알고리즘은 0과 1로 구성된 배열을 정렬하는 알고리즘입니다.

사용을 고려해야 하는 경우

• 배열에 0과 1이 포함되어 있으며, 이를 정렬하여 0과 1을 구분하고자 할 때.
• 추가적인 메모리 공간 없이 배열의 요소를 제자리에서 정렬하고자 할 때.

사용하면 안되는 경우

네덜란드 국기 알고리즘은 0과 1로 구성된 배열을 정렬하는 데에만 사용할 수 있습니다. 다른 종류의 요소를 정렬하기 위해서는 다른 알고리즘을 사용해야 합니다.

장점

• 추가적인 메모리 공간을 사용하지 않고 제자리에서 배열을 정렬할 수 있습니다.
• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

단점

• 0과 1로 구성된 배열에 대해서만 적용 가능하며, 다른 요소를 정렬하는 데에는 적합하지 않습니다.
• 2가지 종류의 요소(0과 1)에 대해서만 정렬할 수 있으므로, 다른 종류의 요소가 추가되면 수정이 필요합니다.

구현 하는 법

1. 첫 번째 포인터(low)를 배열의 첫 번째 위치로, 두 번째 포인터(mid)와 세 번째 포인터(high)를 배열의 마지막 위치로 초기화합니다.
2. mid 포인터가 high 포인터보다 작거나 같은 동안 다음 단계를 반복합니다.
   • arr[mid]의 값에 따라 다음 동작을 수행합니다:
     • 0인 경우: arr[low]와 arr[mid]의 값을 교환하고, low와 mid를 1씩 증가시킵니다.
     • 1인 경우: mid를 1 증가시킵니다
     • 2인 경우: arr[mid]와 arr[high]의 값을 교환하고, high를 1 감소시킵니다.
3. 정렬된 배열을 반환합니다.

예제

public class DutchNationalFlagAlgorithm {
    public static void dutchNationalFlagSort(int[] nums) {
        int low = 0;  // Pointer for 0
        int mid = 0;  // Pointer for 1
        int high = nums.length - 1;  // Pointer for 2

        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap the current element with the low pointer element
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                // Move the mid pointer
                mid++;
            } else if (nums[mid] == 2) {
                // Swap the current element with the high pointer element
                swap(nums, mid, high);
                high--;
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}