top of page
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]);
  }
}


53 views0 comments

Recent Posts

See All

Smallest String With A Given Numeric Value

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

Comments


bottom of page