<p>Assume that we have $N$ numbers (labeled from $1$ to $N$) that are placed on a 1D (linear) array. For example, for $N=5$:</p>

<p><img src="https://i.sstatic.net/8he3A.jpg" alt="Example of placement of numbers on a linear array"></p>

<p>If we want to sort these numbers with the minimum number of adjacent swaps (i.e., by only swapping adjacent numbers), then we can use bubble sort to find the solution. For instance, the aforementioned placement can be sorted with 5 adjacent swaps:</p>

<pre><code>     Initial placement:   3 - 1 - 5 - 4 - 2
After swapping 3 and 1:   1 - 3 - 5 - 4 - 2
After swapping 5 and 4:   1 - 3 - 4 - 5 - 2
After swapping 5 and 2:   1 - 3 - 4 - 2 - 5
After swapping 4 and 2:   1 - 3 - 2 - 4 - 5
After swapping 3 and 2:   1 - 2 - 3 - 4 - 5
</code></pre>

<p>The question, however, is if the numbers are placed on a two dimensional grid, how we can find the minimum number of adjacent swaps in order to sort the numbers? Please assume that the ordering of numbers on the 2D grid is based on the snake-like indexing (as shown below).</p>

<p><img src="https://i.sstatic.net/cfSt6.jpg" alt="Snake-like ordering on a 2D grid"></p>

CC BY-SA 3.0
2013-06-28T10:47:27.437Z
The answer is $\Theta(n^{3/2})$. For upper bound: move numbers on-by-one into their proper places. For lower bound: consider the total distance all the numbers must travel, and not that a single swap contributes only $O(1)$ to that total.
Boris Bukh
CC BY-SA 3.0
2013-06-28T17:08:52.543Z
Thanks Boris. If the number and its proper location are at the same row or column, then there is only one way (path) to move the number to its proper location. However, when they are at different rows and columns, there are $\frac{(n+m)!}{n!m!}$ paths, where $n$ and $m$ are the row and column differences, respectively. Each path will produce a different placement of numbers on the grid, which can affect the movement of the rest of the numbers accordingly. So, how did you address this issue to get $\theta(n^{3/2})$ as the upper bound?
Alireza Shafaei
CC BY-SA 3.0
2013-06-30T22:14:36.847Z
There looks to be some confusion. The comment of @BorisBukh just answers the worst-case asymptotic number of swaps. As far as I understand the comment, this is not meant to be the worst-case asymptotic complexity to find a minimum number of swaps to sort in the grid.
Yoshio Okamoto
<ds.algorithms><sorting>
Minimum Number of Adjacent Swaps to Sort Numbers on a 2D Grid
Alireza Shafaei
# Minimum Number of Adjacent Swaps to Sort Numbers on a 2D Grid

(Asked by: username_0 on 2013-06-27)

Assume that we have $N$ numbers (labeled from $1$ to $N$) that are placed on a 1D (linear) array. For example, for $N=5$:

If we want to sort these numbers with the minimum number of adjacent swaps (i.e., by only swapping adjacent numbers), then we can use bubble sort to find the solution. For instance, the aforementioned placement can be sorted with 5 adjacent swaps:
     Initial placement:   3 - 1 - 5 - 4 - 2
After swapping 3 and 1:   1 - 3 - 5 - 4 - 2
After swapping 5 and 4:   1 - 3 - 4 - 5 - 2
After swapping 5 and 2:   1 - 3 - 4 - 2 - 5
After swapping 4 and 2:   1 - 3 - 2 - 4 - 5
After swapping 3 and 2:   1 - 2 - 3 - 4 - 5

The question, however, is if the numbers are placed on a two dimensional grid, how we can find the minimum number of adjacent swaps in order to sort the numbers? Please assume that the ordering of numbers on the 2D grid is based on the snake-like indexing (as shown below).

**Tags:** ds.algorithms, sorting
> **Comments:**
> **username_1**: The answer is $\Theta(n^{3/2})$. For upper bound: move numbers on-by-one into their proper places. For lower bound: consider the total distance all the numbers must travel, and not that a single swap contributes only $O(1)$ to that total.  
> **username_0**: Thanks Boris. If the number and its proper location are at the same row or column, then there is only one way (path) to move the number to its proper location. However, when they are at different rows and columns, there are $\frac{(n+m)!}{n!m!}$ paths, where $n$ and $m$ are the row and column differences, respectively. Each path will produce a different placement of numbers on the grid, which can affect the movement of the rest of the numbers accordingly. So, how did you address this issue to get $\theta(n^{3/2})$ as the upper bound?  
> **username_2**: There looks to be some confusion. The comment of @BorisBukh just answers the worst-case asymptotic number of swaps. As far as I understand the comment, this is not meant to be the worst-case asymptotic complexity to find a minimum number of swaps to sort in the grid.  

---

## 0 answers

