Sort 2D array

[arpit_sof]

can anyone tell how to sort a 2 dimensional integer array using qsort or some in-built function.
Conditions are :
all columns of a row should be in a sorted order,
the all rows corresponding to the matrix should be in a sorted order.

[system]

Will it be always possible to do such sorting?

[arpit_sof]

why not, i am just asking for a sorted 2-D matrix
eg.

initial matrix
3 1 2 2 4
2 3 1 2 1
5 0 1 2 3 
first sorting all rows
1 2 2 3 4
1 1 2 2 3
0 1 2 3 5
then now sorting according to numbers of first row
answer: -
0 1 2 3 5
1 1 2 2 3
1 2 2 3 4

[system]

Hmm, got it..
All I could think now is a 2D BST.
Will that work? never tried this before, seems interesting

[arpit_sof]

can anyone please reply

[leppyr64]

If your 2d array is an array of pointers to arrays, then all you need to do is sort all of the individual arrays, then sort the array of pointers using your own comparator. The complexity of the comparator would likely be O(width of row).

[arpit_sof]

If your 2d array is an array of pointers to arrays, then all you need to do is sort all of the individual arrays, then sort the array of pointers using your own comparator. The complexity of the comparator would likely be O(width of row).

correct me if wrong, it goes like this,
if rows=n and columns=m;
then sorting individual row would take O(m*log(m))
thus in total :> O(n*m*log(m)) since n rows;

then we have to sort the rows among themselves
Order

[leppyr64]

Correct.

To sort all of the rows is O(n*log(n)*m)

[arpit_sof]

sorting all rows would come out to be O(n*m*log(m))
which is different from yours,
as there are m columns and n rows. At this point we have only sorted the individual rows,
Then how to sort the whole row with other rows,,
and what would be time complexity of that.......
some inbuilt function available in C/C++ for it ,,,

[leppyr64]

The complexity for the first step (sort each row) is O(n*m*log(m)) as you correctly mentioned. The complexity to order the rows is O(n*m*log(n)) as I correctly mentioned.