Algorithm to sort two-dimensional array by swapping

Question

For one-dimensional arrays, sorting through swapping can be achieved easily by using Bubble sort, for example:

5 4 9 8 7 1 6 3 2 10

will require 25 swaps to output

1 2 3 4 5 6 7 8 9 10

---

In a two-dimensional array, however, we have something like this.

4 2 3
1 8 5
7 9 6

Items can be swapped vertically and horizontally, but not diagonally:

• Swap 4 and 1
• Swap 8 and 5
• Swap 8 and 6
• Swap 9 and 8

This becomes the sorted array:

1 2 3
4 5 6
7 8 9

I'm looking for an algorithm that can achieve this efficiently (minimizing the number of swaps). This problem may be similar to the 15 puzzle, though it is much simpler because every item can swap with an adjacent item and not just with the empty tile.

Answer 1

In a one-dimensional array, not only does bubble-sort only ever swap adjacent elements, but it also only ever compares adjacent elements.

Nothing analogous really works for a two-dimensional array, since you'd have no way to detect that

1 2 4
3 5 6
7 8 9

is out of order (since you can't directly compare the non-adjacent 3 and 4).

If we say that you can examine and compare arbitrary elements, but that the only way to update an element is to swap it with one of its neighbors, then the best approach is to start by completely figuring out where each element needs to end up (e.g., by copying the elements over to a regular array and applying a standard sorting algorithm), and only then performing the necessary swaps to move the elements to their destinations.