CODEWITHSUNDEEP
javaarrayssortingjava-9
Ousmane D.
Ousmane D.

Reputation: 56423

How to sort two dimensional array lexicographically?

Assuming we have a two-dimensional array as follows:

int[][] source = {
  {   3,  5,  6,  1},
  {   3,  3,  5, -6},
  {  -1, -3, -5, -6},
  { 124, 43, 55, -66}
};

how do we sort the multidimensional array source lexicographically?

So, as a result, I'd expect it to be:

[ [ -1, -3, -5,  -6], 
  [  3,  3,  5,  -6], 
  [  3,  5,  6,   1], 
  [124, 43, 55, -66] ]

a lot of questions on this site seem to only suggest sorting by the first element of each array or second, third etc. but not taking in consideration the entire array.

Upvotes: 3

Views: 1189

Answers (2)

Sk Monjurul Haque
Sk Monjurul Haque

Reputation: 145

First sort each ArrayList in the Array.

ArrayList<ArrayList<Integer>> allSubset = new ArrayList<>();

for(ArrayList<Integer> row : allSubset) {
     Collections.sort(row);
}

Second sort the whole ArrayList in lexicographically.

allSubset.sort((ArrayList<Integer> o1, ArrayList<Integer> o2) -> {
            if(o2.size() == 0) return 1;
            int min = Math.min(o1.size(), o2.size());
            int i;
            for(i = 0; i < min - 1; i++) {
                if(o1.get(i).equals(o2.get(i))) continue;
                return o1.get(i).compareTo(o2.get(i));
            }
            return o1.get(i).compareTo(o2.get(i));
        });

or

    Collections.sort(allSubset, (ArrayList < Integer > first, ArrayList < Integer > second) -> {
        for (int i = 0; i < first.size() && i < second.size(); i++) {
            if (first.get(i) < second.get(i))
                return -1;
            if (first.get(i) > second.get(i))
                return 1;
        }
        if (first.size() > second.size())
            return 1;
        return -1;
    });

Upvotes: -1

Ousmane D.
Ousmane D.

Reputation: 56423

As of JDK9, there's a new method called Arrays.compare which allows you to compare two given arrays lexicographically.

Short description of Arrays.compare from the documentation:

If the two arrays share a common prefix then the lexicographic comparison is the result of comparing two elements, as if by Integer.compare(int, int), at an index within the respective arrays that is the prefix length. Otherwise, one array is a proper prefix of the other and, lexicographic comparison is the result of comparing the two array lengths.

Given you want to modify the source array then using Arrays.sort should suffice:

Arrays.sort(source, Arrays::compare);

Given you want a new array as a result then I'd go the stream way:

int[][] sorted = Arrays.stream(source)
                       .sorted(Arrays::compare)
                       .toArray(int[][]::new);

Upvotes: 7

Related Questions