Minimum insertions to sort an array

link 0

Given an array of integer numbers, we need to sort this array in a minimum number of steps where in one step we can insert any array element from its position to any other position.
Examples:

Input  : arr[] = [2, 3, 5, 1, 4, 7, 6]
Output : 3
We can sort above array in 3 insertion 
steps as shown below,
1 before array value 2
4 before array value 5
6 before array value 7

Input : arr[] = {4, 6, 5, 1}
Output : 2

We can solve this problem using dynamic programming. The main thing to observe is that moving an element doesn’t change the relative order of elements other than the element which is being moved. Now consider longest increasing subsequenc (LIS) in which equal element are also taken as part of the increasing sequence, now if keep the element of this increasing sequence as it is and move all other elements then it will take the least number of steps because we have taken longest subsequence which does not need to be moved. Finally, the answer will be the size of the array minus the size of the longest increasing subsequence.
As LIS problem can be solved in O(N^2) with O(N) extra space using Dynamic Programming.

Below is C++ implementation of above idea.

// C++ program to get minimum number of insertion
// steps to sort an array
#include <bits/stdc++.h>
using namespace std;
//  method returns min steps of insertion we need
// to perform to sort array 'arr'
int minInsertionStepToSortArray(int arr[], int N)
{
    // lis[i] is going to store length of lis
    // that ends with i.
    int lis[N];
    /* Initialize lis values for all indexes */
    for (int i = 0; i < N; i++)
        lis[i] = 1;
    /* Compute optimized lis values in bottom up manner */
    for (int i = 1; i < N; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] >= arr[j] && lis[i] < lis[j] + 1)
                lis[i] = lis[j] + 1;
    /* The overall LIS must end with of of the array
       elements. Pick maximum of all lis values */
    int max = 0;
    for (int i = 0; i < N; i++)
        if (max < lis[i])
            max = lis[i];
    // return size of array minus length of LIS
    // as final result
    return (N - max);
}
// Driver code to test above methods
int main()
{
    int arr[] = {2, 3, 5, 1, 4, 7, 6};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << minInsertionStepToSortArray(arr, N);
    return 0;
}

Output:

3

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/minimum-insertions-sort-array/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar