Pythonで配列を指定範囲を基準に3方向へ分割する方法

配列とその範囲 [startval, endval] が与えられたとき、配列を次の3つの部分に分割することを考えます。

• 第1部分：startval より小さいすべての要素（先頭に配置）
• 第2部分：startval 以上 endval 以下のすべての要素（中間に配置）
• 第3部分：endval より大きいすべての要素（末尾に配置）

この操作は「3方向パーティション」と呼ばれ、クイックソートの3ウェイ分割やデータの前処理など、さまざまな場面で応用される基本的なテクニックです。

実行例

入力: A = [1, 14, 51, 12, 4, 2, 54, 20, 87, 98, 3, 1, 32]
startval = 14, endval = 54
出力: A = [1, 12, 4, 2, 3, 1, 14, 51, 54, 20, 32, 87, 98]

出力では、14 未満の要素（1, 12, 4, 2, 3, 1）が先頭に集まり、続いて 14〜54 の範囲内の要素（14, 51, 54, 20, 32）、最後に 54 より大きい要素（87, 98）が並びます。各グループ内では、元の配列での出現順序が保たれます。

アルゴリズム

ステップ1: リストを3つの部分に分割する。
　第1部分 … startval 未満の要素
　第2部分 … startval 以上 endval 以下の要素
　第3部分 … endval より大きい要素
ステップ2: 3つの部分をこの順に連結する。

サンプルコード

def partition_array(input_list, low_val, high_val):
    # 入力リストを3つの部分に分割する
    first_part = [num for num in input_list if num < low_val]
    second_part = [num for num in input_list if low_val <= num <= high_val]
    third_part = [num for num in input_list if num > high_val]

    # 3つの部分を連結して返す
    return first_part + second_part + third_part


# ドライバプログラム
if __name__ == "__main__":
    my_input = [10, 140, 50, 200, 40, 20, 540, 200, 870, 980, 30, 10, 320]
    my_low_val = 140
    my_high_val = 200
    print(partition_array(my_input, my_low_val, my_high_val))

出力結果

[10, 50, 40, 20, 30, 10, 140, 200, 200, 540, 870, 980, 320]

コードの解説

この実装ではリスト内包表記を活用し、条件ごとに要素を抽出しています。1つ目の内包表記は low_val 未満の要素を、2つ目は low_val 以上 high_val 以下の要素を、3つ目は high_val を超える要素をそれぞれ収集します。最後に + 演算子で3つのリストを連結すれば、目的の順序で並んだ新しいリストが完成します。

計算量はリストを3回走査するため全体で O(n)、必要な追加メモリも O(n) です。また、各グループ内で元の順序が崩れない「安定な分割」になっている点も大きな特徴です。