Pythonで色リストを「赤→緑→青」の順に並べ替えるアルゴリズム（オランダ国旗問題の解法）

「red」「green」「blue」といった色名の文字列が混在したリストがあるとします。このリストを、赤（red）が緑（green）より先に、緑が青（blue）より先に来るように並べ替えたいというのが今回の課題です。

例えば、入力が colors = ["blue", "green", "blue", "red", "red"] の場合、出力は ['red', 'red', 'green', 'blue', 'blue'] となります。

解法のアプローチ

この問題は、有名なオランダ国旗問題（Dutch National Flag Problem）と同じ構造を持っています。3つのポインタを使ってリストを一度だけ走査し、その場で（in-placeで）並べ替えることで、時間計算量 O(n)、追加メモリ O(1) という効率的な解法を実現できます。

具体的な手順は以下の通りです。

• 3つのカウンタ red = 0、green = 0、blue = 0 を初期化する。これらはそれぞれ「次に赤を書き込む位置」「次に緑を書き込む位置」「次に青を書き込む位置」を表す。
• リスト内の各文字列について以下を繰り返す。
  • 文字列が "red" の場合：
    • strs[blue] = "blue" として blue += 1
    • strs[green] = "green" として green += 1
    • strs[red] = "red" として red += 1
  • 文字列が "green" の場合：
    • strs[blue] = "blue" として blue += 1
    • strs[green] = "green" として green += 1
  • 文字列が "blue" の場合：
    • strs[blue] = "blue" として blue += 1
• 最後に strs を返す。

この手法のポイントは、走査中に「後ろから順に値をずらして書き込んでいく」ことです。赤を見つけたら青・緑・赤の3つを、緑を見つけたら青・緑の2つを、青を見つけたら青の1つだけを更新します。こうすることで、各要素が正しい区画に自然と集まっていきます。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, strs):
        green = 0
        blue = 0
        red = 0
        for string in strs:
            if string == "red":
                strs[blue] = "blue"
                blue += 1
                strs[green] = "green"
                green += 1
                strs[red] = "red"
                red += 1
            elif string == "green":
                strs[blue] = "blue"
                blue += 1
                strs[green] = "green"
                green += 1
            elif string == "blue":
                strs[blue] = "blue"
                blue += 1
        return strs

ob = Solution()
colors = ["blue", "green", "blue", "red", "red"]
print(ob.solve(colors))

入力

["blue", "green", "blue", "red", "red"]

出力

['red', 'red', 'green', 'blue', 'blue']

補足：よりシンプルな代替手段

実務では、この手動のポインタ操作に代わる簡単な方法もあります。

• ソートを使う方法： 色の優先順位を辞書で定義し、sorted(colors, key=lambda c: order[c]) のように並べ替える。コードは短くなりますが、計算量は O(n log n) になります。
• カウントして再構築する方法： 各色の出現回数を数えてから、["red"] * r + ["green"] * g + ["blue"] * b のように新しいリストを作る。O(n) 時間で処理できますが、元のリストを直接書き換える（in-place）方式ではありません。

ただし、面接やアルゴリズムの学習の場では、上記のような1パスで完結するポインタベースの解法が求められることが多いため、仕組みをしっかり理解しておくことをおすすめします。