public void rearrange(int input[]) {

        for (int i = 0; i < input.length; i++) {
            if (i % 2 == 0 && input[i] >= 0) {
                int indexOfNextNegative = findNext(input, i + 1, false);
                if (indexOfNextNegative == -1) {
                    return;
                } else {
                    rightRotate(input, i, indexOfNextNegative);
                }
            } else if (i % 2 != 0 && input[i] < 0) {
                int indexOfNextPositive = findNext(input, i + 1, true);
                if (indexOfNextPositive == -1) {
                    return;
                } else {
                    rightRotate(input, i, indexOfNextPositive);
                }
            }
        }
    }
Date 12/31/2015
@author Tushar Roy

Given an array of positive and negative integers arrange them alternatively maintaining initial order.
If there are more +ve or -ve integer then push them to the end together.

Time complexity is O(n)
Space complexity is O(1)

http://www.geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/
src/com/interview/array/PositiveAndNegativeNumberAlternativelyMaintainingOrder.java