5

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.

Improve this question
9
  • 1
    You have not defined what you mean by sorting. Why would the resulting array look like yours and why are there arbitrary constrains on it ? Commented Jan 17, 2016 at 19:07
  • 1
    @HopefullyHelpful The array is a n×n multi-dimensional array filled with n*n different numbers. Those numbers are to be sorted per row in ascending order; however, the first number of a row must be greater than the last number of the previous row (the smallest number of all will be in [0,0]). Commented Jan 17, 2016 at 19:13
  • 3
    @JCarter an algorithm that achieves the minimum number of swaps will be horribly inefficient. It's already inefficient to modify bubble-sort for this kind of purpose, but with a 2D-array the runtime will become absolutely horrible. Use a modification of a sorting-algorithm for 1D-arrays instead, that maps indices of the 2D-array to those of an equivalent 1D-array. Commented Jan 17, 2016 at 19:46
  • 1
    The third swap is swap 8 and 6, not 5 and 6. Commented Jan 17, 2016 at 20:41
  • Is this a practical problem or a puzzle ? In other words does performance play a role ? If not you can simply add everything to a normal array, sort it, break it appart again, compare distances in your 2D space and then do some graph algorithms on it to find the optimal solution. Commented Jan 17, 2016 at 22:20

2 Answers 2

Reset to default
3

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.

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

Comments

0

If you have 3 x 3 matrix, so there are 9 elements, which means 9!=362880 possible swaps. And if the matrix is 4 x 4, so 16! which is 20,922,789,888,000 possible swaps. You see the pattern. This is unfortunately an NP-Hard problem, that can't really be solved in polynomial time. So far that is like 15Puzzle. Swapping any element should have less number of steps and make it much simpler to find a solution.

However, you can try to find a solution using informed search. Define a good heuristic to represent how far is the current state from the goal state, and use that in A* search for example. That is the simplest you can do. You can always try something a little bit more complicated like Alpha-Beta pruning. As a heuristic, I can suggest the manhattan distance between each item and its target position.
For example,

4 2 3
1 8 5
7 9 6

4 is at [0][0] and it should be at 1, so the hamming distance for 4 is (1-0)+(1-0) = 2. Meaning you need at least two swaps to get 4 to its right position. And you sum the hamming distance for all 9 elements. That is your state score.

Also make sure to use a priority queue when selecting the next state, that will make it O(1) when sampling the best successor state in your frontier at each step, but O(logn) when adding new successor states.

Best,

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.