[01 Feb 2020] Move all negative elements to end in order with extra space allowed

[1] Move all negative elements to end in order with extra space allowed
Given an unsorted array of both negative and positive integer. The task is place all negative element at the end of array without changing the order of positive element and negative element.

Examples:

Input : arr[] = {1, -1, 3, 2, -7, -5, 11, 6 }
Output : 1  3  2  11  6  -1  -7  -5

Input : arr[] = {-5, 7, -3, -4, 9, 10, -1, 11}
Output : 7  9  10  11  -5  -3  -4  -1
// C++ program to Move All -ve Element At End
// Without changing order Of Array Element
#include<bits/stdc++.h>
using namespace std;

// Moves all -ve element to end of array in
// same order.
void segregateElements(int arr[], int n)
{
    // Create an empty array to store result
    int temp[n];

    // Traversal array and store +ve element in
    // temp array
    int j = 0; // index of temp
    for (int i = 0; i < n ; i++)
        if (arr[i] >= 0 )
            temp[j++] = arr[i];

    // If array contains all positive or all negative.
    if (j == n || j == 0)
        return;

    // Store -ve element in temp array
    for (int i = 0 ; i < n ; i++)
        if (arr[i] < 0)
            temp[j++] = arr[i];

    // Copy contents of temp[] to arr[]
    memcpy(arr, temp, sizeof(temp));
}

// Driver program
int main()
{
    int arr[] = {1 ,-1 ,-3 , -2, 7, 5, 11, 6 };
    int n = sizeof(arr)/sizeof(arr[0]);

    segregateElements(arr, n);

    for (int i = 0; i < n; i++)
       cout << arr[i] << " ";

    return 0;
}

Output:
1 7 5 11 6 -1 -3 -2
Time Complexity : O(n)
Auxiliary space : O(n)

# Python program to Move All -ve Element At End
# Without changing order Of Array Element
 
# Moves all -ve element to end of array in
# same order.
def segregateElements(arr, n):
    # Create an empty array to store result
    temp = [0 for k in range(n)]
 
    # Traversal array and store +ve element in
    # temp array
    j = 0 # index of temp
    for i in range(n):
        if (arr[i] >= 0 ):
            temp[j] = arr[i]
            j +=1
 
    # If array contains all positive or all negative.
    if (j == n or j == 0):
        return
 
    # Store -ve element in temp array
    for i in range(n):
        if (arr[i] < 0):
            temp[j] = arr[i]
            j +=1
 
    # Copy contents of temp[] to arr[]
    for k in range(n):
        arr[k] = temp[k]

# Driver program
arr = [1 ,-1 ,-3 , -2, 7, 5, 11, 6 ]
n = len(arr)

segregateElements(arr, n);
 
for i in range(n):
    print arr[i],

# Contributed by Afzal aka Saan

Output:
1 7 5 11 6 -1 -3 -2
Time Complexity : O(n)
Auxiliary space : O(n)