【Python】偶数・奇数ごとに配列を並べ替えるパリティソートの実装方法

整数がいくつか格納された配列 A があるとしましょう。この配列を、偶数が先頭側、奇数が後ろ側に来るように並べ替えることを考えます。たとえば、配列が A = [1, 5, 6, 8, 7, 2, 3] であれば、実行結果は [6, 8, 2, 1, 5, 7, 3] のようになります。

アルゴリズムの考え方

この問題は、2つのインデックス（ポインタ）を使った「その場での入れ替え（インプレーススワップ）」によって効率的に解くことができます。手順は次のとおりです。

• i = 0、j = 0 で初期化します。

• j が配列の長さより小さい間、以下を繰り返します。

  • arr[j] が偶数であれば、arr[i] と arr[j] を入れ替え、i を 1 増やします。

  • その後、j を 1 増やします。

• ループが終わったら arr を返します。

ポイントは、変数 i が常に「次に偶数を配置すべき位置」を指し続けることです。偶数を見つけるたびに先頭側へ送り出すため、走査が完了した時点で配列の前半には偶数、後半には奇数が集まります。

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()
nums = [1, 5, 6, 8, 7, 2, 3]
print(ob1.sortArrayByParity(nums))

入力

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

出力

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

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n) です。また、要素の入れ替えを元の配列内で完結させるため、追加のメモリが不要（空間計算量 O(1)）である点も大きな利点といえます。