Rearrange array into alternate positive and negative numbers

Given an array containing both positive and negative integers, write code to rearrange the elements so that positive and negative numbers comes alternately.

If positive (or negative) integers is not equal in number then extra positive (or negative) numbers should come at the end of array. For example:

Input : {1, 2, -2, -5, 6, 7, -8}
Output: {1, -2, 2, -5, 6, -8, 7}
Input : {-1, 2, 3, -5, -6, -7, -8}
Output: {-1, 2, -5, 3, -6, -7, -8}

Method-1: Using shift and Swap

At each position, keep a note of what is required (whether a +ve number should come at that position or a negative number should come at that position). For each position we will do the following

• Check if the number required at that position is +ve or -ve
• If a +ve number is required at a position and there is already a +ve number (or vice-versa) then there is no problem, and we move forward.
• If a +ve number is required, but the number at that position is -ve then we have to find the first +ve number after that position (move forward till we get a +ve number) and put that number at this position by shifting all the numbers in between forward by one step each.

Below is the code for same

#include <iostream>
using namespace std;
// Shift all elements from 'fromIdx' till 'toIdx-1' one position forward and
// move element at 'toIdx' position at 'fromIdx'
// If array is 1, 2, 3, 4, 5  and fromIdx=1, toIdx=3 then this function will
// change the array to 1, 4, 2, 3, 5.
void shiftAndSwap(int *a, int fromIdx, int toIdx)
{
    int temp = a[toIdx];
    for(int j = toIdx; j > fromIdx; j--) {
        a[j] = a[j-1];
    }
    a[fromIdx] = temp;
}
void arrange(int* a, int n)
{
    if(n<1){ return; }
    // Keep a check of what type of number is expected.
    // If first element is +ve, then the next expected element is negative
    // and vice-versa.
    int positive = false;
    if( a[0] < 0) {
        positive = true;
    }
    int fromIdx = 1;
    for( int i = 1; i < n; i++)
    {
        // If we are expecting +ve and we have -ve number then keep moving forward
        // till we get a +ve number. When we get the first +ve number, we will have to move it
        // to fromIdx and shift all others (all -ve) one step forward.
        if(positive)
        {
            if(a[i] >= 0)
            {
                // If we expected +ve and current no is also +ve
                if(fromIdx != i)
                {
                    shiftAndSwap(a, fromIdx, i);
                    i = fromIdx; // We need to move back because we have skipped all -ve numbers
                }
                positive = false;
                fromIdx = i + 1;
            }
        }
        else
        { // negative
            if(a[i] < 0)
            {
                if( fromIdx != i)
                {
                    shiftAndSwap(a, fromIdx, i);
                    i = fromIdx; // We need to move back because we have skipped all +ve numbers
                }
                positive = true;
                fromIdx = i + 1;
            }
        }
    }
}

The good thing about above code is that it maintains the order in which element are present in the original array.

But it is an O(n²) time algorithm.

Method-2: Using Partition Logic

In this method we first separate the positive and negative numbers (by bringing all positive numbers on one side of the array and all negative numbers on another side). It can be thought of as partitioning in QuickSort algorithm with pivot=0.

Once all the negative numbers are brought at the start of the array, start from the first negative number and first positive number, and swap every alternate negative number with next positive number.

Code:

/** Put positive elements at even position and negative elements at odd positions
 */
void arrange(int *arr, int n)
{
    // Partition logic of QuickSort.
    // Bring all -ve number at start.
    int low = 0, high = n-1;
    while(low<high)
    {
        while(arr[low] < 0) low++;
        while(arr[high] > 0) high--;
        if(low<high)
            swap(arr, low, high);
    }
    // At this point low will be pointint to the first positive number in the array.
    // If there are no jpositive numbers in array, then low will be out of bond
    if(low>=n)
       return;
    // First indexes of positive and negative numbers will be as below
    int positive = low, negative = 0;
    // swap every alternate negative number with next positive number
    while (positive < n && negative < positive && arr[negative] < 0)
    {
        swap(arr, positive, negative);
        positive++;
        negative += 2;
    }
}

This is O(n) time, Constant extra space algorithm. But it will not maintain the order of positive and negative numbers in the original list.