Algorithm/Insights
Before looking at the algorithm, let's first define the right-rotate rotation operation on a given array. If the given array is {-1,3,4,5} then the right-rotate operation on this array would result in array {5,-1,3,4}. Here each element except the last element is right-shifted by one position and the last element is placed at the first position.
Now let's look at the algorithm for re-arranging elements. The steps of the algorithm are -
1. Traverse the array from index 0 to last index.
2. If at any 'index', we find that the element a[index] is not at its right position(if positive element is not at even index and vice versa), then we find out the next element say at index 'nextOpposite' which is of opposite sign to a[index]. Once we find this 'nextOpposite' index we do a right-rotate operation on sub-array ['index' to 'nextOpposite'] including both extremes. The right-rotate operation puts the element a['nextOpposite'] at position 'index' and maintains the order of remaining elements. If we do not find any opposite signed element, then there are extra elements remaining of either positive / negative sign and we break out of the loop since the algorithm is complete.
Let's look at an example to understand this algorithm.
Input: {-1,3,2,4,5,-6,7,-9}
1. array = {-1,3,2,4,5,-6,7,-9}, index = 0: -1 is not at its right position, next element of opposite sign(3) is found at index 1, right-rotate for sub-array{-1,3} is done and modified array is {3,-1,2,4,5,-6,7,-9}
2. array = {3,-1,2,4,5,-6,7,-9}, index = 1: -1 is now placed at its right position.
3. array = {3,-1,2,4,5,-6,7,-9}, index = 2: 2 is also at its right position.
4. array = {3,-1,2,4,5,-6,7,-9}, index = 3: 4 is not at its right position, next opposite signed element(-6) is at index 5. Right-rotate operation is performed on sub-array{4,5,-6} which results in modified array {3,-1,2,-6,4,5,7,-9}
5. array = {3,-1,2,-6,4,5,7,-9}, index = 4: 4 is now placed at its right position.
6. array = {3,-1,2,-6,4,5,7,-9}, index = 5: 5 is not placed at its right position, right-rotation is performed on sub-array {5,7,-9} which results in modified array {3,-1,2,-6,4,-9,5,7}.
7. All remaining elements are at their right positions.