CODEWITHSUNDEEP
pythoncalgorithmsortingmatrix
Mridul Kanti Roy Chowdhury
Mridul Kanti Roy Chowdhury

Reputation: 139

row sorted column sorted matrix

can anyone suggest an algorithm for generating a row sorted, column sorted 2-D matrix given a list of integers ? What I mean is that all rows and all columns should be sorted, preferably in asc/desc order for the entire matrix.

What I came up with is that first sort the list of elements, start at 0,0 and then place the next element at 0,1 then 1,0 then 0,2 then 2,0 and so forth. When there is a limit breach for row/column, pick the next row/column and continue.

Examples of my algo- Elements are natural numbers starting from zero.

3 X 5 Matrix - 

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

5 X 7 Matrix - 

0     1      3     5     7   9  11
2     10     13   15    17  19  21
4     12     18   23    24  26  28
6     14     20   25    29  30  32
8     16     22   27    31  33  34

Is this right ? Can you propose an alternate algo and any code for that (Python/C) ? Thanks in advance.

Edit - Preferably not using any other libraries in Python e.g. numpy etc. Is there a way to implement this with simple plain old python code ?

Upvotes: 2

Views: 711

Answers (4)

user6110729
user6110729

Reputation: 156

you have to use 2 for cicle into a for cicle:

an example:

int matrix[4][4]; //your matrix is a 4x4 in this example
int sum[]={0,0,0,0};

for(int index=0; index<=4; index++){
    for(int i=0;i<=4;i++){  //here sum the row
        sum[index]+=matrix[index][i];
    }

    for(int i=0;i<=4;i++){  //here sum the column
        sum[index]+=matrix[i][index];
    }
}

at the end you will have sum of row&column A in sum[0], B in sum[1],...

Upvotes: 0

user1196549
user1196549

Reputation:

Assuming an RxC array, where R ~ C and R>C, it is clear that the task requires at least to sort all rows, taking an effort O(R.C.Log(C)). Compare this to the effort for a global sort O(R.C.Log(R.C)) = O(R.C.Log(C)) and you see that it may not be really worth to try and find shortcuts, unless R>>C.

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 119857

 1  2  3  4  5
 6  7  8  9 10
 11 12 13 14 15

Upvotes: -1

pmg
pmg

Reputation: 108978

Treat your 2x2 matrix as a single dimension array and sort that using qsort(). Voila!

int arr[3][3];
for (int row = 0; row < 3; row++) {
    for (int col = 0; col < 3; col++) {
        arr[row][col] = row * 3 + col;
    }
}
qsort(arr[0], 9, sizeof (int), delta);

int delta(const void *a, const void *b) {
    const int *aa = a;
    const int *bb = b;
    return *aa - *bb;
}

Upvotes: 2

Related Questions