1. An integer matrix is an n × m array of integers; for example: A = { 3 10 4 1
ID: 3745026 • Letter: 1
Question
1. An integer matrix is an n × m array of integers; for example: A =
{ 3 10 4
1 1012 18
3 12 101
67 0 23
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 merge sort to sort the rows of a matrix, with respect to their columns. For the above example, this yields: A =
{1 1012 18
3 12 101
3 10 4
3 10 5
67 0 23 }
(a) (15 pts) Write pseudocode for this modified version of merge sort (call it MatrixMergeSort)
(b) (20 pts) Prove the best- and worst-case complexity of MatrixMergeSort. For simplicity, assume that the matrices are square (i.e. they are n × n matrices, in which the number of rows is equal to the number of columns).
(c) (5 pts) Assume that comparing two rows can be done in constant time ((1)). Is the worst-case complexity of MatrixMergeSort in this case better or worse than regular merge sort? Why?
(d) Extra credit (5 pts): 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 4 10
18 1 1012
101 12 3
23 0 67
3 5 10 }
Does this guarantee change the worst-case complexity of MatrixMergeSort?
Explanation / Answer
To Take MAtrix Input and Display it, Following program can be run:
import java.util.Scanner;
public class Matrix_Creation {
Scanner scan;
int matrix[][];
int row, column;
void create() {
scan = new Scanner(System.in);
System.out.println("Matrix Creation");
System.out.println(" Enter number of rows :");
row = Integer.parseInt(scan.nextLine());//provide value 4
System.out.println("Enter number of columns :");
column = Integer.parseInt(scan.nextLine());//provide value 3
matrix = new int[row][column];//creates matrix object
System.out.println("Enter the data :");
for(int i=0; i<row; i++) {
for(int j=0; j<column; j++) {
matrix[i][j] = scan.nextInt();
}
}//this for loop takes values of matrix
}
void display() {
System.out.println(" The Matrix is :");
for(int i=0; i<row; i++) {
for(int j=0; j<column; j++) {
System.out.print(" " + matrix[i][j]);
}
System.out.println();
}
}//this for loop displays the taken values of matrix
}
class MainClass {
public static void main(String args[]) {
Matrix_Creation obj = new Matrix_Creation();
obj.create();
obj.display();
}
}
Insertion sort Algo:
Step 1 If its the first element, it is already sorted. return 1;
Step 2 Go to the next element
Step 3 Compare with all elements in the sorted sub-list
Step 4 Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 Insert the value
Step 6 Repeat until list is sorted
a) Pseudo code for insertion sort explained with the help of Array:
procedure insertionSort( A : array of items )
int holePlace
int valueToBeInserted
for i = 1 to length(A) inclusive do:
/ select value to be inserted /
valueToBeInserted = A[i]
holePlace = i
/*locate hole place for the element to be inserted */
while holePlace > 0 and A[holePlace-1] > valueToBeInserted do:
A[holePlace] = A[holePlace-1]
holePlace = holePlace -1
end while
/ insert the number at hole place /
A[holePlace] = valueToBeInserted
end for
end procedure
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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.