Pythonで配列をパリティ（偶数・奇数）ごとに並べ替える方法

問題の概要

いくつかの数値を含む配列 A が与えられたとします。この配列を、偶数が先頭に集まり、その後に奇数が続くように並べ替えます。

たとえば、配列が A = [1, 5, 6, 8, 7, 2, 3] の場合、期待される結果は [6, 8, 2, 1, 5, 7, 3] のようになります。

解法のアプローチ：2つのポインタを使う

この問題は、いわゆる「2ポインタ法」と呼ばれるシンプルな手法で効率よく解けます。配列を一度だけ走査しながら、偶数を見つけるたびに配列の前方へ移動させていく考え方です。

具体的には、次の手順に従います。

• インデックス i := 0 と j := 0 を初期化する
• j が配列の長さ未満である間、以下を繰り返す
  • arr[j] が偶数であれば、arr[i] と arr[j] を入れ替え、i を 1 増やす
  • j を 1 増やす
• 最後に arr を返す

ここで i は「次に偶数を置くべき位置」を指し、j は現在チェック中の要素を指します。偶数が見つかるたびに先頭側へスワップしていくことで、自然と偶数が前半に、奇数が後半に集まります。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

class Solution(object):
    def sortArrayByParity(self, a):
        i = 0
        j = 0
        while j < len(a):
            if a[j] % 2 == 0:
                a[i], a[j] = a[j], a[i]
                i += 1
            j += 1
        return a

ob1 = Solution()
print(ob1.sortArrayByParity([1,5,6,8,7,2,3]))

入力

[1,5,6,8,7,2,3]

出力

[6,8,2,5,7,1,3]

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリを使用せず配列内で入れ替えを行うため、空間計算量は O(1) となります。

なお、出力結果では偶数同士・奇数同士の相対的な順序は元の配列と異なる場合があります。これはインプレースでのスワップを行っているためで、安定性が必要な場合は別途ソート処理を組み合わせる必要があります。