Recently while working for my project, I came across this situation when I had a 2-D array and I needed to sort it twice on 2 of its columns. Consider the following 2D array:
Sorting the above 2D array on zero column will give
{"1", "2", "6"},
{"4", "5", "3"}
}
whereas sorting it on second column will give
{"4", "5", "3"},
{"1", "2", "6"}
}
I did not want to do the most common as well as tedious thing, i.e. write my own sorting function like this:
//code for sorting the array according to my wish.
}
I wanted to avoid this for 2 resons:
- I would have to write the code for it ( lazy me!!).
- Secondly, I can possibly never match the efficiency provided by the sorting functions of java.util.Arrays
So, my main aim was to look for a solution that would help me sort my 2-D array using the internal JAVA sorters.
I started digging into the JAVA docs (I must admit, I was a naive in JAVA at this point), and came across the Comparator Interface, using which we can tell the JAVA sorting function (Arrays.sort) on how to compare two elements of a 2D array. One must understand that a 2D array is essentially a 1D array with its each element as another 1D array.
Above, there are two arrays containing 3 strings each. We must now compare these two arrays to determine their order in the resultant 2D array. We can compare these two 1-D arrays in any way we like, we can compare them on the first column, third column or on the average length of the strings (just anything!!). Let us implement Comparator interface to define such a compare function:
private int columnToSortOn;
//contructor to set the column to sort on.
2DcolumnComparator(int columnToSortOn) {
this.columnToSortOn = columnToSortOn;
}
// Implement the abstract method which tells
// how to order the two elements in the array.
public int compare(Object o1, Object o2) {
// cast the object args back to string arrays
String[] row1 = (String[])o1;
String[] row2 = (String[])o2;
// compare the desired column values
return row1[columnToSortOn].compareTo(row2[columnToSortOn]);
}
}
Above, we create a class 2DcolumnComparator which implements comparator interface and compare 1D array elements on the column passed to the constructor. Now, we can pass an instance of this class to the Arrays.sort function, and the 2D array will sorted on the desired column.
Here, we instantiate the 2DcolumnComaparator class and pass the column to sort on as parameter to its constructor. Above, the 2D array will be sorted on its fifth column (starting from zero). You can, of course, change the compare function to order elements according to your wish.
That is all I needed to sort a 2-D Array. Happy Sorting!!! 
Useful Resources:
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Comparator.html
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Arrays.html#sort(java.lang.Object[], java.util.Comparator)
Update: If you need to sort a 2D array of objects of any class which implements Comparable, you can look at the comment by Lars. Article last updated on 25 Feb 2010.
hmmmm…seriously it help me a lot…thanks
Dear Nitin,
This post suddenly became a big post at dzone, hence i stumbled upon it. The problem you describe is indeed interesting, but your solution is as a matter of fact just a poor one. There are 2 major flaws: On one hand you copy the whole array, something you should actually avoid in a real life scenario, if we are talking about larger arrays, on the other hand your solution is not generic at all. It is just custom made for your “Array of Array of 4 Strings”-problem.
Java Developer should know at least the core utils the JDK API provides. Your problem could be solved with actually 2 lines using tools from java.util:
package example.sort2d;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Sorter {
public static <T extends Comparable> void sort(final T [][] toSort,final int onColumn) {
List list = Arrays.asList(toSort);
Collections.sort(list, new Comparator(){
public int compare(T[] a, T[] b) {
return a[onColumn].compareTo(b[onColumn]);
}
});
}
}
and as a demonstration
package example.sort2d;
import org.junit.Assert;
import org.junit.Test;
public class ExampleTest {
private final String[][] array = new String[][]
{
{“foo”,”bar”},
{“a”,”b”},
{“me”,”you”},
{“by”,”now”}
};
@Test
public void testSortOnFirstColumn(){
Sorter.sort(array,0);
assertInnerArray(array,0,”a”,”b”);
assertInnerArray(array,1,”by”,”now”);
assertInnerArray(array,2,”foo”,”bar”);
assertInnerArray(array,3,”me”,”you”);
}
@Test
public void testSortOnSecondColumn(){
Sorter.sort(array,1);
assertInnerArray(array,0,”a”,”b”);
assertInnerArray(array,1,”foo”,”bar”);
assertInnerArray(array,2,”by”,”now”);
assertInnerArray(array,3,”me”,”you”);
}
private void assertInnerArray(T [][] onArray, int index, T … values){
Assert.assertArrayEquals(onArray[index],values);
}
}
Sincerely,
Lars
Hi Lars,
Thanks for sharing your alternate viewpoint, I agree that making use of generic class literals would have made a better solution if we want to sort arrays of all types.
But I completely disagree with you that the solution I proposed was tailor made for my problem of “array of array of four strings” and where am I copying the whole array in my final solution? Yes, it is customized just to sort strings, and thats because I started my example with it, other than that where do you think our ‘compare’ functions differ? I think you need to give a second look, but please let me know because I am no JAVA Guru, and am here to learn.
Regards,
Nitin
Lars,
Did you compile the code you posted? The signature of compare is:
int compare(Object o1, Object o2);
Do some groundwork before posting!!! Thanks Nitin, it helped me
@Nitin
Hi Nitin,
First of all sorry, my comment may have sounded more harsh than it was supposed to be. And you are right, somehow i stopped reading before your “note” (I must admit it was late here).
@geek
Sorry, i don’t understand your point. Please have a look at http://java.sun.com/javase/6/docs/api/java/util/Comparator.html#compare(T, T)
Best regards,
Lars
Lars,
Its no problem, and I think you are missing < T[] > from your comparator declaration, which is causing the compilation error, probably what geek is talking about.
It should be:
new Comparator< T[] >() { …
Regards,
@Nitin : Thanks for the post. It was quite helpful. However I’d advice you to stick to Java naming conventions even with small examples like this.
@Lars : Thanks for the alternative. It was helpful too!
@geek : It’s you who should “do some groundwork before posting!”
@Anonymous Genius
I will keep that in mind, its just that I transition between different languages daily that sometimes they get mixed up.
Regards,
Ok, now i see what went wrong. Of course and as usual all generics related <T> are eaten up by the browser. Actually my fault not to write them correctly. The correct version copied from my compiling IDE looks like
package example.sort2d;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Sorter {
public static <T extends Comparable<T>> void sort(final T [][] toSort,final int onColumn) {
List<T[]> list = Arrays.asList(toSort);
Collections.sort(list, new Comparator<T[]>(){
public int compare(T[] a, T[] b) {
return a[onColumn].compareTo(b[onColumn]);
}
});
}
}
This blog might use some preview, that would be helpful.
Lars,
I just formatted your comment to make it clear for the readers, I hope you don’t mind.
Regards,
Your entire blog post compresses to “fmap sort.”
Hi Tony,
I am sorry but I am not aware of “fmap”, nor does Google help. Can you provide some links to suitable resources for the readers?
Thanks,
Hi mate, I recommend looking up what a covariant functor is.
Essentially, Java does not have multi-dimensional arrays, but it does have arrays of arrays. What you are describing is running a function over each element of an array of arrays. Those elements will have be arrays. Then you call sort on them. The notion of “running a function across a functor” is often called fmap. It has this type: F => (A => B) => F and satisfies the law of identity and composition. In your case, F=Array, so: A[] => (A => B) => B[] and I am passing the sort function, so Comparable A => A[] => A[].
fmap sort is how we do this in high-level languages. In fact, it can also be done in Java. See the Functional Java project which defines a fmap function for arrays (called map) and a first-class sort function which you can pass right in. http://functionaljava.org/
Questions?
Thanks Morris, I had no idea about this. I will explore it asap and if I have questions I hope you wouldn’t mind answering them.
Regards,