Search

# Rearrange positive and negative numbers alternatively

Given an integer array, rearrange it such that it contains positive and negative numbers at alternate positions. If the array contains more positive or negative elements, move them to the end of the array.

Example:

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

The idea is to use 0 as a pivot element and make one pass of the partition process. The resultant array will contain all positive integers to the end of the array and all negative integers at the beginning. Then swap alternate negative elements from the next available positive element until the end of the array is reached, or all negative or positive integers are exhausted.

Solution:

```int partition(int A[])
{
int j = 0;
int pivot = 0;
for (int i = 0; i < A.length; i++)
{
if (A[i] < pivot)
{
swap(A[i], A[j]);
j++;
}
}
return j;
}

int rearrange(int A[], int size)
{
int positive = partition(A, size);
for (int negative = 0; (positive < size && negative < positive);   positive++, negative += 2)
{
swap(A[negative], A[positive]);
}
}```