@AlexMark

Сортирование матрицы (двухмерного массива) Java?

Задался вопросом (новичек в Jave, просто решаю пока задачки начальных уровней), что будет лучше для сортировки матрицы, перегнать ее в массив, отсортировать, а потом назад в матрицу, или же сразу сортировать матрицу?
Как можно в Idea проверить, какое решение более быстро работает и меньше выделяет памяти на процесс?
  • Вопрос задан
  • 3337 просмотров
Пригласить эксперта
Ответы на вопрос 2
EugeneP2
@EugeneP2
Java Dev
Если вы планируете сортировать матрицу, то конечно эффективней будет хранить её в виде одномерного массива, чтоб можно было эффективно отсортировать его с помощью быстрой сортировки реализованной методе sort в класса java.util.Arrays.

А чтоб с массивом можно было работать как с матрицей, можно реализовать класс-адаптер
import java.util.Arrays;

public class IntMatrix {
		private final int[] lineMatrix;
		private final int n;
		private final int m;

		public IntMatrix(int[] lineMatrix, int n, int m) {

			if (n < 0 || m < 0 || lineMatrix.length != n * m)
				throw new IllegalArgumentException();

			this.lineMatrix = lineMatrix.clone();
			this.n = n;
			this.m = m;
		}

		public int get(int i, int j) {
			if (i < n && j < m)
				return lineMatrix[i * m + j];
			else
				throw new ArrayIndexOutOfBoundsException();
		}

		public void set(int value, int i, int j) {
			if (i < n && j < m)
				lineMatrix[i * m + j] = value;
			else
				throw new ArrayIndexOutOfBoundsException();
		}

		public  void sort() {
			// готовая реализация быстрой сортировки
			Arrays.sort(lineMatrix);
		}

		public int getN() {
			return n;
		}

		public int getM() {
			return m;
		}
	}


Пример использования
public static void main(String[] args) {


		int n = 10, m = 15;

		IntMatrix intMatrix = new IntMatrix(new int[n * m], n, m);

		fillMatrixByRandomValues(intMatrix);

		printMatrix(intMatrix);

		intMatrix.sort();

		System.out.println("---------------");

		printMatrix(intMatrix);
	}


	/** заполнение матрицы случайными числами */
	static void fillMatrixByRandomValues(IntMatrix matrix) {
		Random random = new Random();
		for (int i = 0; i < matrix.getN(); i++) {
			for (int j = 0; j < matrix.getM(); j++) {
				matrix.set(random.nextInt(1000), i, j);
			}
		}
	}

	/** печать матрицы в консоль */
	static void printMatrix(IntMatrix matrix) {
		for (int i = 0; i < matrix.getN(); i++) {
			for (int j = 0; j < matrix.getM(); j++) {
				System.out.printf("%s\t", matrix.get(i , j));
			}
			System.out.println();
		}
	}


Линейный массив будет занимать меньше места, чем двумерный. Сортировка реализованная в классе java.util.Arrays хорошо и по скорости и по расходу памяти.
Ответ написан
@koronabora
Человек
Матрица хранится как двухмерных массив или список. С ним так и работаем. Можно развернуть матрицу как линейных массив. но тут придется поразвлекаться с индексами, ИМХО, проще с двумерным массивом работать.

Замеры производятся при помощи "засекания" времени работы алгоритма. Записываем показания системного времени до и после выполнения сортировки. Разница - время исполнения алгоритма. Прогоняем несколько раз, берем среднее значение времени. Не забываем отключить все лишние программы на компьютере.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы