In C++, use O(1) extra space to rearrange an array so that positive and negative items alternate

We get an array of integer type containing positive and negative numbers, say, arr[] of any given size. The task is to rearrange an array so that positive numbers are surrounded by negative numbers. If there were more positivity and Negative numbers will be sorted at the end of the array.

Let us look at different input and output situations−

Input − int arr[] = {-1, -2, -3, 1, 2, 3 }

Output − Array before sorting: -1 -2 -3 1 2 3 Rearranging an array so that positive and negative items alternate and does not require additional space is: -1 1 -2 2 -3 3.

Explanation: Given an integer array of size 6, containing positive and negative elements. Now we will rearrange the array so that all positive elements appear before negative elements without requiring extra space Surrounded by negative elements and all extra elements, -1 1 -2 2 -3 3 will be added to the end of the final array, which is the final result.

Input - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};

Output - Array before sorting: -1 -2 -3 1 2 3 5 5 -5 3 1 1 The time complexity of rearranging the array into alternating positive and negative terms without using additional space is O(1): -1 1 -2 2 -3 3 -5 5 5 3 1 1

Explanation - We are given an integer array of size 12 containing positive and negative elements. Now we will rearrange the array in such a way that all positive elements are surrounded by negative elements and add all extra elements to the end of the array i.e. -1 1 -2 2 -3 3 -5 5 5 3 1 1 will be the final result.

The method used in the following program is as follows

• Input an array of integer type and calculate the size of the array.

• Use a FOR loop to print the array before the rearrange operation is performed.

• Call the function Rearrangement(arr, size) by passing the array and array size as parameters.

• Inside function Rearrangement(arr, size)

  • Declare an integer variable 'ptr' and initialize it to -1.

  • Loop from i to 0 until i is less than size. Inside the loop, check if ptr is greater than 0, then check if arr[i] is greater than 0 and arr[ptr] is less than 0 or arr[i] is less than 0 and arr[ptr] is greater than 0, then call the function move_array(arr, size, ptr, i), and checks if i - ptr is greater than 2, then sets ptr to ptr 2. Otherwise, set ptr to -1.

  • Check if ptr is equal to -1, then check arr[i] is greater than 0 and! (i & 0x01) or (arr[i] is less than 0) and (i & 0x01), Then set ptr to i.

• Declared inside the function move_array(int arr[], int size, int ptr, int temp)

  • A character type variable named 'ch' and set it to arr[temp].

  • Loop from i to temp until i is greater than ptr. Inside the loop, set arr[i] to arr[i - 1].

  • Set arr[ptr] to ch.

Example

#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
   char ch = arr[temp];
   for(int i = temp; i > ptr; i--){
      arr[i] = arr[i - 1];
   }
   arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
   int ptr = -1;
   for(int i = 0; i < size; i++){
      if (ptr >= 0){
         if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
            move_array(arr, size, ptr, i);
            if(i - ptr >= 2){
               ptr = ptr + 2;
            }
            else{
               ptr = -1;
            }
         }
      }
      if(ptr == -1){
         if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
            ptr = i;
         }
      }
   }
}
int main(){
   //input an array
   int arr[] = {-1, -2, -3, 1, 2, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Output

If we run the above code it will generate the following output

Array before Arrangement: -1 -2 -3 1 2 3
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3

The above is the detailed content of In C++, use O(1) extra space to rearrange an array so that positive and negative items alternate. For more information, please follow other related articles on the PHP Chinese website!