ISC Practicals and Theory - Row-wise and Column-wise Sorting (OOP)

This version of the matrix sorting program is built around a class. A parameterised constructor receives the number of rows and columns and creates the arrays, and each method does one job: reading, copying, sorting rows, sorting columns and displaying. The program sorts every row of one copy and every column of another copy of an m x n matrix in ascending order with bubble sort, and prints the original and both results.

Definition

Row-wise sorting puts the elements of each row in ascending order, one row at a time. Column-wise sorting puts the elements of each column in ascending order from top to bottom, one column at a time. For the rows 9 2 7 and 1 8 6, row-wise gives 2 7 9 and 1 6 8, and column-wise gives 1 2 6 and 9 8 7. Each sort works on its own copy of the original so the two results are independent. The numbers of rows and columns must each be from 2 to 10.

Algorithm

1. In main, read the number of rows into rows. If it is less than 2 or more than 10, print Invalid number of rows and stop.
2. Read the number of columns into cols. If it is less than 2 or more than 10, print Invalid number of columns and stop.
3. Create the object with new MatrixSort(rows, cols). The constructor stores m and n and creates the arrays a, rs and cs of size m x n.
4. Call readMatrix() to read the elements into a.
5. Call makeCopies() to copy every element of a into both rs and cs.
6. Call sortRows(). For each row i of rs, bubble sort runs:
   • the pass counter p runs from 0 to n - 2;
   • q runs from 0 to n - 2 - p;
   • if rs[i][q] > rs[i][q+1] the two are swapped using t.
7. Call sortColumns(). For each column j of cs, the same bubble sort runs down the column, with p up to m - 2 and q up to m - 2 - p.
8. Print a, rs and cs with display() under their headings.

Program

The constructor sets up the arrays, readMatrix() reads the elements, makeCopies() duplicates the original, sortRows() and sortColumns() sort the copies, and display() prints a matrix.

import java.util.Scanner;
/**
 * Class MatrixSort (OOP version) stores an m x n matrix and builds two
 * sorted copies of it: one with every row sorted in ascending order and
 * one with every column sorted in ascending order. The original is kept
 * unchanged.
 */
public class MatrixSort
{
    int a[][];    // stores the original matrix (never changed after input)
    int rs[][];   // copy of a[][] in which every row is sorted
    int cs[][];   // copy of a[][] in which every column is sorted
    int m;        // number of rows of the matrix
    int n;        // number of columns of the matrix

    /**
     * Parameterised constructor.
     * mm is the number of rows, nn the number of columns.
     * Stores them and creates the three m x n arrays.
     */
    MatrixSort(int mm, int nn)
    {
        m = mm;
        n = nn;
        a = new int[m][n];
        rs = new int[m][n];
        cs = new int[m][n];
    }

    /**
     * Reads the m x n elements into a[][].
     */
    void readMatrix(Scanner sc)
    {
        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();
            }
        }
    }

    /**
     * Copies a[][] into both rs[][] and cs[][], element by element,
     * so each sorting works on its own copy.
     */
    void makeCopies()
    {
        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];
            }
        }
    }

    /**
     * Sorts every row of rs[][] in ascending order by bubble sort.
     */
    void sortRows()
    {
        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;
                    }
                }
            }
        }
    }

    /**
     * Sorts every column of cs[][] in ascending order by bubble sort.
     */
    void sortColumns()
    {
        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;
                    }
                }
            }
        }
    }

    /**
     * Prints the m x n matrix x[][] row by row.
     */
    void display(int x[][])
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                System.out.print(x[i][j] + "\t");   // tab between elements
            }
            System.out.println();                   // new line after each row
        }
    }

    /**
     * main reads and checks m and n, creates the object
     * and calls the methods in order.
     */
    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 rows = sc.nextInt();
        if (rows < 2 || rows > 10)            // rows out of range
        {
            System.out.println("Invalid number of rows");
        }
        else
        {
            System.out.print("Enter the number of columns n (2 to 10): ");
            int cols = sc.nextInt();
            if (cols < 2 || cols > 10)        // columns out of range
            {
                System.out.println("Invalid number of columns");
            }
            else
            {
                MatrixSort obj = new MatrixSort(rows, cols);
                obj.readMatrix(sc);
                obj.makeCopies();
                obj.sortRows();
                obj.sortColumns();
                System.out.println("Original matrix:");
                obj.display(obj.a);
                System.out.println("Rows sorted in ascending order:");
                obj.display(obj.rs);
                System.out.println("Columns sorted in ascending order:");
                obj.display(obj.cs);
            }
        }
    }
}

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 sortRows().

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 sortColumns().

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."