1
$\begingroup$

So I have two arrays $d$ and $s$ with size $n \in \mathbb{N}$. Array $d$ contains the elements and array $s$ contains indices. Array $s$ contains all numbers from $0$ upto $n$ with no duplicates.

The indices in $s$ indicate where the elements in $d$ need to go. So the element at $d[q]$ needs to be at $d[s[q]]$ where $n > q \geq 0$.

The goal is to find the minimum amount of $q \in \mathbb{N}$ swaps such that the after all swaps are performed the above holds.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Does this answer your question? Sort array with minimum swaps. You can just stipulate the desired array $d[s[0]], d[s[1]], \cdots$ is in increasing order. $\endgroup$ – John L. Jan 27 '20 at 21:34
0
$\begingroup$

Hint: Assume you have four items that are in order a,b,c,d but you want them in order b, c, d, a. How many swaps do you need and why?

Then you generalise this to the whole array.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.