Sorting a 2-Dimensional Array in Java

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:

String[][] testString = new String[][] {
    {"1", "2", "6"},
    {"4", "5", "3"}
  };

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:

public void myOwnSort(String [][] exampleArray) {
    //code for sorting the array according to my wish.
}

I wanted to avoid this for 2 resons:

  1. I would have to write the code for it ( lazy me!!).
  2. 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.

String[][] testString = new String[][] {
    {"1", "2", "6"},
    {"4", "5", "3"}
  };

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:

class 2DcolumnComparatorΒ implements Comparator {
    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.

public class Analysis {

  public static void main(String args[]) {
    String[][] childrenArray = new String[MAXLIMIT][10];

    //Populate the Array and sort
    Arrays.sort(childrenArray,new 2DcolumnComparator(5));
}
}

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:

  1. If you need to sort a 2D array of objects of any class which implements Comparable, you can look at the comment by Lars.
  2. 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.

23 thoughts on “Sorting a 2-Dimensional Array in Java

  1. Lars

    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

    Reply
    1. Nitin Post author

      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

      Reply
    2. geek

      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 πŸ™‚

      Reply
    1. Nitin Post author

      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,

      Reply
  2. Anonymous Genius

    @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!” πŸ˜›

    Reply
    1. Nitin Post author

      @Anonymous Genius

      I will keep that in mind, its just that I transition between different languages daily that sometimes they get mixed up.

      Regards,

      Reply
  3. Lars

    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.

    Reply
  4. autofei

    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));
    }
    }

    Reply
  5. agil

    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.

    Reply
  6. Line

    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 .

    Reply
  7. Mark

    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.Arrays;
    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]);
                    }
                }
            );
        }
    }
    Reply
    1. Nitin Post author

      Cool, I appreciate you for sharing your work with the readers here. :). Added a link to it in the post for easy access.

      Reply
  8. munir

    I am a newbi to Java. I am trying to understand what you guys have done here, but getting lost. Can you tell me how to understand this wizardry … I read about compare, sorting, comparator, etc.. but when it comes to sorting multiple arrays, just can’t understand it..thanks..

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *