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)
Recommended Reading:
Core Java(TM), Volume I–Fundamentals (8th Edition)
Core Java(TM), Volume 2–Fundamentals (8th Edition)
Updates:
- If you need to sort a 2D array of objects of any class which implements Comparable, you can look at the comment by Lars.
- If you need to sort a multi-dimensional array on multiple columns, you can look at the comment by Mark.
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
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,
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Sorter {
@SuppressWarnings(“unchecked”)
public static 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]);
}
@Override
public int compare(Object o1, Object o2) {
T[] a = (T[])o1;
T[] b = (T[])o2;
return compare(a,b);
}
});
}
public static void main(String[] args) {
final String[][] array = new String[][] { { “foo”, “bar” },
{ “a”, “b” }, { “me”, “you” }, { “by”, “now” } };
System.out.println(Arrays.deepToString(array));
Sorter.sort(array, 0);
System.out.println(Arrays.deepToString(array));
}
}
I just post a working version modified from Lars version. Hope it helpful.
Thanks, it helped me alot. No changes needed at all
Hello Nitin,
Your solution very useful for two Dimensional array with same length.
My question is, can we sort two dimensional array based on some row and based on data length. for example we have an array {{”c”}, {”c”}, {”c”, “d”},{”c”, “a”},{”b”}}. how to get the sorted array like this {{”b”},{”c”},{”c”},{”c”,”a”},{”c”, “d”}}.
Thx a lot Nitin.
The solution is really helpful and I cannot imagine that I can make benefit of
comparator to deal with array object by itself ..
Thank you very much Nitin .
Really helpful article
Quite often in multidimensional arrays, you may want to do a secondary sort on another column. For example, sort first on last name, then on first name if the last names are the same.
Here are a couple extensions to Lars Feb 23, 2010 posting. I apologize in advance that some of the html might get eaten by the browser.
The following code first is a copy of Lars’ posting, followed by code for sorting on two columns, then a third example on sorting by an arbitrary number of columns, using an array of column numbers as the input.
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class TwoDcolumnComparator {
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]);
}
}
);
}
public static < T extends Comparable> void sort(final T [][] toSort,final int onColumn1, final int onColumn2) {
List list = Arrays.asList(toSort);
Collections.sort(
list, new Comparator(){
public int compare(T[] a, T[] b) {
if (a[onColumn1].compareTo(b[onColumn1]) == 0) {
return a[onColumn2].compareTo(b[onColumn2]);
} else {
return a[onColumn1].compareTo(b[onColumn1]);
}
}
}
);
}
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) {
for (int i = 0;i < onColumn.length-1;i++){
if (a[onColumn[i]].compareTo(b[onColumn[i]]) != 0) {
return a[onColumn[i]].compareTo(b[onColumn[i]]);
}
}
return a[onColumn.length].compareTo(b[onColumn.length]);
}
}
);
}
}
Cool, I appreciate you for sharing your work with the readers here.
. Added a link to it in the post for easy access.
So why is it that
is faster than
Can that really be?
I don’t think so, it seems to be inspired from the original comment from Lars. Mark, or in fact Lars, will be able to throw some more light.
Great article post.Much thanks again. Really Cool.