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] (a) Write pseudocode for this modified version of insertion sort (call it MATRIXINSERTIONSORT) (b) Prove the best- and worst-case complexity of MATRIX-INSERTIONSORT. For simplicity, assume that the matrices are square (i.e. they are n times n matrices, in which the number of rows is equal to the number of columns).

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).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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