How to Sort a 2D array?

Question

I need help with sorting 2D array. I've got array with two rows

[5, 3, 4, 1, 2]
[10,20,30,40,50]

and I need to sort it to look like this:

[1, 2, 3, 4, 5]
[40,50,20,30,10]

I know how to do that with bubble sort, but I need some faster algorithm, e.g. quicksort.

Here is my bubble sort code

   for (int i = 0; i < length-1; i++) {
         for (int j = 0; j < length-i-1; j++) { 

            if (array[0][j] > array[0][j+1]) {

               for (int k = 0; k < 2; k++) {
               int tmp = array[k][j];
               array[k][j] = array[k][j+1];
               array[k][j+1]=tmp;
               }
           }
       }
    }

if you need Quicksort, than you can use [Quicksort](https://en.wikipedia.org/wiki/Quicksort) — Sam I am says Reinstate Monica, Sep 09 '13 at 19:06
It looks like you've got some sort of map or dictionary. Have you considered using a different data structure? — thegrinner, Sep 09 '13 at 19:11
Possible duplicate of [Sort a two dimensional array based on one column](http://stackoverflow.com/questions/4907683/sort-a-two-dimensional-array-based-on-one-column) — Jaroslaw Pawlak, Apr 11 '17 at 14:08

score 4 · Answer 1 · edited May 23 '17 at 12:18

transpose the 2D array java multi-dimensional array transposing

use Arrays.sort(T[] a, Comparator<? super T> c) where the comparator compares on index 0 of each row

transpose the result again:

e.g.

from: [5,3,4,1,2] [10,20,30,40,50]

obtain [5, 10] [3, 20] [4, 30] [1, 40] [2, 50]

then sort them to [1, 40] [2, 50] [3, 20] [4, 30] [5, 10]

then transpose again to: [1,2,3,4,5] [40,50,20,30,10]

or implement quicksort by yourself.

tkroman · Answer 2 · 2013-09-09T19:21:24.150

1

Edit (after OP changed formulations):

You may collect that all to Map and then sort it by keys. Collecting to Map is O(n) and you can get sorting for free using ordered Map implementation. Transposing looks more expensive to me

edited Sep 09 '13 at 19:21

answered Sep 09 '13 at 19:11

tkroman

4,811
1
26
46

No, i need sort first row and in the same order that second. In first is index and in second the value. – Jakub Martinek Sep 09 '13 at 19:17
@JakubMartinek this will do exactly that. Translate your 2d array to a `Map`. quick-sort the keyset (or whatever algorithm you want to use). Then, if it really has to be an `array` for some reason, translate it back into an array by iterating over the `keyset` of the `Map`. This is an excellent solution, with the proviso that the keys have to be unique, any duplicate keys would be discarded – StormeHawke Sep 09 '13 at 19:27
@StormeHawke, that's comment to my previous post edit, where I told incorrect solution due to incorrect question statement :) – tkroman Sep 09 '13 at 19:29

score 0 · Answer 3 · answered Sep 09 '13 at 19:10

0

Did you think about merge-sort-alorithm?

http://en.wikipedia.org/wiki/Merge_sort that should be the fastest in that case. (an abstract implementation is available in wiki too)

answered Sep 09 '13 at 19:10

user972851

191
1
17

score 0 · Answer 4 · edited May 23 '17 at 10:30

You can use Comparator to do that. This thread has some useful information for C++ . Sample code in Java is like,

Arrays.sort(a, new Comparator<Long[]>() {

        @Override
        public int compare(Long[] o1, Long[] o2) {

            Long t1 = o1[1];
            Long p1 = o1[0];
            Long t2 = o2[1];
            Long p2 = o2[0];

            if (t1 == t2) {
                return (p1 > p2 ? 1 : (p1 == p2 ? 0 : -1));
            } else {
                return (t1 < t2 ? -1 : 1);
            }

        }
    });

Do your comparison login in compare method and return the relevant values to sort the array accordingly.

How to Sort a 2D array?

4 Answers4

Linked

Related