ISC Practicals and Theory - Row-wise and Column-wise Sorting

A matrix can be sorted in two ways: every row on its own, or every column on its own. This program, written in the main method alone, reads an m x n matrix, makes two separate copies of it, sorts every row of one copy and every column of the other in ascending order with bubble sort, and prints the original and both results.

Definition

Row-wise sorting arranges the elements of each row in ascending order, one row at a time; the rows stay in the same order, and elements never move from one row to another. Column-wise sorting arranges the elements of each column in ascending order from top to bottom, one column at a time. Ascending means each element is smaller than or equal to the one after it.

For the matrix with rows 9 2 7 and 1 8 6:

• sorted row-wise: 2 7 9 and 1 6 8
• sorted column-wise: 1 2 6 and 9 8 7

The two results are independent, so each sort is done on its own copy of the original. If the column sort were done on the already row-sorted matrix, the answer would be different. The numbers of rows and columns must each be from 2 to 10, otherwise the input is invalid.

Algorithm

1. Read the number of rows m and the number of columns n. If either is not from 2 to 10, print an error message and stop.
2. Read the elements of the matrix a row by row. The original a is never changed after the input.
3. Make two separate copies of a: rs for the row sort and cs for the column sort.
4. Row sort on rs: take one row i at a time and apply bubble sort to it. In each pass p, compare neighbours rs[i][q] and rs[i][q + 1] and swap them if the left one is larger.
5. Column sort on cs: take one column j at a time and apply bubble sort down the column, comparing cs[q][j] and cs[q + 1][j].
6. Print the original matrix, the row-sorted matrix and the column-sorted matrix.

Program

Everything is written inside main: the input, the copying, one triple loop for the rows, one triple loop for the columns, and three printing loops.

import java.util.Scanner;
public class MatrixSort
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of rows m (2 to 10): ");
        int m = sc.nextInt();                  // number of rows of the matrix
        if (m < 2 || m > 10)                   // rows out of range
        {
            System.out.println("Invalid number of rows");
            return;
        }
        System.out.print("Enter the number of columns n (2 to 10): ");
        int n = sc.nextInt();                  // number of columns of the matrix
        if (n < 2 || n > 10)                   // columns out of range
        {
            System.out.println("Invalid number of columns");
            return;
        }
        int a[][] = new int[m][n];             // stores the original matrix (never changed after input)
        System.out.println("Enter the elements of the matrix:");
        for (int i = 0; i < m; i++)            // i runs over the rows
        {
            for (int j = 0; j < n; j++)        // j runs over the columns
            {
                a[i][j] = sc.nextInt();
            }
        }
        int rs[][] = new int[m][n];            // copy of a[][] in which every row is sorted
        int cs[][] = new int[m][n];            // copy of a[][] in which every column is sorted
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                rs[i][j] = a[i][j];
                cs[i][j] = a[i][j];
            }
        }
        for (int i = 0; i < m; i++)                  // take one row at a time
        {
            for (int p = 0; p < n - 1; p++)          // number of passes
            {
                for (int q = 0; q < n - 1 - p; q++)  // compare neighbours in the row
                {
                    if (rs[i][q] > rs[i][q + 1])     // larger one moves right
                    {
                        int t = rs[i][q];
                        rs[i][q] = rs[i][q + 1];
                        rs[i][q + 1] = t;
                    }
                }
            }
        }
        for (int j = 0; j < n; j++)                  // take one column at a time
        {
            for (int p = 0; p < m - 1; p++)          // number of passes
            {
                for (int q = 0; q < m - 1 - p; q++)  // compare neighbours in the column
                {
                    if (cs[q][j] > cs[q + 1][j])     // larger one moves down
                    {
                        int t = cs[q][j];
                        cs[q][j] = cs[q + 1][j];
                        cs[q + 1][j] = t;
                    }
                }
            }
        }
        System.out.println("Original matrix:");
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                System.out.print(a[i][j] + "\t");   // tab between elements
            }
            System.out.println();                   // new line after each row
        }
        System.out.println("Rows sorted in ascending order:");
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                System.out.print(rs[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("Columns sorted in ascending order:");
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                System.out.print(cs[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

Variable description table

Sample input and output

Enter the number of rows m (2 to 10): 3
Enter the number of columns n (2 to 10): 4
Enter the elements of the matrix:
9 2 7 5
1 8 6 3
4 0 -2 5
Original matrix:
9	2	7	5	
1	8	6	3	
4	0	-2	5	
Rows sorted in ascending order:
2	5	7	9	
1	3	6	8	
-2	0	4	5	
Columns sorted in ascending order:
1	0	-2	3	
4	2	6	5	
9	8	7	5	

Enter the number of rows m (2 to 10): 2
Enter the number of columns n (2 to 10): 3
Enter the elements of the matrix:
5 5 5
5 5 5
Original matrix:
5	5	5	
5	5	5	
Rows sorted in ascending order:
5	5	5	
5	5	5	
Columns sorted in ascending order:
5	5	5	
5	5	5	

Enter the number of rows m (2 to 10): 3
Enter the number of columns n (2 to 10): 12
Invalid number of columns

Enter the number of rows m (2 to 10): 1
Invalid number of rows

Dry run

Take the first sample, $m = 3$ and $n = 4$. First the row 9 2 7 5 (row 0 of rs) is sorted by the row-sorting loops.

The sorted row is 2 5 7 9, the first row of the row-sorted output. Now column 3 of cs, which holds 5, 3, 5 from top to bottom, is sorted by the column-sorting loops.

The last column of the column-sorted output is therefore 3 5 5, the same as the first sample run.

Variations

1. Sort the whole matrix "Sort all the elements of a matrix in ascending order and display the sorted matrix."
2. Descending order "Sort every row of a matrix in descending order and display it."
3. Row sum and column sum "Display the sum of each row and each column of the matrix."