5
$\begingroup$

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

Example of placement of numbers on a linear array

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).

Snake-like ordering on a 2D grid

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Boris Bukh Jun 28 '13 at 10:47
  • $\begingroup$ 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? $\endgroup$ – Alireza Shafaei Jun 28 '13 at 17:08
  • $\begingroup$ 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. $\endgroup$ – Yoshio Okamoto Jun 30 '13 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.