Как сортировать по столбцам в 2-х мерных массивах в C?

Question

Я только начал учиться C. И я пытаюсь отсортировать столбцы в 2-мерных массивах в C.

Вот проблема

Напишите программу для ввода массива mx n. Сортировать нечетный столбец по возрастанию и четный столбец по убыванию

Моя идея - использовать рекурсивную функцию. В каждой строке массива я добавлю sh элементов в новый массив, отсортирую его и переназначу старому массиву. L oop это рекурсивно, пока мы не достигнем конца столбцов.

Вот мой код в C:

#include <stdio.h>

int j = 0, temp[] = {}, sizeTemp = 0; // The size of temp, change overtime in loop()
int arr[4][3] = {
    {1,2,3},
    {4,8,6},
    {2,1,5},
    {3,7,4}
};

void pushToArray(int arr[], int currentEl, int addEl){  // Push an element into an array
    arr[currentEl] = addEl;
}

void bubbleSort(int arr[], int size, int inc_dec){  
// Using bubble sort to sort the temporary array, which is then reassigned to the old array
    int temp;

    for(int i = 0; i < size; i++){
        for(int j = 0; j < size - 1;j++){
            if(inc_dec == 1){
                // Increasing
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }else{
                // Decreasing
                if(arr[j] < arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}
int justForReturnSomething(){ 
// void function can't return a value, so I use this just for returning something
    return 1;
}
void loop(){
    int temp2;
    for(int i = 0; i < 4; i++){
        if(j > 2){
            return justForReturnSomething();
        }
        temp2 = arr[i][j];
        pushToArray(temp,sizeTemp,temp2);
        sizeTemp++;
        if(j % 2 != 0){
            bubbleSort(temp,sizeTemp,1);
        }else{
            bubbleSort(temp, sizeTemp,-1);
        }

    }

    for(int k = 0; k < 4; k++){
        arr[k][j] = temp[k];
    }

    if(j > 2){
        return justForReturnSomething();
    }else{
        j++;
        for(int m = 0; m < sizeTemp; m++){ // Reassign the temp to empty
            temp[m] = 0;
        }
        sizeTemp = 0; // reassign the size of temp to 0
        loop();    
    }

}

int main(){

    loop();
    printf("Your sorted array: \n");
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 3; j++){
            printf("%d,",arr[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Результат:

Your sorted array:                                                                                                            
5,0,7,                                                                                                                        
4,0,6,                                                                                                                        
3,0,4,

Только для ДЕМОНСТРАЦИЯ Идея подойти к проблеме, я попробовал это с Javasript, результат отлично:

let arr = [
    [1,2,3],
    [4,8,6],
    [2,1,5],
    [3,7,4]
]; 
let temp = [], j=0;
function bubbleSort( arr,  size,  inc_dec){
    let temp;

    for(let i = 0; i < size; i++){
        for(let j = 0; j < size - 1;j++){
            if(inc_dec == 1){
                // Increasing
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }else{
                // Decreasing
                if(arr[j] < arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

function loop(){
    for(let i = 0; i < 4; i++){
        if(j > 2){
            return;
        }
        temp.push(arr[i][j]);
        if(j % 2 !== 0){
            bubbleSort(temp,temp.length,1);
        }else{
            bubbleSort(temp, temp.length,-1);
        }

    }

    for(let k = 0; k < 4; k++){
        arr[k][j] = temp[k];
    }

    if(j > 2){
        return;
    }else{
        j++;       
        temp = [];
        loop();    
    }

}
loop();
console.log(arr);

Поскольку я пытался решить эту проблему с помощью собственной идеи и нашел решение без поиска в Google, я был бы очень рад, если бы вы могли направить меня ввести решение для C с этим подходом. Но другие подходы очень ценятся.

Answer 1

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

Хитрость здесь в том, чтобы сортировать по столбцам, когда C хранит массивы в главном порядке строк. Вы можете сделать это, определив шаг (для массива с M столбцами и N строками это будет sizeof a[0], то есть размер одной строки) и выполнив все индексирование, кратное этому шагу. Или вы можете транспонировать массив, сортировать по строкам и транспонировать результат обратно.

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

Если вы пишете функции для сортировки по возрастанию и по убыванию, и у вас есть int[M][N], вы можете позвонить sort_ascending( int[i], N ) или sort_descending( int[i], N ) в зависимости от ситуации. Вы можете взглянуть на qsort() в стандартной библиотеке. Если вы хотите попытаться выполнить сортировку на месте, вам нужно будет передать количество строк, количество столбцов и столбец для сортировки. Количество столбцов будет шагом между интересующими вас элементами.

Несколько различных способов контролировать, сортируете ли вы строки вверх или вниз: всегда сортируйте по убыванию, затем увеличивая и увеличивая на 2, сохраняйте флаг, который запоминает отсортировали ли вы последнюю строку по возрастанию или по убыванию, или установите флажок 1%2, который оптимизируется до чрезвычайно дешевой побитовой или инструкции.

Answer 2

Это ответ @Brian. Большое спасибо, Брайан

#include <stdio.h>

void bubbleSort2D(int numRows, int numCols, int arr[][numCols], int col, int incDec) {
  // Using bubble sort to sort a column in the matrix
  for (int i = 0; i < numRows; i++) {
    for (int j = 0; j < numRows - 1; j++) {
      int a = arr[j][col];
      int b = arr[j + 1][col];
      if ((incDec && a > b) || (!incDec && a < b)) {
        arr[j][col] = b;
        arr[j + 1][col] = a;
      }
    }
  }
}

int main() {

  int arr[4][3] = {
    {1,2,3},
    {4,8,6},
    {2,1,5},
    {3,7,4}
  };

  for (int i = 0; i < 3; i++) {
    // sort "odd" columns in descending order, "even" columns in ascending order
    bubbleSort2D(4, 3, arr, i, i % 2 == 0);
  }

  printf("Your sorted array: \n");
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 3; j++) {
      printf("%d,", arr[i][j]);
    }
    printf("\n");
  }

  return 0;
}

Вот ссылка на ссылку:

Сортировка столбцов в двумерном массиве