Sorting Algorithms Discussion

Moved here from SortingAlgorithms:

Are there any sorting algorithms for two dimensional arrays? AnswerMe -- JonGrover

How do you define "sortedness" for a two dimensional array?

It might mean that given that every cell in the array has two values, an X value and a Y value. The 2 dimensional array is sorted when the X values for the cells are ordered as well as is possible in the X dimension, and the Y values in the cells are ordered as well as possible in the Y dimension.

Or something like that.

I don't understand that suggestion. Perhaps the original questioner could provide a before and after type example - here's my array before, and here's what I expect to be output, and why.

I'm not the original questioner, but here's something "sorted" could mean for a 2d array: i<=I & j<= J ==> a[i,j] <= a[I,J]. Clearly you can achieve this by considering the whole array as a single vector in (say) row-major order and sorting that, but maybe there are ways of achieving that condition that are a little cheaper (can't be much more than a factor of 2 cheaper, of course) or that are more restricted in what permutations they are allowed to apply.

Rolling a few dice, I came up with this example. I came up with 9 tpairs with the intention of sorting them into a 3x3 array. The pairs were (3,6) (5,3) (6,3) (2,3) (4,6) (5,5) (1,6) (6,1) (4,1). They might sort into a 2D array as follows (in this case X is sorted slightly better):

 +-------+-------+-------+
 | (3,6) | (4,6) | (5,5) |
 +-------+-------+-------+
 | (1,6) | (5,3) | (6,3) |
 +-------+-------+-------+
 | (2,3) | (4,1) | (6,1) |
 +-------+-------+-------+

They might also sort less well like so (in this case Y is sorted slightly better):

 +-------+-------+-------+
 | (1,6) | (3,6) | (4,6) |
 +-------+-------+-------+
 | (2,3) | (5,5) | (6,3) |
 +-------+-------+-------+
 | (4,1) | (5,3) | (6,1) |
 +-------+-------+-------+

This could be useful for example in coming up with an 'index' for a sparse array. For example if you have a 1000 x 1000 array with 40,000 values set, you could set up a 200 x 200 'index' 2D array which contains the values of the sparse array coordinates ordered by those coordinates, and if you only wanted to work on a a 5x5 portion of that, you would probably not have to deal with either most of the 200x200 array or with the 40,000 items. You could focus on perhaps a 10x10 area in the index array which is only 100 items. This could be useful in GIS applicaitons. -- JonGrover

---

Perhaps a better phrasing of the 2d sorting could be posed, with some thought directed towards the purpose of sorting a simple list.

You don't do it because you want the list in order.

You do it because of the properties that a sorted list has; specifically, the ability to get at a particular item quicker. There's no other point to it. This is why a hash-map is just as useful, especially when the hash value is consistent with the items' natural ordering (i.e., when it's really a radix sort).

• Saying "there's no other point to it" is much too strong a statement. Another valid point to it might be if doing so directly models something in the problem domain. Also a hash is not always just as useful. The common case where hashes completely fail is for inexact matching, e.g. ">=" rather than just "==".

The question "Are there any sorting algorithms for two dimensional arrays?" means "Is there any preprocessing we can do so that we can efficiently find an item in a two dimensional array?", realizing that 'sorting' = 'preprocessing in order to decrease average seek time'.

And so: yes, there are many...

[see TwoDimensionalRendezvous and related pages]

-- WilliamUnderwood