An integer matrix is an n times m array of integers: for example: A = [3 1 3 67

Question

An integer matrix is an n times m array of integers: for example: A = [3 1 3 67 3 10 1012 -12 0 10 4 -18 -101 -23 5] A row is a series of numbers from left to right and a column is the series from top to bottom. Here, we will modify insertion sort to sort the rows of a matrix, with respect to their columns. For the above example, this yields: A = [1 3 3 3 67 1012 -12 10 10 0 -18 -101 4 5 -23] (c) Assume that comparing two rows can be done in constant time (Theta (1)). Is the worst-case complexity of MATRIXINSERTIONSORT in this case better or worse than regular insertion sort? Why? (d) Assume that we are guaranteed that each row of the matrix is pre-sorted (i.e., increasing from left to right). For the example above, we would have: A = [3 -18 -101 -23 3 4 1 -12 0 5 10 1012 3 67 10] Does this guarantee change the worst-case complexity of MATRIXINSERTIONSORT?

Explanation / Answer

Pseudocode is as follows:

So insertion sort is all about inserting a[i] in the sorted array a[0..i-1]

Say A is a set of all the row vectors
compare(a, b) - this compares the tuples and return 1 if b > a

for i := 1 to n-1:   (Assuming array starts with 0)
    for j: 0 to i-1:
        if compare(a[i],a[j]) == 1
            insert a[i] at jth place and shift all the elements to one position right starting from j onwards.

So i = 1 we have 1 comparison, i = 2 , two comparisons.....

So for n we have = 1+2 +3 + 4 +5 +6 +.....(n-1) = (n-1)(n)/2

So in worst case the complexity will be O(n^2) plus we also have to look at the compolexity of comparing the row vectors of size n and this complexity is O(n) as we have to compare each and every element of both the row vectors. So the total
complexity in the worst case is O(n^2) + O(n).

In the best case may be if the it already sorted but in this case also we have to have minimum one comparison. So the order of complexity will be O(n). So the total complexity will be O(n) + O(n).

c)In case the row comparison is done in O(1) time, then the complexity of matrix insertion sort is comprable to normal insertion sort becuase this is the only step which is of constant time in normal insertion sort.

d) If the rows are presorted, then also there is not much impact on the overall complexity because the rows are tuples are just one entity, the overall insertion alorithm is independent of that.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.