Сортировка столбцов матрицы по возрастанию элементов первой строки

Задача

Изменить последовательность столбцов матрицы так, чтобы элементы их первой строки были отсортированы по возрастанию. Например, дана матрица

 3 -2  6  4
 8  1 12  2
 5  4 -8  0

В результате работы программы она должна быть преобразована в следующую:

-2  3  4  6
 1  8  2 12
 4  5  0 -8

Как мы видим, первая строка отсортирована по возрастанию, а элементы столбцов перемещены в те столбцы, где находятся их первые элементы.

Пояснение к задаче и алгоритм решения

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

Так как известен номер столбца элемента первой строки, который перемещается в конец области массива, то для перемещения всего столбца надо пройтись по всем строкам и обменять значения найденного столбца с последним на данном отрезке массива.

Исходный код на языке программирования Pascal

const
    N = 4; M = 6;
var
    arr: array[1..N,1..M] of integer;
    i,j,k,id: byte;
    max: integer;
 
begin
    randomize;
    for i:=1 to N do begin
        for j:=1 to M do begin
            arr[i,j] := random(50) - 25;
            write(arr[i,j]:4);
        end;
        writeln;
    end;
 
    k := M;
    while k > 1 do begin
        id := 1;
        for j:=2 to k do
            if arr[1,j] > arr[1,id] then
                id := j;
        for i:=1 to N do begin
            max := arr[i,id];
            arr[i,id] := arr[i,k];
            arr[i,k] := max;
        end;
        k := k - 1;
    end;
 
    writeln;
    for i:=1 to n do begin
        for j:=1 to m do
            write(arr[i,j]:4);
        writeln;
    end;
end.

Особенности решения на языке программирования Pascal

Пример(ы) выполнения программы на языке Pascal:

   1   6  10 -21 -22   0
 -25  -8   3  -6  11 -23
  12 -17  23  -5   1  -1
  13   4  -6  10 -16 -21
 
 -22 -21   0   1   6  10
  11  -6 -23 -25  -8   3
   1  -5  -1  12 -17  23
 -16  10 -21  13   4  -6

Исходный код на языке программирования C

#include <stdio.h>
#define N 5
#define M 6
main() {
    int a[N][M], i, j, k, id, max;
    srand(time(NULL));
    for (i=0; i<N; i++) {
        for (j=0; j<M; j++) {
            a[i][j] = rand()%50 - 25;
            printf("%4d", a[i][j]);
        }
        printf("\n");
    }
    printf("\n");
 
    k = M-1;
    while (k > 0) {
        id = 0;
        for (j=1; j<=k; j++)
            if (a[0][j] > a[0][id])
                id = j;
        for (i=0; i<N; i++) {
            max = a[i][id];
            a[i][id] = a[i][k];
            a[i][k] = max;
        }
        k -= 1;
    }  
 
    for (i=0; i<N; i++) {
        for (j=0; j<M; j++) {
            printf("%4d", a[i][j]);
        }
        printf("\n");
    }
}

Исходный код на языке программирования Python

from random import random
N = 5
M = 6
a = []
for i in range(N):
    z = []
    for j in range(M):
        n = int(random() * 50) - 25
        z.append(n)
        print("%4d" % n, end='')
    print()
    a.append(z)
print()
 
k = M-1
while k > 0:
    ind = 0
    for j in range(k+1):
        if a[0][j] > a[0][ind]:
            ind = j
    for i in range(N):
        m = a[i][ind]
        a[i][ind] = a[i][k]
        a[i][k] = m
    k -= 1
 
for i in range(N):
    for j in range(M):
        print("%4d" % a[i][j], end='')
    print()

Исходный код на языке программирования КуМир

алг обмен диагоналей
нач
  цел N=4, M=6
  цел таб a[1:N,1:M]
  цел i, j, k, id, m
  нц для i от 1 до N
    нц для j от 1 до M
      a[i,j] := int(rand(10,50))
      вывод a[i,j], " "
    кц
    вывод нс
  кц
  вывод нс
 
  k := M
  нц пока k > 1
    id := 1
    нц для j от 2 до k
      если a[1,j] > a[1,id] то
        id := j
      все
    кц
    нц для i от 1 до N
      m := a[i,id]
      a[i,id] := a[i,k]
      a[i,k] := m
    кц
    k := k-1
  кц
 
  нц для i от 1 до N
    нц для j от 1 до M
      вывод a[i,j], " "
    кц
    вывод нс
  кц
кон

Исходный код на языке программирования Basic

N = 5
M = 6
dim a(N,M)
for i=0 to N-1
        for j=0 to M-1
                a[i,j] = int(rand*50) + 10
                print a[i,j] + "  ";
        next j
        print
next i
print
 
k = M-1
while k > 0
        id = 0
        for j=1 to k
                if a[0,j] > a[0,id] then id = j
        next j
        for i=0 to N-1
                m = a[i,id]
                a[i,id] = a[i,k]
                a[i,k] = m
        next i
        k = k - 1
end while
 
for i=0 to N-1
        for j=0 to M-1
                print a[i,j] + "  ";
        next j
        print
next i

Тема

Матрицы

Уровень сложности

Сложный

Дата публикации