Sort an array with swapping only with a special element is allowed | n is total number of elements . index is index of 999 or space . k is number of elements yet to be sorted . ; Print the sorted array when loop reaches the base case ; Else if k > 0 and space is at 0 th index swap each number with space and store index at second last index ; If space is neither start of array nor last element of array and element before it greater than / the element next to space ; First swap space and element next to space in case of { 3 , 999 , 2 } make it { 3 , 2 , 999 } ; Than swap space and greater element convert { 3 , 2 , 999 } to { 999 , 2 , 3 } ; Wrapper over sortRec . ; Find index of space ( or 999 ) ; Invalid input ; Driver Code
def sortRec ( arr , index , k , n ) : NEW_LINE INDENT if ( k == 0 ) : NEW_LINE INDENT for i in range ( 1 , n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( 999 , end = " " ) NEW_LINE DEDENT elif ( k > 0 and index == 0 ) : NEW_LINE INDENT index = n - 2 NEW_LINE for i in range ( 1 , index + 1 ) : NEW_LINE INDENT arr [ i - 1 ] = arr [ i ] NEW_LINE DEDENT arr [ index ] = 999 NEW_LINE DEDENT if ( index - 1 >= 0 and index + 1 < n and arr [ index - 1 ] > arr [ index + 1 ] ) : NEW_LINE INDENT arr [ index ] , arr [ index + 1 ] = arr [ index + 1 ] , arr [ index ] NEW_LINE arr [ index - 1 ] , arr [ index + 1 ] = arr [ index + 1 ] , arr [ index - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT if ( index - 1 < 0 ) : NEW_LINE INDENT return NEW_LINE DEDENT arr [ index ] , arr [ index - 1 ] = arr [ index - 1 ] , arr [ index ] NEW_LINE DEDENT sortRec ( arr , index - 1 , k - 1 , n ) NEW_LINE DEDENT def sort ( arr , n ) : NEW_LINE INDENT index = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] == 999 ) : NEW_LINE INDENT index = i NEW_LINE break NEW_LINE DEDENT DEDENT if ( index == - 1 ) : NEW_LINE INDENT return NEW_LINE DEDENT sortRec ( arr , index , n , n ) NEW_LINE DEDENT arr = [ 3 , 2 , 999 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE sort ( arr , n ) NEW_LINE