数値の配列が与えられた時、配列の最初に偶数が現れるよう並び替える

出典

Elements of Programming Interviews in Python: The Insiders’ Guide (English Edition)

問題

数値の入った配列が渡されます。
偶数の値が最初に現れるように配列の値を並べ替えなければしてください。
なお、追加で配列を用意してはなりません。

解法

# List[int] -> None

def even_odd(A):
    next_even,next_odd = 0,len(A)-1
    while next_even < next_odd:
        if A[next_even] % 2 == 0:
            next_even += 1
        else:
            A[next_even],A[next_odd] = A[next_odd],A[next_even]
            next_odd -= 1
# Time Complexity O(N)
# The additional space complexity O(1)

値が2で割り切れる時はイテレーションのインデックスを後ろにずらし、そうでない場合には入れ替え（スワップ）と後ろのインデックスを前にずらすことで比較的容易に実装が出来ます。