Сортировка матрицы

@iksergeyru

Существует множество способов упорядочивания одномерного массива. Эту задачу решить не составляет особого труда, но что если требуется упорядочить двумерный массив по столбцам.

Т е массив

3 4 7 4 1 5
1 9 1 5 2 4
6 4 6 2 9 1
2 1 2 1 5 3

Превратить в

1 1 1 1 1 1
2 4 2 2 2 3
3 4 6 4 5 4
6 9 7 5 9 5

Давайте разбираться как это сделать.

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

Фактически, решение задачи "сортировки матрицы" сводится к упорядочиванию "одномерных" массив, представляющих собой некоторое количество столбцов.

Если имеется двумерный массив:

int[][] matrix =
{
  new int[] { 3, 4, 7, 4, 1, 5 },
  new int[] { 1, 9, 1, 5, 2, 4 },
  new int[] { 6, 4, 6, 2, 9, 1 },
  new int[] { 2, 1, 2, 1, 5, 3 }
};

Зафиксируем столбец

int column = 0;

Опишем логику упорядочивания элементов выбранного столбца

for (int i = 0; i < size - 1; i++)
{
  int minPos = i;
  for (int j = i + 1; j < size; j++)
  {
    if (array[j][column] < array[minPos][column])
      minPos = j;
  }
  Swap(array[i][column], array[minPos][column]);
}

Для сравнения упорядочивание элементов одномерного массива выглядело бы так:

for (int i = 0; i < size - 1; i++)
{
  int minPos = i;
  for (int j = i + 1; j < size; j++)
  {
    if (array[j] < array[minPos])
      minPos = j;
  }
  Swap(array[i], array[minPos]);
}

Замечание 1: под size понимается количество строк в двумерном массиве и общее количество элементов в одномерном массиве;

Замечание 2: под Swap(x, y) подразумевается метод, меняющий значения элементов х и у местами;

Очевидно, что код отличается только явным указанием сортируемого столбца.

Таким образом, упорядочивание одного столбца можно инкапсулировать в метод выделив в качестве зависимости номер столбца:

void SortColumn(int[][] array, int column)
{
  int size = array.Length; // size = rows

  for (int i = 0; i < size - 1; i++)
  {
    int minPos = i;
    for (int j = i + 1; j < size; j++)
    {
      if (array[j][column] < array[minPos][column])
        minPos = j;
    }
    Swap(array[i][column], array[minPos][column]);
  }
}

Чтобы упорядочить все столбцы требуется перебрать их:

for (int column = 0; column < columns; column++)
{
  SortColumn(matrix, column);
}

Построчное упорядочивание двумерного массива делается аналогично.

Исходник: GitHub

Благодарю за внимание!

Сортировка матрицы

Report Page