Separate even and odd numbers

Problem Description

Write a function that takes an array of integers and returns reordered array such that the even entries appear first. Solve it without allocating additional storage.

Example

input: [1,2,3,4,5,6,7,8]
output: [2,4,6,8,1,3,5,7] or [8,2,4,6,1,7,5,3]

Algorithm

Key Idea: take advantage of the fact that with arrays, you can operate efficiently on both ends

• Partition the array into three subarrays: Even, Unclassified, and Odd (appearing in this order)
• Initially Even and Odd are empty and Unclassified is the entire array
• Iterate through Unclassified while moving its elements to the boundaries of the Even and Odd subarrays via swap. Thereby, the Unclassified gets shrinked and the Even and Odd expand.

Code

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

Test Cases

A = [1,2,3,4,5,6,7,8,9]
even_odd(A)
print(A)
# [8, 2, 6, 4, 5, 7, 3, 9, 1]

Analysis

We do a constant amount of processing per entry, so the time complexity is O(n). The additional space complexity is O(1).