CA 09 - Move All Negative Elements to end

Problem

Given an unsorted array arr[] containing both negative and positive integers, the task is to move all negative elements to the end of the array without changing the order of positive and negative elements.

Output

Example 1
Output: [1, 3, 2, 11, 6, -1, -7, -5]
Example 2
Output: [7, 9, 10, 11, -5, -3, -4, -1]

My Approach

To solve this problem, I used a stable partition method.

I first iterate through the array and collect all positive elements in their original order.

Then I iterate again and place all negative elements after the positives.

This ensures that the relative order of both positive and negative elements is preserved.

This approach works because we are separating elements based on their sign while maintaining their original sequence.

Code

def move_negatives(arr):
    positives = []
    negatives = []
    for num in arr:
        if num >= 0:
            positives.append(num)
        else:
            negatives.append(num)
    arr[:] = positives + negatives