Сортировка двумерного массива методом обмена (Си)

Question

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

Алгоритм, для вектора:

R = N - 1;
while(R > 0) {
    k = 0;
    for(int i = 0; i < R; i++) {
        if (A[i] > A[i + 1]) {
            tmp = A[i];
            A[i] = A[i + 1];
            A[i + 1] = tmp;
            k = i;
        }
    }
    R = k;
}

Входящий массив:

5	6	4
3	10	0
2	7	9
1	8	11

Результат:

0	4	8
1	5	9
2	6	10
3	7	11

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

left = 0;
for(int left = 0; left < N; left++) {
    down = M - 1;
    while(down > 0){
        k = 0;
        for(int i = 0; i < down; i++) {
          if (A[i][left] > A[i + 1][left]) {
                tmp = A[i][left];
                A[i][left] = A[i + 1][left];
                A[i + 1][left] = tmp;
                k = i;
            }
        }
        down = k;
    }
}

Результат этого кода:

1	6	0
2	7	4
3	8	9
5	10	11

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

Answer 1

Делаете функции перерасчета индексов из одномерного массива в двумерный. geti - индекс по строкам, getj - индекс по столбцам
В закомментированном блоке - сортировка по строкам, т.е. как одномерный массив.
Меняете функции geti и getj и размерность со строк на столбцы и получаете сортировку по столбцам.

int geti(int i, int col) { return i / col; }
int getj(int i, int col) { return i % col; }
     
int main(void)
{
    int K=4, L=3;
    int N = K * L;
    int M[K][L] = { {  5,  6,  4},
                    {  3, 10,  0},
                    {  2,  7,  9},
                    {  1,  8, 11}};
    int R = N - 1;
    int k;
    
/*
    while(R > 0) 
    {
        k = 0;
        for(int i = 0; i < R; i++)
        {
            if (M[geti( i, L)][getj( i, L)] > M[geti( i+1, L)][getj( i+1, L)]) 
            {
                int tmp = M[geti( i, L)][getj( i, L)];
                M[geti( i, L)][getj( i, L)] = M[geti( i+1, L)][getj( i+1, L)];
                
                M[geti( i+1, L)][getj( i+1, L)] = tmp;
                k = i;
            }
        }    
        R = k;
    }
*/
   
    while(R > 0) 
    {
        k = 0;
        for(int i = 0; i < R; i++)
        {
            if (M[getj( i, K)][geti( i, K)] > M[getj( i+1, K)][geti( i+1, K)]) 
            {
                int tmp = M[getj( i, K)][geti( i, K)];
                M[getj( i, K)][geti( i, K)] = M[getj( i+1, K)][geti( i+1, K)];
                M[getj( i+1, K)][geti( i+1, K)] = tmp;
                k = i;
            }
        }    
        R = k;
    }

    std::cout << "\n"; // вывод двумерного массива как одномерного 
    for(int i=0; i<N; i++)
        std::cout << M[geti( i, L)][getj( i, L)] << " ";
    
    std::cout << "\n";
    for(int i=0; i<K; i++)
    {   
        for(int j=0; j<L; j++)
            std::cout << M[i][j] << "\t";
        std::cout << "\n";
    }
   
}

БЛОГ НА HUSL

Сортировка двумерного массива методом обмена (Си)

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