C#で余分な領域を使わずに配列内の0・1・2をソートする方法（オランダ国旗問題）

「オランダ国旗問題」は、0・1・2 のみで構成された配列を、追加のメモリ領域を使わずに一括でソートする古典的なアルゴリズム問題です。この記事では、C# を使って3ポインタ方式でこの問題を解く方法を解説します。

アルゴリズムの考え方

この手法では、low、mid、high という3つのポインタを使用します。

• low と mid は配列の先頭（インデックス0）から開始します。
• high は配列の末尾（最後の要素）を指します。

そのうえで、mid が指す要素の値に応じて以下のように処理を振り分けます。

処理のルール

1. arr[mid] == 0 の場合：arr[mid] と arr[low] を交換し、low と mid の両方のポインタを1つずつ進めます。
2. arr[mid] == 1 の場合：交換は不要です。mid ポインタだけを1つ進めます。
3. arr[mid] == 2 の場合：arr[mid] と arr[high] を交換し、high ポインタを1つ手前に戻します。

この操作を mid が high を追い越すまで繰り返すことで、配列全体が「0 → 1 → 2」の順に整列されます。

計算量

各要素は一度だけ走査されるため、時間計算量は O(N)、追加のメモリ使用量は O(1) となります。非常に効率的なソート手法です。

C#での実装例

using System;
namespace ConsoleApplication{
    public class Arrays{
        private void Swap(int[] arr, int pos1, int pos2){
            int temp = arr[pos1];
            arr[pos1] = arr[pos2];
            arr[pos2] = temp;
        }
        public void DutchNationalFlag(int[] arr){
            int low = 0;
            int mid = 0;
            int high = arr.Length - 1;
            while (mid <= high){
                if (arr[mid] == 0){
                    Swap(arr, low, mid);
                    low++;
                    mid++;
                }
                else if (arr[mid] == 2){
                    Swap(arr, high, mid);
                    high--;
                }
                else{
                    mid++;
                }
            }
        }
}
class Program{
    static void Main(string[] args){
        Arrays a = new Arrays();
        int[] arr = { 2, 1, 1, 0, 1, 2, 1, 2, 0, 0, 1 };
        a.DutchNationalFlag(arr);
        for (int i = 0; i < arr.Length; i++){
            Console.WriteLine(arr[i]);
        }
        Console.ReadLine();
    }
}

実行結果

0 0 0 0 1 1 1 1 2 2 2

まとめ

オランダ国旗アルゴリズムを使えば、0・1・2 からなる配列を追加領域なしで線形時間 O(N) でソートできます。3つのポインタの役割と移動ルールさえ理解すれば、実装もシンプルなので、面接対策や競技プログラミングでも役立つ重要なテクニックです。