I. An integer matrix is an n × m array of integers; for example: 3 10 4 1 1 1012
ID: 3885246 • Letter: I
Question
I. An integer matrix is an n × m array of integers; for example: 3 10 4 1 1 1012 -18 A- 3 12-101 67 0 -23 3 10 5 3 10 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 colums. For the above example, this yields: 1 1012-18 3 -12-101 10 3 10 5 67 0 23 A=13 (a) (15 pts) Write pseudocode for this modified version of insertion sort (call it MATRIXINSERTIONSORT) (b) (20 pts) Prove the best- and worst-case complexity of MATRIX- INSERTIONSORT. For simplicity, assume that the matrices are square (ie, they are n × n matrices, in which the number of rows is equal to the number of columns).Explanation / Answer
To Take MAtrix Input and Display it, Following program can be run:
Insertion sort Algo:
a) Pseudo code for insertion sort explained with the help of Array:
b)This can be done by taking Matrix instead of an Array and representing it in Column major order/row major order
After that 1st column to be sorted ,make sure that the row remain intact with its 1st column value so that while arranging , the complete row should change along with the position of 1st element of the column.
c)Worst case: Order of n squared (simple sort)
n*O(n^2) in matrix selection sort. because here there are technicaly more arrays. to be gone through.
d)Yes, if its always presorted, worst case time complexity will change