How to move all the negative elements to one side of the array

Overview

Suppose we've got an array with negative and positive numbers; it might be helpful to segregate its positive and negative elements. We can sort the array by moving the negative elements to one side. It doesn't yield an efficient solution.

Algorithm

The illustration below uses the following array: [-3, 2, -1, 5, 7, 3, -6, 8, 4], and depicts how a possible algorithm would move all the negative elements to one side of the array efficiently.

Code

The code snippet below provides the algorithm used in the illustration above. A single array traversal is performed, and the index of the array's first positive element is stored throughout. If an element is positive, the traversal continues, but if it is negative, it's swapped with the array's first positive element.

Note: To run the following code, provide input for the array in the form of just integers separated with a space (without commas or brackets).

For example, enter [-3, 5, 1, -6, 4] as: $\text{-}3\;5\;1\;\text{-}6\;4$

Complexity

The algorithm operates with the following properties:

Explanation

• Lines 1–10: These lines contain the function shift_negatives() that takes the original array, arr, and shifts its negative elements to one side.
• Line 2: We use the first_positive function to store the index of the array's first positive element
• Lines 3–9: A single traversal of the array is performed, in which:
• Lines 4–9: If the current element is negative, then it's swapped with the array's first positive element (whose index is stored in first_positive. If the current element is positive, we move to the next element.
• Line 10: The modified array arr is returned.
• Lines 12–14: These cater to taking the user's input for the array.
• Lines 16–17: The modified array is created by calling the function, and is then printed.