Сортировка матрицы nxn (2D-массив)

Question

Во время теста на программирование мне было предложено написать программу Java для сортировки по матрице 3x3. т.е. я получил матрицу (2D-массив, скажем, m[3][3])

2 6 1 
3 5 7 
4 8 9 

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

1 2 3 
4 5 6 
7 8 9 

Что я сделал, чтобы преобразовать эту 3x3 матрицу в 1D массив

a[9] = {2,6,1,3,5,7,4,8,9} 

и выполнил пузырьковую сортировку на этом массиве и преобразуют результирующий массив обратно в 2D массив.

Я не был доволен этим подходом, поскольку я чувствовал, что этот подход очень дрянной. Есть лучший способ сделать это.

Редактировать: Я хотел бы удалить часть преобразования массива. Любой алгоритм сортировки можно использовать и хотел бы выполнить сортировку по самой матрице (2D-массив).

Answer 1

Для уменьшения сложности времени вы можете использовать другой алгоритм сортировки, например, quicksort или, возможно, radixsort (потому что вы имеете дело только с числами).

Преобразование матрицы в массив - это не ваш основной метод потребления времени, а сортировка. Поэтому оптимизируйте это и только потом попробуйте разные методы.

редактировать:

Согласно макету m[3][3] данных, вы можете использовать bucket sort (это может привести к большему увеличению производительности, если вы используете m[1000][1000] Потому что у вас уже есть ведра, которые можно сортировать, это будет. устранить необходимость преобразовать его первым

Answer 2

Ну под ваши странными требованиями вы можете создать вид список из подкрепленного входной матрицы и сортировать его с помощью стандартного Collections.sort:.

public static void sortMatrix(final int[][] matrix) { 
    // Assuming the matrix is rectangular 
    final int n = matrix.length; 
    final int m = matrix[0].length; 

    List<Integer> list = new AbstractList<Integer>() { 
     @Override 
     public Integer set(int index, Integer element) { 
      return matrix[index/m][index%m] = element; 
     } 

     @Override 
     public Integer get(int index) { 
      return matrix[index/m][index%m]; 
     } 

     @Override 
     public int size() { 
      return n*m; 
     } 
    }; 
    Collections.sort(list); 
} 

Здесь мы просто определим наши собственные методы get и set, которые меняют соответствующий матричный элемент. Пример использования:

int[][] matrix = {{2,6,1},{3,5,7},{4,8,9}}; 
sortMatrix(matrix); 
System.out.println(Arrays.deepToString(matrix)); 

Выход:

[[1, 2, 3], [4, 5, 6], [7, 8, 9]] 

Answer 3

У вас есть N целых чисел, превращая его из 2D массива -> 1D массив и 1D -> 2D массив не может занять больше времени, чем O (N) времени при сортировке в общем занимает больше времени, чем то, что означает, что Сортировка доминирует над вашей временной сложностью. Тем не менее, вы должны сосредоточиться на внедрении более эффективной сортировки.

Попробуйте использовать сортировку кучи, например, сложность по времени - O (NlogN), которая намного быстрее, чем сортировка пузырьков (O (N^2)). По мере того, как ваш вклад становится все больше, вы увидите резкое различие в количестве времени, которое занимает ваш процесс.

Answer 4

public int[][] sortMatrix(int matrix[][], int r, int c) { 

    for (int k = 0; k < r * c; k++) { 
     Integer current = null; 
     Integer previous = null; 
     Integer currentI = null; 
     Integer currentJ = null; 
     Integer previousI = null; 
     Integer previousJ = null; 
     for (int i = 0; i < r; i++) { 
      for (int j = 0; j < c; j++) { 
       current = matrix[i][j]; 
       currentI = i; 
       currentJ = j; 
       if (previous != null) { 
        if (current < previous) { 
         matrix[currentI][currentJ] = previous; 
         matrix[previousI][previousJ] = current; 
        } 
       } 
       previous = matrix[i][j]; 
       previousI = i; 
       previousJ = j; 
      } 
     } 
    } 
    return matrix; 
} 

Answer 5

Вы можете воспользоваться Streams:

public int[][] sortWithStreams(int[][] matrix) { 
    return Arrays.stream(matrix) 
      // Turn it into a stream of ints by streaming each row. 
      .flatMapToInt(x -> Arrays.stream(x)) 
      // Sort it. 
      .sorted() 
      // Gather the now sorted stream back into a new array. 
      .collect(
        // A new matrix. 
        () -> new int[matrix.length][matrix[0].length], 
        // Consumer folds each value into the next position in an array. 
        new ObjIntConsumer<int[][]>() { 
         // Start at [0][0] 
         int x = 0, y = 0; 

         @Override 
         public void accept(int[][] t, int value) { 
          // Place it and step on. 
          t[y][x++] = value; 
          // Wrap if necessary. 
          if (x >= t[y].length) { 
           x = 0; 
           y += 1; 
          } 
         } 

        }, 
        // As `sorted` cannot generate a parallel stream it is safe to ignore the combiner. 
        null); 
} 

public void test() { 
    int[][] matrix1 = {{2, 6, 1}, {3, 5, 7}, {4, 8, 9}}; 
    int[][] matrix2 = {{2, 6, 1, 12}, {3, 5, 7, 10}, {4, 8, 9, 11}}; 
    int[][] matrix3 = {{2, 6, 1}, {3, 5, 7}, {4, 8, 9}, {1, 3, 12}}; 
    // Print them. 
    System.out.println(Arrays.deepToString(sortWithStreams(matrix1))); 
    System.out.println(Arrays.deepToString(sortWithStreams(matrix2))); 
    System.out.println(Arrays.deepToString(sortWithStreams(matrix3)));// 
}