Smart sorting

Hello everybody!

I can say it now since I gained two followers! Unfortunately it just happen that I know who those two people are and for one of them I was forced to a little bit of lobbying in order to have her following me, but nevertheless I’m obliged from now on to welcome EVERYBODY 🙂 So, HELLO!

Today I have an interesting problem which is about sorting array, the problems statement is: Given an array of n elements where each element Pi of the array is bounded to 1<=Pi<=n and given that if i!=j then Pi!=Pj and of course 1<=Pi,Pj<=n, calculated the amount of operations needed to sort the array under the condition that: The ONLY operation allowed is to move one element at time from its current position to the front or back of the array.

Return the min amount of move operation. Examples:

• 1,2,3 = 0 (already sorted)
• 2,3,1 = 1 (move 1 to front)
• 3,2,1 = 2 (move 1 to front and 3 to back)
• 4,1,2,5,3 = 2 (move 4 to back, and AFTER move 5 to back)

Well, the whole point of the problem is noticing that in order to minimize the amount of moves is required to calculated the maximum streak of consecutive elements of the array, subtracting this value from n is the solution.

In other words, removing from the array the elements that you’ll expect to move will give you the required maximum subarray. How do I found the amount of elements that I’m supposed to move? Well let’s pick a O(n+1) array and put p[d[i]] = i, where i is the index of the d[i] input element.

Now you may notice that sorting d[] will provide you with the output array after the sorting –of course…– but since we have in p[] the original index of the elements now we are able to calculate the longest subsequence of elmeents which do not need to be moved (already in position) comparing they actual relative position to the relative position in the sorted array.

Here’s the code:

#include 
#include 
#include 
using namespace std;

int main()
{
	int n,c{1},r{1};
	cin >> n;
	vector d(n);
	vector p(n+1);
	for(int i{0};i<n;i++) 	{ 		
                cin >> d[i];
		p[d[i]] = i;
	}
	sort(d.begin(),d.end());
	for(int i{1};i<n;i++) 	{ 		
                if(p[d[i]] > p[d[i-1]]){
			++c;
		}else{
			r = max( r, c );
			c = 1;
		}
	}
	cout<<n-max(r,c)<<endl;
}

The code does exactly what explained earlier. Eventually the d[] array may be completely removed if we consider the problem statement constrait that for each i!=j we have Pi!=Pj and 1<=Pi,Pj<=n, which basically means that the output array will have the form {1…n}, so:

#include 
#include 
#include 
using namespace std;

int main()
{
	int n,c{1},r{1},t;
	cin >> n;
	vector p(n+1);
	for(int i{0};i<n;i++) 	{ 		
                cin >> t;
		p[t] = i;
	}
	for(int i{2};i<=n;i++) 	{ 		
                if(p[i] > p[i-1]){
			++c;
		}else{
			r = max( r, c );
			c = 1;
		}
	}
	cout<<n-max(r,c)<<endl;
}

So we saved a little of space and improved the performance from nlogn to linear since no more sorting is required.