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 to test above methods
function minInsertionStepToSortArray ( arr , N ) { let lis = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { lis [ i ] = 1 ; } for ( let i = 1 ; i < N ; i ++ ) { for ( let j = 0 ; j < i ; j ++ ) { if ( arr [ i ] >= arr [ j ] && lis [ i ] < lis [ j ] + 1 ) { lis [ i ] = lis [ j ] + 1 ; } } } let max = 0 ; for ( let i = 0 ; i < N ; i ++ ) { if ( max < lis [ i ] ) { max = lis [ i ] ; } } return ( N - max ) ; } let arr = new Array ( 2 , 3 , 5 , 1 , 4 , 7 , 6 ) ; let N = arr . length ; document . write ( minInsertionStepToSortArray ( arr , N ) ) ;