Rearrange the array such that it contains positive and negative numbers at alternate positions

Given an array of integers, rearrange the array such that it contains positive and negative numbers at alternate positions. If array contains more positive or negative elements, they should be moved to end of the array.

For example,

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

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

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

We can solve this problem in linear time by using partitioning logic of quicksort. The idea is to use 0 as pivot element and make one pass of partition process. The resultant array will contain all positive integers at the end of the array and all negative integers in the beginning. Then we swap alternate negative element from next available positive element till end of array is reached or all negative or positive integers are exhausted.

C++ implementation –

Output:

5 -2 9 -6 1 -8 3 -3

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1). The problem with this approach is that it changes relative order of elements.

Exercise: Implement a solution that maintains the relative order of elements.