How to rearrange positive and negative numbers with constant extra space in an array using C++

In this tutorial, you will learn how to arrange positive and negative numbers within an array with constant extra space in C++. We are going to arrange the array in such a way that the negative numbers will appear on the left side of the array whereas positive on the right side of the array but the order of their sequence will be maintained. There are many methods by which you do so, one of them is given below.

Method for rearranging positive and negative numbers with constant extra space in an array in C++

  1. Run the loop from 0 to size of array-1
  2. Check the element at a position is +ve.
  3. If the number is positive do nothing
  4. If negative then shift all the numbers from the first positive number in an array to right.

Program: rearrange positive and negative numbers with constant extra space in an array

The following code shows how to rearrange the array by the method discussed above –

#include <iostream>
using namespace std;
int main()
{
    int arr[] = { -20,5,7,6,-12,2,1,-6,-9,9};
    int i, j, f, k;
    for (i = 0; i < 10; i++)
    {
        f = arr[i];
        if (f > 0)
            continue;
        else 
        {
            j = i - 1;
            while (j >= 0 && arr[j] > 0) 
            {
                arr[j + 1] = arr[j];
                j = j - 1;
            }

                        arr[j + 1] = f;
        }
    }
    for (i = 0; i < 10; i++)
        cout << arr[i]<<" ";
}

Output:-

-20 -12 -6 -9 5 7 6 2 1 9

Conclusion

There are many more methods to solve this problem. The above method used is a modified insertion sort. You can also use various other methods also like optimized merge sort and so on.

 

Leave a Reply

Your email address will not be published. Required fields are marked *