Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 3 down vote favorite
1

Is it possible to sort 2d-array by last row with Arrays.sort(,) in Java. The following snippet works great for sorting by last column but it doesn't seem to have a way to be adjusted for sorting by last row.

My first thought was to use tranforming columns to rows, doing sort and then transforming rows to column. Any better way for very big arrays?

int[][] twoDim = { {1, 2, 3}, {3, 7, 11}, {8, 9, 16}, {4, 2,8}, {5, 3, 9} };
Arrays.sort(twoDim, new Comparator<int[]>() {
     @Override
     public int compare(int[] o1, int[] o2) {
         return ((Integer) o1[2]).compareTo(o2[2]);
     }
});

Let's elaborate the whole situation: This is where I am when my array gets initialized and by rows and columns you can imagine this dataset as following:

{1, 2, 3}, //first row with three columns
{3, 7, 11}, //second row with three columns
{8, 9, 16},
{4, 2, 8},
{5, 3, 9} //last row with three columns

Sorting by last row means to rearrange the position of first and second column because 5 is bigger than 3. So after rearranging dataset it looks like:
2, 1, 3
7, 3, 11
9, 8, 16
2, 4, 8
3, 5, 9 //now it's ordered by last row (first and second column have changed they position, by chance third column is in a right place already)

share|improve this question
1  
Please define what you mean by columns and rows, they have me confused a lot. – Dhaivat Pandya May 26 '11 at 22:29
"My first thought was to use tranforming columns to rows, doing sort and then transforming rows to column." This sounds like the best idea to achieve what you want. – Marcelo May 26 '11 at 22:33
That's a very slow procedure. – Dhaivat Pandya May 26 '11 at 22:38

3 Answers

up vote 0 down vote

Interesting question.

I would do it by implementing a variation of quick sort. The variations are essentially in the partition function:

  • you use the last row of your matrix as the array to be sorted
  • when swapping two elements, you actually swap two columns of your matrix

Here's an implementation:

public void qsortOnLastRow(int[][] matrix, int left, int right) {
    if (left < right) {
        int i = partition(matrix, left, right);
        qsortOnLastRow(matrix, left, i - 1);
        qsortOnLastRow(matrix, i + 1, right);
    }
}

public int partition(int[][] matrix, int left, int right) {
    int lastrow = matrix.length - 1;
    int pivotValue = matrix[lastrow][left];
    int i = left;
    for (int j = left + 1; j <= right; j++) {
        if (matrix[lastrow][j] <= pivotValue) {
            i++;
            swapColumns(matrix, i, j);
        }
    }
    swapColumns(matrix, left, i);
    return i;
}

public void swapColumns(int[][] matrix, int c0, int c1) {
    if (c0 != c1) {
        for (int i = 0; i < matrix.length; i++) {
            int t = matrix[i][c0];
            matrix[i][c0] = matrix[i][c1];
            matrix[i][c1] = t;
        }
    }
}

You can sort your int[][] matrix by calling qsortOnLastRow(matrix, 0, matrix[0].length - 1);

Complexity, if I'm not wrong, should be O(m * n * log n), where m = number of rows and n = number of columns in your matrix.

Note: You can use the same trick (sorting on the last row and swapping columns) also with other sorting algorithms.

share|improve this answer
Quick sort has a worst case complexity of O(n^2) to sort n elements. And it has an average case complexity of O(n * log n) to sort n elements. Since, in this case you have to swap whole columns, the complexity is worse. Usually, the amount of comparison is used to describe complexity of sorting algorithms, but here the amount of swaps is far more important. So another algorithm might be better. – jmg May 27 '11 at 8:10
@jmg: swapping here involves and entire columns: swapColumn has complexity O(m) (assuming that the matrix has m rows). Which other algorithm would you recommend? Almost every sorting algorithm use comparison and swap. – MarcoS May 27 '11 at 8:16
Ah well, when I wrote that, your answer said something different ;-) Something, like O(n^2 log n). Does not matter, I can agree on that. Depending on "pre-sortedness" of the arrays it might be worthwhile to try bubble sort, since it usually has to move objects far fewer times. While quicksort moves them quit alot due to partitioning. But to give definite answer, one has to do good benchmarks. – jmg May 27 '11 at 8:19
@jmg: sorry, I edited my answer before replying to your comment :) (yes, it was wrong before, because I had O(n^2 lg n)). I see your point about swapping: I agree some benchmark is required to figure out which approach is better. – MarcoS May 27 '11 at 8:28
up vote 0 down vote

Remember that two dimensional arrays are arrays of arrays. Every sort algorithm needs a facility to move the entries you want to sort. Your solution to sort by last column works, because Arrays.sort sees your inner arrays as the objects to sort. What you call sorting by last row, has no equivalent object, which should represent columns.

So you have two options:

  1. Implement your own sorting algorithm which swaps whole columns at once, but please use a text book algorithm.

  2. Transpose your matrix. But remember that this may be free, if it is possible to swap the meaning of the first and second index in the whole program.

share|improve this answer
What do you mean by free? – ough May 27 '11 at 14:59
up vote 1 down vote

This cannot be answered if I understand what you mean by columns and rows correctly.

If you look at the dataset like this:

1, 2, 3
3, 7, 11
8, 9, 16
4, 2, 8
5, 3, 9

Now, if you sort these by the last row, you get these results:

{2, 7, 9, 2, 3}, {1,3,8,4,5}, {3, 11, 16, 8, 9}

This obviously will not be the case if you replace the 4, 2, 8 row with the 5,3,9 row. So, you have to either come up with a standard ordering, or find a different way to solve the your actual problem that you're facing.

If you are dealing with matrices, I would highly recommend a library.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.