Sorting non boundary elements – ISC Computer Science Practical 2016, Question 2

sorting non boundary elements

Write a program to declare a square matrix A[][] of order (M x M) where ‘M’ must be greater than 3 and less than 10. Allow the user to input positive integers into this matrix. Perform the following tasks on the matrix:

(a) Sort the non-boundary elements in ascending order using any standard sorting technique and rearrange them in the matrix.
(b) Calculate the sum of both the diagonals.
(c) Display the original matrix, rearranged matrix and only the diagonal elements of the rearranged matrix with their sum.

Test your program with the sample data and some random data:

Example 1

INPUT :M = 4
9   2   1   5   
8   13  8   4   
15  6   3   11  
7   12  23  8   

OUTPUT:

ORIGINAL MATRIX
9   2   1   5   
8   13  8   4   
15  6   3   11  
7   12  23  8   

REARRANGED MATRIX
9   2   1   5   
8   3   6   4   
15  8   13  11  
7   12  23  8   

DIAGONAL ELEMENTS
9           5   
    3   6       
    8   13      
7           8       

SUM OF THE DIAGONAL ELEMENTS = 59

Example 2

INPUT : 5
7	4	1	9	5
8	2	6	10	19
13	1	3	5	1
10	0	5	12	16
1	8	17	6	8
ORIGINAL MATRIX : 
	7	4	1	9	5
	8	2	6	10	19
	13	1	3	5	1
	10	0	5	12	16
	1	8	17	6	8
REARRANGED MATRIX : 
	7	4	1	9	5
	8	0	1	2	19
	13	3	5	5	1
	10	6	10	12	16
	1	8	17	6	8
DIAGONAL ELEMENTS : 
	7	 	 	 	5
	 	0	 	2	 
	 	 	5	 	 
	 	6	 	12	 
	1	 	 	 	8
SUM OF DIAGONAL ELEMENTS = 46

Example 3

INPUT : 13
OUTPUT: THE SIZE OF THE MATRIX IS OUT OF RANGE

An efficient Java implementation for sorting non boundary elements problem is as follows:

import java.util.*;
class Matrix{
    // sorting non boundary elements problem
    public static int[] bubbleSort( int a[] ){
        int temp;
        for(int i=0; i < a.length-1;i++){
            for(int x=0;x < a.length-i-1;x++){
                if(a[x+1] < a[x]){
                    temp=a[x];
                    a[x] = a[x+1];
                    a[x+1] = temp;
                }
            }
        }
        return a;
    }

    public static void displayMatrix(int A[][]){
        for( int row = 0 ; row < A.length; row++ ){
            for( int col = 0 ; col < A[ row ].length ; col++ ){
                System.out.print( "\t" + A[ row ][ col ]);
            }
            System.out.println();
        }
    }

    public static int displayMatrixDiagonals(int A[][]){
        int sumOfDiagonals=0;
        for( int row = 0 ; row < A.length; row++ ){
            for( int col = 0 ; col < A[ row ].length ; col++ ){
                System.out.print( "\t" );
                if( row == col || row == A.length - 1 - col ){ 
                    System.out.print(A[ row ][ col ]);
                    sumOfDiagonals += A[ row ][ col ];
                }else{ 
                    System.out.print( " " );
                }
            }
            System.out.println();
        }
        return sumOfDiagonals;
    }

    public static void main( String args[] ){
        Scanner sc = new Scanner( System.in );
        System.out.print( "INPUT : " );
        int M = sc.nextInt();
        if( M > 3 && M < 10 ){
            int A[][] = new int[M][M];
            int n[] = new int[ M*M - 2*M - 2*(M-2) ];
            int i=0;
            for( int row = 0 ; row < M; row++ ){
                for( int col = 0 ; col < M ; col++ ){
                    A[ row ][ col ] = sc.nextInt();
                    //check for non-border elements
                    if( row > 0 && row < M-1 && col > 0 && col < M-1 ){
                        //store non border elements in array n
                        n[ i++ ] = A[ row ][ col ];
                        System.err.print(row+", "+col+"\t");
                    }

                }
            }
            System.out.println( "ORIGINAL MATRIX : " );
            displayMatrix( A );
            //sort the array n
            n = bubbleSort( n );
            //display(n);
            i=0;
            for( int row = 1 ; row < M - 1  ; row++ ){
                for( int col = 1 ; col < M - 1  ; col++ ){
                    A[ row ][ col ] = n[ i++ ];
                }
            }
            
            System.out.println( "REARRANGED MATRIX : " );
            displayMatrix( A );
            System.out.println( "DIAGONAL ELEMENTS : " );
            int sumOfDiagonals = displayMatrixDiagonals(A);
            System.out.println( "SUM OF DIAGONAL ELEMENTS = " + sumOfDiagonals );
        }else{
            System.out.println( "OUTPUT: THE SIZE OF THE MATRIX IS OUT OF RANGE" );
        }
    }
}

Observe that the single dimension array used for sorting non boundary elements is populated while entering the double dimension array to save one set of nested loop. Also note that the sum of diagonals is being calculated while printing the diagonals to save redundant loops.

For details of the bubbeSort method refer to my earlier post on bubble sort.