Sort matrix row-wise and keep indices

user_15942576 0
Viewed 230

I am trying to sort a 2D array row-wise in Java. However, I want to only sort the indeces, not the values itself.

For example:

values
1.3 0.3 0.4 0.1
0.4 0.2 3.7 2.4
2.1 6.4 1.9 0.3

indices       sorted according to values
0 1 2 3       3 1 2 0
0 1 2 3  -->  1 0 3 2
0 1 2 3       3 2 0 1

Unfortunately, anything I could find in other StackOverflow questions was either how to sort a matrix, or how to keep indices when sorting an array. But combining both efficiently is what I struggle with.

Any insight would be gladly appreciated.

What I tried so far, but that does not work. It seems to not change my matrix at all.

// Function to sort the given matrix in row wise manner
public void RowWiseSort(Integer[][] idx, double[][] values) {
    // Traverse the row
    for (int i = 0; i < (int) idx.length; i++) {
        ArrayIndexComparator comp = new ArrayIndexComparator(values[i]);

        // Row - Wise Sorting
        Arrays.sort(idx[i], comp);
    }
}

private class ArrayIndexComparator implements Comparator<Integer> {
    private final double[] A;

    public ArrayIndexComparator(double[] arr) {
        this.A = arr;
    }

    @Override
    public int compare(Integer o1, Integer o2) {
        return Double.compare(A[o1], A[o2]);
    }
}
multidimensional-array matrix sorting arrays java
3 Answers

Given your example 2D-Array of doubles

double[][] values = {
        {1.3, 0.3, 0.4, 0.1},
        {0.4, 0.2, 3.7, 2.4},
        {2.1, 6.4, 1.9, 0.3}};

and the expected result is a 2D-Array of the indices(Integers) sorted according to the values above; you can do something like:

Integer[][] result = IntStream.range(0, values.length)
        .mapToObj(i -> IntStream.range(0, values[i].length)
                .boxed()
                .sorted(Comparator.comparingDouble(j -> values[i][j]))
                .toArray(Integer[]::new))
        .toArray(Integer[][]::new);

for (Integer[] row : result) {
    System.out.println(Arrays.toString(row));
}

output:

[3, 1, 2, 0]
[1, 0, 3, 2]
[3, 2, 0, 1]
user_51769920

You can use Java Streams as follows:

double[][] arr = {
        {1.3, 0.3, 0.4, 0.1},
        {0.4, 0.2, 3.7, 2.4},
        {2.1, 6.4, 1.9, 0.3}};

// row-wise sorted array of indices
int[][] idx = Arrays.stream(arr)
        .map(row -> IntStream
                .range(0, row.length)
                // Stream<Integer>
                .boxed()
                // sort indices by element value
                .sorted(Comparator.comparingDouble(i -> row[i]))
                // IntStream
                .mapToInt(Integer::intValue)
                // row of indices
                .toArray())
        .toArray(int[][]::new);

Arrays.stream(idx).map(Arrays::toString).forEach(System.out::println);
//[3, 1, 2, 0]
//[1, 0, 3, 2]
//[3, 2, 0, 1]

See also: Finding the position of a row element in a 2d ordered array

Admin1

You may create a custom data structure, e.g. "MatrixEntry" which can encapsulate value and indice. You can define a custom comparing logic for the instances of MatrixEntry. Instead of 2D array of doubles, you can have a 2D array of MatrixEntry instances. Then you can sort the rows based on the custom comparing logic you've defined.

class MatrixEntry implements Comparable<MatrixEntry> {
    double value;
    int indiceInRow;

    @Override
    public int compareTo(MatrixEntry other) {
        // define your comparing logic.
    }
}

Once all entries are sorted, you can easily generate a 2D array of indices from the 2D array of matrix entries.

user_5449830
Related