Rearrange positive and negative numbers alternatively in Array

In the given random array with both positive and negative integers, rearrange the array so that positive and negative are placed alternatively

Number of positive and negative numbers need not be equal. If there are more positive or more negative they appear at the end of the array.

Here, we rearrange all positives at odd indices and negatives at even indices.

Example

a) Input array: [-5, -7, 9, 11, 12, -15, 17]
Output array: [-5, 11, -15, 17, -7, 12, 9]
Rearranged positives and negatives in alternative positions and excess in the end.

b) Input array: [-4, -7, 9, 11, -16, 13, 3, -5]
Output array: [-16, 11, -4, 3, -7, 13, -5, 9]
Rearranged positives and negatives in alternative positions.

c) Input array: [1, -2, 3, 4, 5, -6, 7, 8, -9]
Output array: [-2, 3, -6, 5, -9, 8, 1, 4, 7]
Rearranged positives and negatives in alternative positions and excess in the end.

Algorithm

Time complexity: O(n)

a. We modify the array such that all positives will be in the beginning of the array and negatives at the end.
[1, -2, 3, 4, 5, -6, 7, 8, -9] → [1, 3, 4, 5, 7, 8, -2, -6, -9]

b. We maintain two pointers i and j. if array[j] > 0 we move it to the front of the array by swap with first    element. Else we move forward.

c. We initialize negative numbers start index as negative and positive as 0.

d. Increment the negative index by 1 and positive index by 2. That means we swap every alternate positive number with next negative number.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

//swap two elements based on given addresses
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

//Rearrange function  
void Rearrange(int array[], int n)
{
    int i = -1;
    //swap positive elements to the start of the array
    for (int j = 0; j < n; j++)
    {
        if (array[j] > 0)
        {
            i = i + 1;
            swap(&array[i], &array[j]);
        }
    }
    //Initialize positive_index, negative_index
    int positive_index = 0, negative_index = i + 1;
    //Increment postive by 2 and negative by 1.
    //swap elements after each increments and swap them.
    //such that alternative elements will be changed
    while (negative_index < n && negative_index > positive_index && array[negative_index] < 0)
    {
        swap(&array[negative_index], &array[positive_index]);
        positive_index = positive_index + 2;
        negative_index = negative_index + 1;
    }
}
 
 
//Main function
int main()
{
    int input_array[] = {1, -2, 3, -4, 5, -6, -7, 8, -9};
    int size = sizeof(input_array)/sizeof(int);
    cout<<"Input array is: ";
    for (int i = 0; i < size; ++i)
    {
        cout<<input_array[i]<<" ";
    }
    Rearrange(input_array, size);
    cout<<"\nOutput array is: ";
    for (int i = 0; i < size; ++i)
    {
        cout<<input_array[i]<<" ";
    }
    return 0;
}