0
$\begingroup$

The question is as follows:

enter image description here

I am new to this, and I do not understand how to apply divide and conquer to a matrix, the algorithm that I have come up with is as follows (I am not sure if I am correct)

I thought I can divide the matrix into a matrices of 3 x 3 and 2 x 3 first. Then I will apply sorting of rows over column individually on both the matrices. Finally I will copy the second matrix sorting result over to the first sorted matrix. However, my problem is how do I sort the matrix first in to some order so that my division will yield a correct partition else what happens is, post copy I have to again sort (Which I thought is probably wrong)

$\endgroup$
  • 1
    $\begingroup$ Please transcribe the text in your image -- images are inaccessible to search engines and people with visual difficulties. $\endgroup$ – David Richerby Sep 8 '18 at 18:51
1
$\begingroup$

As far as I can see, "sort the rows of the matrix, with respect to their columns" means that you're supposed to sort the rows lexicographically. That is, the row $$a_1\ a_2\ \ldots\ a_n$$ comes before $$b_1\ b_2\ \ldots\ b_n$$ if and only if there's some $i$ such that $a_j=b_j$ for $j<i$ and $a_i<b_i$.

As far as the divide and conquer goes, it doesn't matter that it's a two-dimensional matrix. You're trying to sort a collection of "things" according to some ordering on "things". These "things" happen to be the rows of some array but that doesn't make any difference to the algorithm.

$\endgroup$
  • $\begingroup$ can you please explain how to apply "if and only if there's some i such that aj=bj for j<i and ai<bi" to the given matrix, I did not quite understand it. Thanks $\endgroup$ – shakeel osmani Sep 8 '18 at 19:10
  • $\begingroup$ Check each possible $i$ in turn. $\endgroup$ – David Richerby Sep 8 '18 at 19:10
  • $\begingroup$ But we have to apply merge sort right, that means we will have to divide the matrix into sub matrices and then finally merge them back right $\endgroup$ – shakeel osmani Sep 8 '18 at 20:07
  • $\begingroup$ Yes but just think of it as a one-dimensional array, where each entry of the array is a thing called a row. Basically, the answer is "It's just standard merge sort except for the coding." $\endgroup$ – David Richerby Sep 8 '18 at 21:24
  • $\begingroup$ And what impact will it have on time complexity? $\endgroup$ – shakeel osmani Sep 9 '18 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.