Отсортировать столбцы переданного двумерного массива по возрастанию

Question

Один столбец считается больше второго столбца, если первый элемент (с индексом строки 0) первого столбца больше первого элемента второго столбца и наоборот в противном случае. Если первые элементы столбцов совпадают, то аналогичным образом для сравнения столбцов сравниваются вторые элементы столбцов и т.д. Например: [[1, 1, 2], [4, 3, 6], [6, 4, 9]] превращается в [[1, 1, 2], [3, 4, 6], [4, 6, 9]] Надо написать функцию, пытался но не получилось. Вот мой код, который после своей работы почему то ничего не делает:

public class Main {
    public static void main(String[] args) {
        int[][] twoDimArray = new int[3][3];
        twoDimArray[0][0] = 1;
        twoDimArray[0][1] = 1;
        twoDimArray[0][2] = 2;
        twoDimArray[1][0] = 4;
        twoDimArray[1][1] = 3;
        twoDimArray[1][2] = 6;
        twoDimArray[2][0] = 6;
        twoDimArray[2][1] = 4;
        twoDimArray[2][2] = 9;
        System.out.println(Arrays.deepToString(MatrixSorter(twoDimArray)));

    }
    public static int[][] MatrixSorter(int[][] matrix){
        for(int j=0;j<matrix.length-3;j++){
            for(int i =0;i<matrix[0].length;i++){
                int tempCol = matrix[j][i];
                if (matrix[j][i]>matrix[j][i+1]){
                    matrix[j][i] = matrix[j][i+1];
                    matrix[j][i+1] = tempCol;

                }
                else if (matrix[j][i] == matrix[j][i+1]){
                    matrix[j+1][i] = matrix[j+1][i+1];
                    matrix[j+1][i+1] = tempCol;

                }
            }
        }

        return matrix;
    }
}

Answer 1

В общем случае такая задача решается с помощью транспонирования входного массива/матрицы (ответ на Eng SO: how to sort two dimensional array by one column in Java):

входной массив транспонируется (столбцы превращаются в строки)
транспонированный массив сортируется построчно, используя нужный компаратор
отсортированный массив снова транспонируется, чтобы получить сортировку по столбцам

При транспонировании квадратной матрицы N × N достаточно будет переставлять строки и столбцы местами, а для прямоугольной матрицы N × M потребуется создать новый промежуточный массив и скопировать в него данные.

// транспонировать матрицу 
public static int[][] transpose(int[][] src) {
    if (src.length == src[0].length) {
        // квадратная матрица
        return transpose(src, src);
    }
    // создать новый массив для прямоугольной матрицы
    return transpose(src, new int[src[0].length][src.length]);
}    

private static int[][] transpose(int[][] src, int[][] dst) {
    if (src.length == dst.length) {
        // переставить элементы в квадратной матрице
        return transposeSquare(src);
    }
    // скопировать столбцы в колонки
    for (int i = 0, n = src.length; i < n; i++) {
        for (int j = 0, m = src[i].length; j < m; j++) {
            dst[j][i] = src[i][j];
        }
    }
    return dst;
}

private static int[][] transposeSquare(int[][] arr) {
    for (int i = 0, n = arr.length; i < n; i++) {
        // поменять местами элементы относительно главной диагонали
        for (int j = i + 1, m = arr[i].length; j < m; j++) {
            int tmp = arr[i][j];
            arr[i][j] = arr[j][i];
            arr[j][i] = tmp;
        }
    }
    return arr;
}

Тогда сортировка по колонкам может выглядеть так:

public static void sortByColumn(int[][] arr, Comparator<int[]> comparator) {
    int[][] toSort = transpose(arr);
    Arrays.sort(toSort, comparator);
    transpose(toSort, arr);
}

В качестве компаратора по всем элементам строки можно использовать следующую реализацию, использующую Stream API:

Comparator<int[]> cmp = (a, b) -> {
    return IntStream.range(0, Math.min(a.length, b.length))
        .filter(i -> Integer.compare(a[i], b[i]) != 0)
        .findFirst()
        .orElseGet(() -> Integer.compare(a.length, b.length));
};

Тест и результат:

int[][] arr = {
    {1, 1, 2},
    {4, 3, 6},
    {6, 4, 9}
};
sortByColumn(arr, cmp);
for (int[] a : arr) {
    System.out.println(Arrays.toString(a));
}
System.out.println(Arrays.deepToString(arr));

Результат:

[1, 1, 2]
[3, 4, 6]
[4, 6, 9]
[[1, 1, 2], [3, 4, 6], [4, 6, 9]]

БЛОГ НА HUSL

Отсортировать столбцы переданного двумерного массива по возрастанию

Ответы (1 шт):