Minimum steps to sort array [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Computer Science Stack Exchange.

Closed 5 months ago.

Improve this question

Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need to be sorted. Let $array_i$, $array_j$ and $array_k$ be the values at those indices and now you make a right shift to it, that is $new$ $array_i$= $old$ $array_j$ and $new$ $array_j$= $ old$ $array_k$ and $new$ $array_k$=$old$ $array_i$. Find the minimum number of operations required to sort the array or if is impossible how to determine it.

Example : Consider $array= [3,1,2]$; consider indices $(1,3,2)$ in the given order after applying one operation it is $s =[1,3,2]$.

Can anybody share your approach.

Answer 1

Your operations correspond to applying a 3-cycle on the input permutation. You can reach the identity by applying 3-cycles iff the input permutation is even. Given the cycle decomposition of the input permutation, it shouldn't be hard to answer your question (though the answer is not immediate).