5 Best Ways to Sort an Array by Parity in Python

Rate this post

๐Ÿ’ก Problem Formulation: We often face scenarios where we need to rearrange arrays so that even numbers precede odd numbers. This operation is known as sorting by parity. For instance, given an input array [3, 1, 2, 4], a possible sorted by parity output could be [2, 4, 3, 1]. This article explores five efficient methods to perform this task in Python.

Method 1: Using Two Pointer Technique

The two-pointer technique uses two indices to iterate through the array from opposite directions, swapping out-of-place elements. This efficient in-place algorithm is straightforward and doesn’t need extra memory for output.

Here’s an example:

def sort_by_parity_two_pointers(arr):
    left, right = 0, len(arr) - 1
    while left  arr[right] % 2:
            arr[left], arr[right] = arr[right], arr[left]
        if arr[left] % 2 == 0: left += 1
        if arr[right] % 2 == 1: right -= 1
    return arr

print(sort_by_parity_two_pointers([3, 1, 2, 4]))

The output of this code snippet:

[2, 4, 1, 3]

This method swiftly reorders the array with minimal moves. As the two pointers converge towards the center, elements are swapped only when an even number is behind an odd one. It’s an optimal solution that operates in linear time and constant space complexity.

Method 2: Using Filter and Concatenation

This approach sorts the array into two lists โ€“ one with all the even numbers and one with all the odd numbers โ€“ using the filter function. These lists are then concatenated. It’s elegant but uses extra space.

Here’s an example:

def sort_by_parity_filter(arr):
    evens = list(filter(lambda x: x % 2 == 0, arr))
    odds = list(filter(lambda x: x % 2 != 0, arr))
    return evens + odds

print(sort_by_parity_filter([3, 1, 2, 4]))

The output of this code snippet:

[2, 4, 3, 1]

The filter function applies a lambda to process only the required elements, which are then merged. It’s not as memory-efficient as the two-pointer method, but it is cleaner and can be more readable.

Method 3: Using Sorted Function with Key Parameter

The sorted function in Python can take a key parameter that allows custom sorting logic. By defining the key as the modulo function, we can sort by parity elegantly.

Here’s an example:

def sort_by_parity_sorted(arr):
    return sorted(arr, key=lambda x: x % 2)

print(sort_by_parity_sorted([3, 1, 2, 4]))

The output of this code snippet:

[2, 4, 3, 1]

The sorted function with a key provides a one-liner solution that is both elegant and simple. However, note that this method creates a new list, which means that the sort is not in-place and requires additional memory.

Method 4: List Comprehensions

List comprehensions in Python provide a succinct way to create lists. They can be used to separate even and odd numbers and then concatenate them into a single sorted list.

Here’s an example:

def sort_by_parity_comprehension(arr):
    return [x for x in arr if x % 2 == 0] + [x for x in arr if x % 2 != 0]

print(sort_by_parity_comprehension([3, 1, 2, 4]))

The output of this code snippet:

[2, 4, 3, 1]

List comprehensions replace the filter function with a more Pythonic construct that is faster and can be more readable. However, it suffers from the same memory usage issues as the filter-based approach due to list creation.

Bonus One-Liner Method 5: Built-in Sort with Custom Key

Python’s built-in sort method can be made to sort by parity in-place using a custom key, like the sorted function. This method modifies the original list.

Here’s an example:

arr = [3, 1, 2, 4]
arr.sort(key=lambda x: x % 2)
print(arr)

The output of this code snippet:

[2, 4, 3, 1]

By using the sort() method’s key parameter, we achieve in-place sorting by parity. This method maintains a balance between memory efficiency and readability, providing a very practical solution in many cases.

Summary/Discussion

  • Method 1: Two Pointer Technique. Best for in-place array modification. Efficient but less straightforward for beginners.
  • Method 2: Filter and Concatenation. Clean and readable. Requires extra space for sorting, less memory efficient.
  • Method 3: Sorted Function. Simplistic and elegant. Not in-place, additional memory is needed for the result.
  • Method 4: List Comprehensions. Pythonic and possibly faster than filter. Similar cons as methods 2 and 3 regarding memory usage.
  • Method 5: Built-in Sort with Custom Key. In-place and readable. The most pragmatic approach if list modification is acceptable.