retagged by
425 views
0 votes
0 votes
Assume Two-Dimensional Sorted Array (TDSA) is a two-dimensional

matrix of size n × n such as the elements in the matrix are sorted

row-wise and column-wise. For example, the following matrix is a TDSA.

1 2 3

4 5 6

7 8 9

Write an algorithm that should convert the given matrix of a dimension

n × n into TDSA. Analyse the running time of the algorithm.
retagged by

1 Answer

0 votes
0 votes
Consider

1 3 5

3 5 7

4 5 8

Compare 1×3 with 2×1 if they match, it's fine, move on.

If they don't, then 1. go back an element the previous row, compare again, consider the inequality and decide which one to be added first.

Do the same for the next rows.

 

P.S. duplicate should also be considered.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
Karthi2003 asked Sep 9, 2022
656 views
Given ‘N’ objects, which are coloured as red, white and blue. Sort theseobjects so that objects of the same colour are adjacent, with the coloursin the order red, whi...
0 votes
0 votes
2 answers
4
_Madhuri asked Oct 9, 2021
634 views
The complexity of comparison based sorting algorithm is (nlogn) .How?