Rearrange array in alternating positive & negative items with O(1) extra space, while keeping the order of the elements maintained.

[Tarun Jha]

The idea is to process array from left to right. While processing, find the first out of place element in the remaining unprocessed array. An element is out of place if it is negative and at odd index, or it is positive and at even index. Once we find an out of place element, we find the first element after it with opposite sign. We right rotate the sub-array between these two elements (including these two).

/* C++ program to rearrange positive and negative integers in alternate
fashion while keeping the order of positive and negative numbers. */
#include
#include
using namespace std;

void printArray(int arr[], int n);

// Utility function to right rotate all elements between [outofplace, cur]
void rightrotate(int arr[], int n, int outofplace, int cur)
{
char tmp = arr[cur];
for (int i = cur; i > outofplace; i--)
arr[i] = arr[i-1];
arr[outofplace] = tmp;
}

void rearrange(int arr[], int n)
{
int outofplace = -1;

for (int index = 0; index < n; index ++)
{
    if (outofplace >= 0)
    {
        // find the item which must be moved into the out-of-place
        // entry if out-of-place entry is positive and current
        // entry is negative OR if out-of-place entry is negative
        // and current entry is negative then right rotate
        //
        // \[...-3, -4, -5, 6...\] -->   \[...6, -3, -4, -5...\]
        //      ^                          ^
        //      |                          |
        //     outofplace      -->      outofplace
        //
        if (((arr\[index\] >= 0) && (arr\[outofplace\] < 0))
            || ((arr\[index\] < 0) && (arr\[outofplace\] >= 0)))
        {
            rightrotate(arr, n, outofplace, index);
            printArray(arr, n);

            // the new out-of-place entry is now 2 steps ahead
            if (index - outofplace > 2)
                outofplace = outofplace + 2;
            else
                outofplace = -1;
        }
    }


    // if no entry has been flagged out-of-place
    if (outofplace == -1)
    {
        // check if current entry is out-of-place
        if (((arr\[index\] >= 0) && (!(index & 0x01)))      // what does (index & 0x01) means ??
            || ((arr\[index\] < 0) && (index & 0x01)))
        {
            outofplace = index;
        }
    }
}

}

// A utility function to print an arra

[CPallini]

index & 0x01

It is a test on last bit of the index variable: it is 1 when index is odd (0 when index is even).