# Move all negative elements at the end of array

The problem is to move all negative elements to the end of the array while maintaining the relative order of positive elements. The goal is to rearrange the elements of the array in such a way that all negative elements come after all positive elements. The relative order of positive elements within the sorted array should be the same as in the original array.

## Example

Consider the following array:

``[1, -1, 3, 2, -7, -5, 11, 6]``

After rearranging, the array becomes:

``[1, 6, 3, 2, 11, -5, -7, -1]``

All negative elements have been moved to the end of the array while preserving the order of positive elements.

## Idea to Solve the Problem

To solve this problem, we can use a two-pointer approach. We maintain two pointers, `i` and `j`, where `i` starts from the beginning of the array and `j` starts from the end of the array. We move `i` from left to right and `j` from right to left. At each step, we check if the element at `i` is negative and the element at `j` is positive. If so, we swap these elements to move the negative element to the end of the array. We repeat this process until `i` becomes greater than or equal to `j`.

## Algorithm

1. Initialize two pointers, `i` and `j`, where `i` starts from the beginning of the array (index 0) and `j` starts from the end of the array (index `n - 1`, where `n` is the size of the array).
2. Repeat the following steps until `i` becomes greater than or equal to `j`: a. If the element at index `i` is negative and the element at index `j` is positive, swap these elements. b. If the element at index `i` is positive, increment `i`. c. If the element at index `j` is negative, decrement `j`.
3. After the loop, all negative elements will be moved to the end of the array.

## Pseudocode

``````function moveNegative(arr):
i = 0
j = size of arr - 1

while i < j:
if arr[i] < 0 and arr[j] >= 0:
swap arr[i] with arr[j]
increment i
decrement j
else if arr[i] >= 0:
increment i
else:
decrement j

end function``````

## Time Complexity

• The above algorithm has a time complexity of O(N), where N is the number of elements in the array. This is because we traverse the array once and perform constant-time swap or increment/decrement operations for each element.
• Therefore, the algorithm is efficient for moving negative elements to the end of an array with a large number of elements.

## Resultant Output Explanation

The given program implements the algorithm to move negative elements to the end of the array while preserving the relative order of positive elements.

In the provided output, the program displays the initial array elements before rearranging and the array elements after rearranging. The algorithm moves all negative elements to the end of the array while maintaining the order of positive elements.

The output shows the sorted array, where all negative elements come after all positive elements, and the relative order of positive elements within the array remains the same as in the original array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.