Javaで0・1・2の配列をソートする方法｜DNF（オランダ国旗）アルゴリズムの実装

問題の概要

0、1、2 のみで構成された配列が与えられ、すべての「0」を先頭に、「1」を中間に、「2」を最後に配置するように並べ替えます。このとき、追加の配列を使用せずインプレース（in-place）でソートする必要があります。

この問題は、DNF（Dutch National Flag：オランダ国旗）ソートアルゴリズムを用いることで効率的に解けます。このアルゴリズムは、計算機科学者エドガー・W・ダイクストラが提唱した「オランダ国旗問題」に由来する古典的な手法で、3種類の値（ここでは 0・1・2）をたった1回の走査で整列できるのが特徴です。

入力例 1

arr[ ] = {2, 0, 0, 1, 2, 1}

出力：

0 0 1 1 2 2

説明：DNFソートアルゴリズムでこの配列を並べ替えると、{0, 0, 1, 1, 2, 2} が出力されます。

入力例 2

arr[ ] = {0, 1, 1, 2, 1, 1, 0}

出力：

0 0 1 1 1 1 2

説明：同様にDNFソートを適用すると、{0, 0, 1, 1, 1, 1, 2} が出力されます。

解き方のアプローチ

0・1・2 を含む配列のソートには、DNFソートアルゴリズムが有効です。
DNFソートアルゴリズムでは、3つのポインタを使って配列を走査しながら、必要な要素どうしを交換していきます。

• low ポインタ：配列の先頭に配置します。「0」を集める領域の境界を示します。

• high ポインタ：配列の末尾に配置します。「2」を集める領域の境界を示します。

• mid ポインタ：先頭から順に走査を進めるカーソルです。

アルゴリズムの手順

1. low を配列の先頭、high を配列の末尾、mid も先頭に初期化します。
2. mid が指す要素が「0」の場合：mid と low の要素を交換し、low と mid をそれぞれ 1 つ進めます。
3. mid が指す要素が「2」の場合：mid と high の要素を交換し、high を 1 つ戻します（mid は動かさず、交換後の要素を再度判定します）。
4. mid が指す要素が「1」の場合：すでに適切な位置にあるため、mid だけを 1 つ進めます。
5. mid が high を超えるまで、上記の手順を繰り返します。

このアルゴリズムの計算量は、時間 O(n)・空間 O(1) と非常に効率的です。

Javaでの実装例

public class Solution {

    public static void dnfSort(int[] arr, int n) {
        int low = 0;
        int high = n - 1;
        int mid = 0;

        while (mid <= high) {
            if (arr[mid] == 0) {
                // 「0」は先頭側へ交換
                int temp = arr[mid];
                arr[mid] = arr[low];
                arr[low] = temp;
                low++;
                mid++;
            } else if (arr[mid] == 1) {
                // 「1」はそのまま次へ
                mid++;
            } else {
                // 「2」は末尾側へ交換（mid は動かさず再判定）
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }

    public static void print(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 0, 1, 0, 1, 0, 1, 2, 2};
        int n = arr.length;
        dnfSort(arr, n);
        print(arr, n);
    }
}

実装のポイント：条件分岐は必ず else if を使って排他的に行いましょう。独立した if を連ねて書くと、交換直後の要素を同じ周回内で誤って二重に判定してしまい、意図しない並び順になることがあります。

実行結果

上記のコードを実行すると、次の出力が得られます。

0 0 0 0 1 1 1 2 2