Whats is the proper name of this problem and or solution algorithm?

I have a 2D array that holds unique integers - this represents a physical container with rows/columns - in each position there is a vial.

I know the integers that should be in the array and where they should be located.

My array however is shuffled with potentially many/all unique integers in the wrong positions.

I now need to sort the array - however this maps to a physical process and therefore I really want to reduce the number of sort steps involved due to potential human error.

Is this just a plain sort? or is there a more specific name for this scenario? Is there well known solutions?

My colleague has suggested just creating a list of swap [1][1]开发者_运维百科 with [2][1] type instructions, which seems reasonable however I can't quite get my head around if the order of swaps is important.

All assistance grateful.

---

If you really can tell, just by looking at the vial, where it belongs, the shortest way is to take the first vial that is in the wrong place out, then put it where it belongs, take whatever was there, put it to its proper place, etc., until you happen to get the vial that belongs where you originally made a "hole". Then repeat.

Since you take out each vial at most once, and only if it is in the wrong place, I think that this is optimal with respect to physical motion.

---

Sorting algorithms are analysed by the number of comparisons and the number of swaps required. Since for a human operator the cost of a swap is much higher than the cost of a comparison, you want a 2D sort that minimizes the number of swaps required.

---

"I can't quite get my head around if the order of swaps is important."

I general yes, it is. For a simple example consider the starting list of 3 elements, X Y Z.

The result of "swap 1 with 2, then 2 with 3" is Y Z X.

The result of "swap 2 with 3, then 1 with 2" is Z X Y.

The list of swaps you come up with will probably be (at most) 1 for each element that is out of place, and will swap that element with whatever is in its correct place. So for example you might swap [0][0] with wherever it belongs. Unless the place where it belongs happens to contain the element that belongs in [0][0], then your next swap could be, again [0][0] with wherever that belongs. So certainly the order of swaps is important - this second swap is only correct because the first swap has already happened, and moved some particular element into [0][0].

If two consecutive swaps are disjoint, though, then you can reverse their order: (1 2)(3 4) is equivalent to (3 4)(1 2), where (x y) is a mathematical notation for "swap x with y".

It's a theorem that any permutation can be written as a set of disjoint cycles. This decomposition into cycles is unique apart from which element in your cycle you choose to list first, and the order the cycles are listed, both of which are irrelevant to the result. The notation (1 2 3) means "move 1 to 2, 2 to 3, and 3 to 1", and is a 3-cycle. It's exactly the same as (2 3 1), but different from (1 3 2).

Depending how your human operative works, it might well be more efficient for them to carry out an n-cycle rather than an equivalent n swaps. So once you know how to sort your array (that is, you know what permutation must be performed on it to get it into order), it may be that the best thing to do is to generate that decomposition.