0

I've just started to learn C. And I'm trying to sort the columns in 2 dimensional arrays in C.

Here's the problem

Write a program to input an array of m x n. Sort the odd column in increasing order and the even column in decreasing order

My idea is to use recursive function. At each row of the array, I will push the elements in a new array, sort it, and reassign to the old array. Loop that recursively until we reach the end of the columns.

Demonstration

Here's my code in 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;
}

Result:

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

Just for DEMONSTRATING the idea to approach the problem, I tried it with Javasript, the result is fine:

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);

Result

Since I've tried to solve this with my own idea and did come up with a solution without searching on google, I'd be very happy if you can guide me to bring in the solution for C with this approach. But, other approaches are greatly appreciated.

13
  • 1
    Javascript has pass by reference, whereas C does pass by value. Commented Apr 14, 2020 at 15:05
  • 1
    It's good to think about how to write testable code - that is, how can I break my code down so that each function does the bare minimum that is required by its test case? This can help simplify code. For example, we could refactor your example above using a sortColumn function, which has a single responsibility (given a matrix, columnIndex, and sort direction, sort the values for that column in the matrix). This function may be easier to implement, and adding logic to sort based on column index is trivial afterwards. Commented Apr 14, 2020 at 15:49
  • 1
    For example, we can write a simple expression in javascript to implement sortColumn: function sortColumn(matrix, columnIndex, desc) { let sortFn = desc ? (a, b) => b - a : (a, b) => a - b; matrix .map(row => row[columnIndex]) .sort(sortFn) .forEach((columnValue, rowIndex) => matrix[rowIndex][columnIndex] = columnValue); return matrix; } Commented Apr 14, 2020 at 15:55
  • 1
    Thanks for the comment Brian. I'll try. But as far as I know, we can't return an array in C. Commented Apr 14, 2020 at 16:10
  • 1
    Here's a quick demo in C: repl.it/repls/ArcticFavorableRoot Commented Apr 14, 2020 at 16:41

2 Answers 2

1

This is the answer from @Brian. Thank you very much 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;
}

Here's repl link:

Srort columns in 2D array

Sign up to request clarification or add additional context in comments.

Comments

0

Not a complete answer, since it looks like you want to solve this problem on your own.

The trick here is to sort by columns, when C stores arrays in row-major order. You can do this by defining a stride (for an array witn M columns and N rows, this would be sizeof a[0], that is, the size of a single row) and doing all indexing in multiples of that stride. Or you can transpose the array, sort by rows, and transpose the result back.

I would recommend sorting in place for performance, but writing the code that does round-trip transposition will probably be simpler. Copying entire arrays twice is expensive, but not incredibly so: it’s proportional to the size of the array.

If you write functions to sort in ascending order and in descending order, and you have an int[M][N], you can call sort_ascending( int[i], N ) or sort_descending( int[i], N ) as appropriate. You might have a look at qsort() in the standard library. If you want to try to sort in place, you’d need to pass the number of rows, the number of columns, and the column to sort. The number of columns would be the stride between the elements you care about.

A few different ways to control whether you sort rows up or down: always sort decreasing then increasing and increment by 2, keep a flag that remembers whether you sorted the last row ascending or descending, or check 1%2, which optimizes to an extremely cheap bitwise or instruction.

2 Comments

Thanks for the help Davislor. I'll look up on that
@Darwin Should’ve said more about the thing that makes the problem non-trivial: that you’re sorting columns, not rows.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.