determine if the array could be sorted rotating 3 consecutive array elements?

Question

I have a permutation of a sequence of natural numbers incrementing from 1 as an array. How can I determine whether the array can be sorted using rotation of 3 consecutive elements?

I have implemented an algorithm in which basically I'm comparing the indices of the array with the element at that index in the array. If they are not equal then I call the function choose_indices() which first finds the element to be swap at the right position in the array and after finding it, selects the 3 consecutive elements including the number to be swapped and rotates them. After performing n-1 rotations for an array of size n, the array is sorted. This implementation returns true if an array can be sorted using 3 consecutive element rotation but timeouts for an array if the array can't be sorted using this method.

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
int n;
void rotate(vector<int> &arr,int end,int mid,int start)
{
    int temp=arr[start];
    arr[start]=arr[end];
    arr[end]=arr[mid];
    arr[mid]=temp;
}
void choose_indices(vector<int> &arr,int s,int q)
{
    for(int l=q;l<n;l++)
    {
        if(arr[l]==s)
        {
            if(l-q>=2)
            {
                rotate(arr,l,l-1,l-2);
                break;
            }
            else
            {
                rotate(arr,l+1,l,l-1);
                break;
            }
        }
    }
}
int main()
{
    vector<int> arr;
    int q,count=0;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>n;
        count=0;
        for(int i=0,p;i<n;i++)
        {
            cin>>p;
            arr.push_back(p);
        }
        for(int j=0,k=1;j<n && k<n; )
        {
            if(arr[j]!=k)
            {
                choose_indices(arr,k,j);
                if(arr[j]==k)
                {
                    j++;
                    k++;
                    count++;
                }
            }
            else
            {
                j++;
                k++;
                count++;
            }
        }
        if(count==n-1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
           cout<<"NO"<<endl;
        }
        arr.clear();
    }
}

Sample Input: 1 2 3 5 4

For this input, my code gives runtime error. How can I find if the array given cannot be sorted using the rotation of 3 consecutive elements?

1 5 1 2 3 5 4 is not "a permutation of a sequence of natural numbers". — Igor Tandetnik
– Igor Tandetnik, Commented Jun 16, 2018 at 13:47
If you only need to determine whether an array could be sorted this way (and not actually sort it), that should be simple. Count the number of transpositions (pairs of elements that are in the wrong order relative to each other) - if it's even, the array can be sorted, if it's odd it cannot be. That's because every rotation adds or removes two transpositions (assuming no equal elements are present, as would be the case if the array is in fact a permutation of a sequence of natural numbers). At least, I think so, off the top of my head. — Igor Tandetnik
– Igor Tandetnik, Commented Jun 16, 2018 at 13:54
1 represents the number of queries and 5 is the size of the array. — Shantanu
– Shantanu, Commented Jun 17, 2018 at 6:25

Sumeet · Accepted Answer · 2018-06-16 15:18:57Z

2

Rotating 3 adjacent elements will always cancel 2 inversions if present or it will introduce 2 inversions.

Consider this:

1 2 3 5 4

Has only 1 inversion, no matter how many times you rotate , you can never cancel that inversion without introducing other inversions as you will be always rotating 3 consecutive elements.

So just count the number of inversions and if its odd then the answer is NO, otherwise YES. There are efficient algorithms out there to count the number of inversions(like merge sort).

answered Jun 16, 2018 at 15:18

Sumeet

8,3645 gold badges27 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Shantanu Over a year ago

That is what i thought at first but the problem is that i have to devise same algorithm that does both these jobs.

Sumeet Over a year ago

What do u mean both jobs?

Shantanu Over a year ago

meaning that if the array could be sorted, then the output shoud be yes but if it can't, then it should return no.

Sumeet Over a year ago

You don't need to actually do any rotations and see if sorting is possible

Sumeet Over a year ago

Just count the number of inversions and get the Boolean answer. What's the big deal?

Shantanu · Accepted Answer · 2018-06-18 18:00:44Z

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
int n;
void rotate(vector<int> &arr,int end,int mid,int start)
{
    int temp=arr[start];
    arr[start]=arr[end];
    arr[end]=arr[mid];
    arr[mid]=temp;
}
void choose_indices(vector<int> &arr,int s,int q)
{
    for(int l=q;l<n;l++)
    {
        if(arr[l]==s)
        {
            if(l-q>=2)
            {
                rotate(arr,l,l-1,l-2);
                break;
            }
            else
            {
                rotate(arr,l+1,l,l-1);
                break;
            }
        }
    }
}
int main()
{
    vector<int> arr;
    int q,count=0;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>n;
        count=0;
        for(int i=0,p;i<n;i++)
        {
            cin>>p;
            arr.push_back(p);
        }
        //Counting the number of inversion in the array
        int ctiv=0;
        for(int r=0;r<n;r++)
        {
            for(int s=r+1;s<n;s++)
            {
                if(arr[r]>arr[s] && r<s)
                {
                    ctiv++;
                }
            }
        }
        if(ctiv%2!=0)
        {
            cout<<"NO"<<endl;
        }
        else 
        {
            for(int j=0,k=1;j<n && k<n; )
            {
                if(arr[j]!=k)
                {
                    choose_indices(arr,k,j);
                    if(arr[j]==k)
                    {
                        j++;
                        k++;
                        count++;
                    }
                }
                else
                {
                    j++;
                    k++;
                    count++;
                }
            }
            if(count==n-1)
            {
                cout<<"YES"<<endl;
            }
            arr.clear();
        }
    }
}

This is the algorithm i designed which finds if the given algorithm can be sorted and if it can be sorted, it sorts the given array by performing the necessary 3 consecutive rotations.

Collectives™ on Stack Overflow

determine if the array could be sorted rotating 3 consecutive array elements?

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related