Separate positive and negative numbers in array

Input: arr = {1,-3,9,-5,-2,6,4,-7}

Output: {-3,-5,-2,-7,9,6,4,1} when order is not maintained.

Output: {-3,-5,-2,-7,9,6,4,1} when order is maintained.

Explanation: The input contains an unsorted array with multiple elements both positive and negative. The output is the rearrangement of the positive and negative elements in the array.

There are two approaches to solve it:

Case 1: Rearrange the array without maintaining the order.
Case 2: Rearrange the array with the order maintained.

# Separate/Rearrange the array without maintaining the order

# Algorithm

1. Pass the given array to the function to rearrange the array elements.
2. Iterate through the array and find the negative element in the array and replace it with the first encountered positive element.
3. Then swap the elements and continue the process for all the negative elements.
4. The rearranged array is displayed on the console.

Code:

#include <iostream>
using namespace std;

void rearrangePositiveNegativeElements(int arr[], int size){
    int i, j = 0;
    for(i = 0; i < size; i++){
        if(arr[i] < 0){
            if(i != j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            j++;
        }
    }
}

int main(){
    int numElements, i;
    cout << "Enter the number of elements: " << endl;
    cin >> numElements;
    int myArray[numElements];
    cout << "Enter the array elements: " << endl;
    for(i = 0; i < numElements; i++){
        cin >> myArray[i];
    }

    cout << "Original array is: " << endl;
    for(i = 0; i < numElements; i++){
        cout << myArray[i] << " ";
    }
    cout << endl;

    rearrangePositiveNegativeElements(myArray, numElements);

    cout << "Rearranged array is: " << endl;
    for(i = 0; i < numElements; i++){
        cout << myArray[i] << " ";
    }
    cout << endl;
    return 0;
}

Output:

Enter the number of elements:
8

Enter the array elements:
1
-3
9
-5
-2
6
4
-7

Original array is:

1 -3 9 -5 -2 6 4 -7

Rearranged array is:

-3 -5 -2 -7 9 6 4 1

Time Complexity: O(N)

# Rearrange the array with the order maintained

# Algorithm

1. Pass the given array to the function to rearrange the array elements.
2. Iterate through the array and find the negative element in the array and insert it within the array in the sequence of 0 to n-1 by shifting the positive element one position to the right.
3. If the encountered element is positive, then skip it and move on to the next element. 
4. The rearranged array is displayed on the console.

Code:

#include <iostream>
using namespace std;

void rearrangePositiveNegativeElements(int arr[], int size){
    int i, temp, j;
    for(i = 1; i < size; i++){
        temp = arr[i];
        if (temp > 0)
            continue;

        j = i - 1;

        while(j >=0 && arr[j] > 0){
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = temp;
    }
}

int main(){
    int numElements, i;
    cout << "Enter the number of elements: "<< endl;
    cin >> numElements;
    int myArray[numElements];
    cout << "Enter the array elements: " << endl;
    for(i = 0; i < numElements; i++){
        cin >> myArray[i];
    }

    cout << "Original array is: " << endl;
    for(i = 0; i < numElements; i++){
        cout << myArray[i] << " ";
    }
    cout << endl;

    rearrangePositiveNegativeElements(myArray, numElements);

    cout << "Rearranged array is: " << endl;
    for(i = 0; i < numElements; i++){
        cout << myArray[i] << " ";
    }
    cout << endl;
    return 0;
}

Output:

Enter the number of elements:
8

Enter the array elements:
1
-3
9
-5
-2
6
4
-7

Original array is:

1 -3 9 -5 -2 6 4 -7

Rearranged array is:

-3 -5 -2 -7 1 9 6 4

Time Complexity: O(N^2)

# Optimized Algorithm for Case 2

1. Pass the given array to the function to rearrange the array elements.
2. Iterate through the array and sort the elements using merge sort.
3. While positioning the elements in the subarray place first the negative elements of both the right and left subarrays and then the positive elements using additional condition in the algorithm. 
4. The rearranged array is displayed on the console.

Code:

#include <iostream>

using namespace std;

void modified_merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int left_size = mid - left + 1;
    int right_size = right - mid;
    int left_arr[left_size], right_arr[right_size];

    for (i = 0; i < left_size; i++)
    {
        left_arr[i] = arr[left + i];
    }

    for (j = 0; j < right_size; j++)
    {
        right_arr[j] = arr[mid + 1 + j];
    }

    i = 0;
    j = 0;
    k = left;

    while (i < left_size && left_arr[i] < 0)
    {
        arr[k++] = left_arr[i++];
    }

    while (j < right_size && right_arr[j] < 0)
    {
        arr[k++] = right_arr[j++];
    }

    while (i < left_size)
    {
        arr[k++] = left_arr[i++];
    }

    while (j < right_size)
    {
        arr[k++] = right_arr[j++];
    }
}

void rearrange_array(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        rearrange_array(arr, left, mid);
        rearrange_array(arr, mid + 1, right);
        modified_merge(arr, left, mid, right);
    }
}

int main()
{
    int arr[] = {1, -3, 9, -5, -2, 6, 4, -7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array is: " << endl;

    for (int i = 0; i < arr_size; i++)
    {
        cout << arr[i] << " ";
    }

    cout << endl;

    rearrange_array(arr, 0, arr_size - 1);

    cout << "Rearranged array is: " << endl;

    for (int i = 0; i < arr_size; i++)
    {
        cout << arr[i] << " ";
    }

    cout << endl;

    return 0;
}

Output:

Original array is:

1 -3 9 -5 -2 6 4 -7

Rearranged array is:

-3 -5 -2 -7 1 9 6 4

Time Complexity: O(NlogN)

This way with more practices of data structures and algorithms we can approach towards efficient source codes of any particular programs.