text: Rearrange positive and negative numbers with constant extra space | C ++ program to Rearrange positive and negative numbers in a array ; Function to print an array ; Function to reverse an array . An array can be reversed in O ( n ) time and O ( 1 ) space . ; Merges two subarrays of arr [ ] . First subarray is arr [ l . . m ] Second subarray is arr [ m + 1. . r ] ; Initial index of 1 st subarray ; Initial index of IInd ; arr [ i . . m ] is positive ; arr [ j . . r ] is positive reverse positive part of left sub - array ( arr [ i . . m ] ) ; reverse negative part of right sub - array ( arr [ m + 1. . j - 1 ] ) ; reverse arr [ i . . j - 1 ] ; Function to Rearrange positive and negative numbers in a array ; Same as ( l + r ) / 2 , but avoids overflow for large l and h ; Sort first and second halves ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void printArray ( int A [ ] , int size ) { for ( int i = 0 ; i < size ; i ++ ) cout << A [ i ] << " ▁ " ; cout << endl ; } void reverse ( int arr [ ] , int l , int r ) { if ( l < r ) { swap ( arr [ l ] , arr [ r ] ) ; reverse ( arr , ++ l , -- r ) ; } } void merge ( int arr [ ] , int l , int m , int r ) { int i = l ; int j = m + 1 ; while ( i <= m && arr [ i ] < 0 ) i ++ ; while ( j <= r && arr [ j ] < 0 ) j ++ ; reverse ( arr , i , m ) ; reverse ( arr , m + 1 , j - 1 ) ; reverse ( arr , i , j - 1 ) ; } void RearrangePosNeg ( int arr [ ] , int l , int r ) { if ( l < r ) { int m = l + ( r - l ) / 2 ; RearrangePosNeg ( arr , l , m ) ; RearrangePosNeg ( arr , m + 1 , r ) ; merge ( arr , l , m , r ) ; } } int main ( ) { int arr [ ] = { -12 , 11 , -13 , -5 , 6 , -7 , 5 , -3 , -6 } ; int arr_size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; RearrangePosNeg ( arr , 0 , arr_size - 1 ) ; printArray ( arr , arr_size ) ; return 0 ; }