Rearrange positive and negative numbers with constant extra space | 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
def printArray ( A , size ) : NEW_LINE INDENT for i in range ( 0 , size ) : NEW_LINE INDENT print ( A [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT def reverse ( arr , l , r ) : NEW_LINE INDENT if l < r : NEW_LINE INDENT arr [ l ] , arr [ r ] = arr [ r ] , arr [ l ] NEW_LINE l , r = l + 1 , r - 1 NEW_LINE reverse ( arr , l , r ) NEW_LINE DEDENT DEDENT def merge ( arr , l , m , r ) : NEW_LINE INDENT i = l NEW_LINE j = m + 1 NEW_LINE while i <= m and arr [ i ] < 0 : NEW_LINE INDENT i += 1 NEW_LINE DEDENT while j <= r and arr [ j ] < 0 : NEW_LINE INDENT j += 1 NEW_LINE DEDENT reverse ( arr , i , m ) NEW_LINE reverse ( arr , m + 1 , j - 1 ) NEW_LINE reverse ( arr , i , j - 1 ) NEW_LINE DEDENT def RearrangePosNeg ( arr , l , r ) : NEW_LINE INDENT if l < r : NEW_LINE INDENT m = l + ( r - l ) // 2 NEW_LINE RearrangePosNeg ( arr , l , m ) NEW_LINE RearrangePosNeg ( arr , m + 1 , r ) NEW_LINE merge ( arr , l , m , r ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ - 12 , 11 , - 13 , - 5 , 6 , - 7 , 5 , - 3 , - 6 ] NEW_LINE arr_size = len ( arr ) NEW_LINE RearrangePosNeg ( arr , 0 , arr_size - 1 ) NEW_LINE printArray ( arr , arr_size ) NEW_LINE DEDENT