正負の値を含むリストの要素を正負交互に並び替える

問題

今日はRearrange positive and negative numbers in O(n) time and O(1) extra spaceの問題にチャレンジする。

この問題は、正の数と負の数の両方がランダムな順序で含まれていて、正の数と負の数が交互に配置されるように要素を並び替える問題。正の数と負の数は同じではなく、より多くの正の数がある場合、それらはリストの最後に表示しておけば良い。さらに負の数がある場合は、それらも最後に表示しておく。

Input : [-1, 2, -3, 4, 5, -7, 8, 9]
Output: [4, -3,  5,-1, 2, -7, 8, 9]

実装

問題を対処するためには、QuickSortのパーティションの考え方を利用するのが良いとのこと。つまり、ランダムなリストを一度、正の数と負の数にパーティションを利用して分離。すべての負の数が正の数の前に配置できたら、負の数と正の数が交互に並び替えるように、値をスワップしていく。

いつもどおり、デバッグの要素を図解してイメージしやすいようにする。ランダムなリストを一度、正の数と負の数にパーティションを利用して分離する部分がこの画像のイメージ。

すべての負の数が正の数の前に配置できたら、負の数と正の数が交互に並び替えるように、値をスワップしていく部分がこの画像のイメージ。

from typing import List

def ReArrange(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)

    i = -1
    for j in range(len_numbers):
        if numbers[j] < 0:
            i += 1
            numbers[i], numbers[j] = numbers[j], numbers[i]

    pos, neg = i + 1, 0

    while pos < len_numbers and neg < pos and numbers[neg] < 0:
        numbers[neg], numbers[pos] = numbers[pos], numbers[neg]
        pos += 1
        neg += 2


if __name__ == '__main__':
    numbers = [-1, 2, -3, 4, 5, -7, 8, 9]
    print(numbers)
    ReArrange(numbers)
    print(numbers)

[-1, 2, -3, 4, 5, -7, 8, 9]
[4, -3, 5, -1, 2, -7, 8, 9]