Rearrange positive and negative numbers with constant extra space | Java 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
class GFG { static void printArray ( int A [ ] , int size ) { for ( int i = 0 ; i < size ; i ++ ) System . out . print ( A [ i ] + " ▁ " ) ; System . out . println ( " " ) ; ; } static void reverse ( int arr [ ] , int l , int r ) { if ( l < r ) { arr = swap ( arr , l , r ) ; reverse ( arr , ++ l , -- r ) ; } } static 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 ) ; } static 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 ) ; } } static int [ ] swap ( int [ ] arr , int i , int j ) { int temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; return arr ; } public static void main ( String [ ] args ) { int arr [ ] = { - 12 , 11 , - 13 , - 5 , 6 , - 7 , 5 , - 3 , - 6 } ; int arr_size = arr . length ; RearrangePosNeg ( arr , 0 , arr_size - 1 ) ; printArray ( arr , arr_size ) ; } }