1. An integer matrix is an n x m array of integers; for example: 3 10 4 1 1012 -
ID: 3883113 • Letter: 1
Question
1. An integer matrix is an n x m array of integers; for example: 3 10 4 1 1012 -18 A=13-12-101 23 67 0 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 A=13 10 3 10 5 67 0 23 (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 columnsExplanation / Answer
Here I am assuming you know the algorithm for InsertionSort
a. Array <--- array[m][n] //declare 2D array of size m and n and later initialize
insertionSort(array[m][n]) //pass array in real insertion sort algorithm
/**********************in InsertionSort*****************/
sort by columnwise // instead of swapping elements swap row arrays
now find where column elements are same and sort it according second column if elemnts of second column are same sort according to subsequent column
tip: // use insertion sort algorithm for above, in that algorithm change 1D array with 2D array and single elements with row array
b. best case is when all the elements in first column are different so we will not have to worry about second column so time complexity only n2
worst case is when all the elements in first n-1 columns are same and only last column elements are different(optional because if same not much difference it will make), here we will have to sort columnwise so for every column we will get n2 time so we will have to sort all n columns due to that time complexity will be n3
c. it will not be same
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.