Program to Rearrange Positive and Negative Number Alternatively

  • Write a program to rearrange alternating positive and negative numbers in O(n) time and O(1) space.
  • Algorithm to rearrange positive and negative numbers alternatively.

Given an integer array of size N containing both positive and negative numbers. we have to rearrange array elements such that positive and negative numbers are placed in alternate positions. There maybe any number of positive and negative numbers in input array.
For Example :

Input Array : -3, 5, -5, -6, 8, -9, 7, 2, -14, 10, 17
Output : -3 8 -5 7 -9 2 -6 5 -14 10 17

Let inputArray be an integer array of size N.

Algorithm to rearrange array in alternating positive and negative numbers
  • First of all we have to separate positive numbers and negative numbers using Dutch Flag Algorithm. This algorithm is similar to partition step of Quick Sort. First all negative numbers then all positive numbers.
  • Traverse inputArray and find the the index of first positive number. Let it be posIndex.
  • Initialize negIndex with index of second negative number that is 1.
  • Swap alternate negative numbers with positive numbers. Swap inputArray[negArray] and inputArray[posArray].
  • Increment posIndex (posIndex++) and set negIndex to alternate negative number(negIndex += 2;).
Time Complexity : O(n)
Space Complexity : O(1)

C program to rearrange alternate positive and negative numbers

#include <stdio.h>

void swap(int *array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

/*Seperates -ve and +ve in an array. first all -ve and then all +ve.
This approach is similar to partition step of quick sort */
void seperateNumbers(int *array, int size){
    int temp, left = 0, right = size-1;
    while(right > left){
     /* traverse from left to right till we find a +ve number */
     while(array[left] < 0)
         left++;
     /* traverse from right to left till we find a -ve numbers */
     while(array[right] > 0)
         right--;
     
     if(left < right){
            /* Swap array[left] and array[right] */
            swap(array, left, right);
        }
    }
}

void rearrangeNumbers(int *array, int size) {
    int i, j;
    
    /* Seperate -ve and +ve numbers */
    seperateNumbers(array, size);
 
    /* Find index of first +ve number */
    for(i = 0; array[i] < 0; i++);
 
    /* Now swap alternate -ve numbers with positive numbers */
    for(j = 1; (j < i) && (array[j] < 0); j += 2){
        swap(array, i, j);
        i++;
    }
    return;
}

int main(){
    int i, array[11] = {-3, 5, -5, -6, 8, -9, 7, 2, -14, 10, 17}; 
    
    rearrangeNumbers(array, 10);
    
    for(i = 0; i < 11; i++){
     printf("%d ", array[i]);
    }

    return 0;
}
Output
-3 8 -5 7 -9 2 -6 5 -14 10 17
Posted by
Labels: ,