Minimum insertions to sort an array | method returns min steps of insertion we need to perform to sort array 'arr ; lis [ i ] is going to store length of lis that ends with i . ; Initialize lis values for all indexes ; Compute optimized lis values in bottom up manner ; The overall LIS must end with of the array elements . Pick maximum of all lis values ; return size of array minus length of LIS as final result ; Driver Code
' NEW_LINE def minInsertionStepToSortArray ( arr , N ) : NEW_LINE INDENT lis = [ 0 ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT lis [ i ] = 1 NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( arr [ i ] >= arr [ j ] and lis [ i ] < lis [ j ] + 1 ) : NEW_LINE INDENT lis [ i ] = lis [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT max = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( max < lis [ i ] ) : NEW_LINE INDENT max = lis [ i ] NEW_LINE DEDENT DEDENT return ( N - max ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 3 , 5 , 1 , 4 , 7 , 6 ] NEW_LINE N = len ( arr ) NEW_LINE print ( minInsertionStepToSortArray ( arr , N ) ) NEW_LINE DEDENT