Meaningful 2D array sort?

Garrett Rowe
Ranch Hand
Posts: 1296
Is there any meaninful way to sort/search a 2D array. For instance if I have a 2D int[][] with values:

1 5 3
2 4 8
6 9 7

Is there a meaninful way to sort this to

1 2 3
4 5 6
7 8 9

so that if I do a search for 5, I can use a binary search algorithm (either a custom one or one provided by the standard library) to optimize the search speed.

Keith Lynn
Ranch Hand
Posts: 2409
One way would be to place all of the integers from the 2D array into a 1D array, sort it, and then put the numbers back into the 2D array.

Garrett Rowe
Ranch Hand
Posts: 1296
Keith,
Thanks for the reply. Of course you're right. For any real world problem this is what I would do. Really, what happened was that I read at another site that it was twice as expensive to access a 2D array than a 1D array. I decided to test this assertion out and tried to implement the following code:

Obviously this code will not compile bc the Arrays.sort(int[]) method will not sort a 2D array. In this case converting the 2D array to a 1D array nullifies the test I was trying to conduct. So.. my original question stands, is there any other way?
One afterthought: is there a better/more accurate of generating the time stamp than calling the

method?

[ January 22, 2006: Message edited by: Garrett Rowe ]
[ January 22, 2006: Message edited by: Garrett Rowe ]

Layne Lund
Ranch Hand
Posts: 3061
Technically, Java does not have 2D arrays. Really you are using an array of arrays here. This might be why people claim that 2D arrays are slow.

Interestingly, you CAN use the another version of the sort() method: Arrays.sort(Object[], Comparator). Since arrays are Objects in their own right this method will work. However, you will then have to define what it means for one array to be "less than", "greater than", and "equal to" another.

Layne

Garrett Rowe
Ranch Hand
Posts: 1296
Layne

It is possible to do this, however I really would have to implement my own sort() implementation then. For instance if I start out with my original [3][3] array:
1 5 3
2 4 8
6 9 7
I could call the Arrays.sort() method to each "row" and get the result
1 3 5
2 4 8
6 7 9
But then I can't think of a meaningful way to define a Comparator to give me anyting other than what I already have.

Can anyone think of another way to test the 2D array accessor speed other than the one I have already outlined?

Layne Lund
Ranch Hand
Posts: 3061
Originally posted by Garrett Rowe:
Layne

It is possible to do this, however I really would have to implement my own sort() implementation then. For instance if I start out with my original [3][3] array:
1 5 3
2 4 8
6 9 7
I could call the Arrays.sort() method to each "row" and get the result
1 3 5
2 4 8
6 7 9
But then I can't think of a meaningful way to define a Comparator to give me anyting other than what I already have.

I wasn't considering sorting indivdual rows. That may or may not be part of the problem depending on how you define "sorting a 2D array". What if you start with the 3x3 array that you gave but with the 2nd and 3rd rows switched:

1 5 3
6 9 7
2 4 8

Then if you want to sort each row, you will get

1 3 5
6 7 9
2 4 8

I would imagine that you want to sort the rows from here to get the result you gave above:

1 3 5
2 4 8
6 7 9

You could define a Comparator that would give this sort order. If you are using Java 1.5, you will probably define a Comparator<int[]>. Of course, this depends on how you define when one array is "less than" another.

Can anyone think of another way to test the 2D array accessor speed other than the one I have already outlined?

Well, it depends on exactly what you want to test. If you are just testing the access of an element in the array, I can think of a lot easier tests. To access setting the value, you can do something like

Similar methods could be created to test accessing an element of the 2D array and for setting and accessing elements in 2D arrays. In fact, I think that these are much better tests since you don't have the overhead of the sorting algorithm. You are ONLY testing how the array is accessed.

Layne

Garrett Rowe
Ranch Hand
Posts: 1296
Ok, so implementing Layne's suggestion I implemented the following test.

Based on this test on my laptop, there is about a 33% difference between accessing an element in a 2D array and a 1D array.

Layne Lund
Ranch Hand
Posts: 3061
The clock time is not necessarily an accurate measurement of how long an operation takes. This is because the system could be doing other things, especially in this age of multi-tasking operating systems. Unfortunately, this is about the best empirical method availble for measuring such things. It might be interesting to run this program multiple times and taking the average and standard deviation for the sample.

Also, you might want to test getting array elements (i.e. value = array[x][y]). I wonder if there is much of a difference between setting and gettign an element.

Layne