In C++, rearrange positive and negative numbers using fixed extra space

We have an array of integer type containing positive and negative numbers, assuming it is arr[] of any given size. The task is to rearrange the array such that all elements of the array are sorted using the C STL's built-in sort function and using recursion Technical coding and printing of results.

Let us look at various input and output scenarios of this −

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

Output − Rearrange positive and negative numbers, using constant extra space: -3 -1 -1 0 6 2 4.

Explanation − We are given an integer array of size 7, containing positive and negative elements. Now, we will rearrange the array so that all elements in the array are sorted within constant extra space and the end result will be -3 -1 -1 0 2 4 6.

Input − int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}

Output − Rearrange positive and negative numbers, using constant extra space: -9 -10 2 3 10 5 8 4

Explanation − We are given an integer array of size 8, containing Positive and negative elements. Now, we will rearrange the array so that all the elements in the array are sorted within constant extra space and the final result will be -9 -10 2 3 10 5 8 4.

The method used in the following program is as follows

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

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

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

• Inside the function Rearrangement(arr, size)

  • Set an integer type variable i to 0 and j to size -1 .

  • Start while(true). Inside the while, start another loop and increment i when arr[i] is less than 0 and i is less than size.

  • Start when WHILE arr[j] is greater than 0 and j is greater than 0, decrement j.

  • Check IF i is less than j, then set temp to arr[i], arr[i] to arr[j], and arr[j] to temp.

  • Otherwise, break out of the loop.

• Print the result.

Example

#include<iostream>
using namespace std;
void Rearrangement(int arr[], int size){
   int i = 0;
   int j = size - 1;
   while(true){
      while(arr[i] < 0 && i < size){
         i++;
      }
      while(arr[j] > 0 && j >= 0){
         j--;
      }
      if (i < j){
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
      }
      else{
         break;
      }
   }
}
int main(){
   int arr[] = {4, 2, -1, -1, 6, -3, 0};
   int size = sizeof(arr)/sizeof(arr[0]);
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"Rearrangement of positive and negative numbers with constant extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Output

If we run the above code, the following output will be generated

Rearrangement of positive and negative numbers with constant extra space is: -3 -1 -1 0 6 2 4

The above is the detailed content of In C++, rearrange positive and negative numbers using fixed extra space. For more information, please follow other related articles on the PHP Chinese website!