13
$\begingroup$

I have a dataset which is a number of objects arranged in a 2-D grid. I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each column. For example,

  • 1 2 3
  • 4 6 7
  • 5 8 9

Can I improve on naive sorting to sort the entire dataset linearly (as measured in comparisons)?

What about for n-d datasets? Arbitrary finite datasets with a subset of comparisons known?

$\endgroup$
3
  • 1
    $\begingroup$ Can you ask a more precise question? Your first paragraph can be read to imply that your data is already sorted! What exactly is your input, and what output do you wish? $\endgroup$ – Jacques Carette Aug 16 '10 at 19:56
  • 1
    $\begingroup$ Yes, the language is a bit confusing. It took me some time to realize that the data set consists of n numbers to be sorted but these numbers are arranged in a sqrt(n) x sqrt(n) grid such that each row and each column is already sorted. Is that what you meant? $\endgroup$ – Hans Aug 16 '10 at 20:00
  • $\begingroup$ Yes, that's what I meant. I will edit for clarity. $\endgroup$ – Zachary Vance Aug 16 '10 at 20:02
19
$\begingroup$

It's easy to prove an Ω(n2 log n) lower bound on this problem (in the comparison sorting model): if the element at position (i,j) is always within distance 1/2 of i+j, then the grid diagonals are independent of each other, and the sorted order within each grid diagonal is arbitrary. So under this constraint the total number of orderings possible is the product (over all the diagonals of the grid) of the factorials of the lengths of the diagonals, which is exponential in n2 log n.

Which is to say that standard comparison sorting algorithms are asymptotically optimal for grids ordered as you describe.

$\endgroup$
1
  • $\begingroup$ The other answer gives an explicit algorithm with this complexity, so I'll consider this problem solved for 2-D grids and, without actually checking, probably for arbitrary dimension grids. $\endgroup$ – Zachary Vance Aug 16 '10 at 20:54
4
$\begingroup$

If I understand the problem correctly (and I may not, feel free to tell me if I don't) you want to transform a 2D grid into a sorted 1D array, whereas each row and column is already sorted in the 2D grid?

The first element in the list in this case has to be the top-left corner ((0,0), by definition of the problem). After this it has to either be the (1,0) or (0,1) element, as all others will be larger than these by definition.

You can generalise by saying that the next smallest element in the grid is always directly below an element already used (or the edge of grid), and also to the right of an element already used (or the edge of grid), since both are defined to be smaller than it. So at each iteration you must only consider the smallest value that fulfills this requirement.

You can keep the possible candidates in sorted order as you find them (no more than two will ever be made available in one iteration), and at each iteration check the new values made available (if any). If they're lower than the lowest of the previous candidates add them to the list straight away and repeat, otherwise add the lowest previous candidate and compare to the next lowest etc.

Unfortunately I don't claim to be able to provide an exact complexity of this, nor do I claim it's the most efficient possible, it certainly seems better than a naive approach, and I hope I explained it well enough for you to understand.

EDIT: For n-d grids like this I believe the same basic principle applies, but each iteration makes up to n new candidates available, and these candidates must be the smallest unused elements in each of n dimensions at this point.

$\endgroup$
1
  • $\begingroup$ In short, you can do an sqrt(N)-way merge, like in mergesort? That was my running best method, but it turns out to be O(N log N)--I don't have an exact constant there, but there's a 0.5 for log(sqrt(N)) at least. $\endgroup$ – Zachary Vance Aug 16 '10 at 20:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.