Pythonで3色の配列をソートする方法（オランダ国旗問題の解き方）

問題の概要

n個のオブジェクトを含む配列があるとします。各オブジェクトは赤・白・青のいずれかの色で塗られており、同じ色のオブジェクトが隣り合い、かつ赤→白→青の順に並ぶように、配列をインプレース（追加メモリを使わずに）ソートします。

ここでは、色を数値で表現し、赤=0、白=1、青=2 とします。例えば、配列が [2,0,2,1,1,0] の場合、出力は [0,0,1,1,2,2] となります。

この問題は「オランダ国旗問題」としても知られており、3つのポインタを使うことで1回の走査で効率的に解くことができます。

解法のステップ

• low を 0、mid を 0、high を 配列の長さ − 1 に設定する
• mid ≤ high の間、次の処理を繰り返す：
  • arr[mid] = 0 の場合：arr[mid] と arr[low] を交換し、low と mid を1ずつ増やす
  • arr[mid] = 2 の場合：arr[mid] と arr[high] を交換し、high を1減らす
  • それ以外（arr[mid] = 1）の場合：mid を1増やすだけ

Pythonでの実装例

理解を深めるために、実際の実装コードを見てみましょう。

class Solution(object):
    def sortColors(self, nums):
        low = 0
        mid = 0
        high = len(nums)-1
        while mid<=high:
            if nums[mid] == 0:
                nums[low],nums[mid] = nums[mid],nums[low]
                low+=1
                mid += 1
            elif nums[mid] == 2:
                nums[high], nums[mid] = nums[mid], nums[high]
                high-=1
            else:
                mid += 1
        return nums

ob1 = Solution()
print(ob1.sortColors([2,0,2,1,1,0]))

入力

[2,0,2,1,1,0]

出力

[0,0,1,1,2,2]

アルゴリズムのポイント

この手法の優れている点は、以下の通りです。

• 時間計算量：O(n) — 配列を一度走査するだけでソートが完了します。
• 空間計算量：O(1) — 追加の配列を使わず、元の配列内だけで要素を入れ替えます。
• low より前はすべて0、high より後はすべて2 であることが常に保証されるため、mid の位置にある未確定要素だけを判定すればよい構造になっています。

なお、arr[mid] = 2 の場合に mid を進めないのは、交換後の値がまだ確認されていない可能性があるためです。この細かい点が正しく動作する鍵となります。