Rearrange Positive and Negative numbers in an array

By | April 24, 2016

Rearrange Positive and Negative numbers in an array

In this post we solve the problem of rearranging positive and negative elements of an array such that they are placed alternatively in the same array.

Rearrange Positive and Negative numbers in an array Problem Statement

Given array contains both positive and negative numbers in random order. We need to rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers, they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

Rearrange Positive and Negative numbers in an array Problem Example

Let the input array be arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9}
The output should be arr[] = {9, -7, 8, -3, 5, -1, 2, 4, 6}

Rearrange Positive and Negative numbers in an array Problem Solution

The solution is to first separate positive and negative numbers using partition process of QuickSort. In the partition process, consider 0 as value of pivot element so that all negative numbers are placed before positive numbers. Once negative and positive numbers are separated, we start from the first negative number and first positive number, and swap every alternate negative number with next positive number.

Algorithm:

  1. Use the partition process of quicksort to separate positive and negative numbers.
  2. Consider 0 as the pivot point.
  3. This places all negative numbers before positive numbers.
  4. Start from the first negative number and first positive number
  5. Swap every alternate negative number with next positive number.

How to Rearrange Positive and Negative numbers in an array Problem Solution code in C++

#include <iostream>
using namespace std;

// A utility function to swap two elements
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
/* The main function that rearranges elements of given array. 
  It puts  positive elements at even indexes (0, 2, ..) and 
  negative numbers at odd indexes (1, 3, ..).*/
void rearrange(int arr[], int n)
{
    /* The following few lines are similar to partition process
     of QuickSort.  The idea is to consider 0 as pivot and
      divide the array around it.*/
    int i = -1;
    for (int j = 0; j < n; j++)
    {
        if (arr[j] < 0)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
 
    /* Now all positive numbers are at end and negative numbers
     at the beginning of array. Initialize indexes for starting
     point of positive and negative numbers to be swapped*/
    int pos = i+1, neg = 0;
 
    /* Increment the negative index by 2 and positive index by 1,
    i.e., swap every alternate negative number with next 
     positive number*/
    while (pos < n && neg < pos && arr[neg] < 0)
    {
        swap(arr[neg], arr[pos]);
        pos++;
        neg += 2;
    }
}
 

 
// A utility function to print an array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout<< arr[i]<<" ";
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    rearrange(arr, n);
    printArray(arr, n);
    return 0;
}

 Output:

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

Time Complexity:O(N)
Space Complexity:O(1)