Row Sorting

Problem Statement

Write a Java program that implements a method to sort each row of a jagged array (a 2D array where each row can have a different length) independently in ascending order. The program should modify the jagged array in-place and test the implementation with jagged arrays containing rows of different lengths, including edge cases like empty matrices, matrices with empty rows, and matrices with rows of varying lengths. You can visualize this as organizing books on multiple shelves of different lengths, where each shelf’s books are sorted by size without affecting other shelves.

Input: A jagged 2D array of integers, where each row may have a different length (e.g., matrix = {{4, 2, 1}, {3, 5}, {6, 0, 8, 7}}). Output: The same jagged array with each row sorted in ascending order (e.g., {{1, 2, 4}, {3, 5}, {0, 6, 7, 8}}). Constraints:

• The number of rows is between 0 and 100.
• Each row’s length is between 0 and 100.
• Elements are integers between -10^4 and 10^4.
• The matrix may be empty or contain empty or null rows. Example:
• Input: matrix = {{4, 2, 1}, {3, 5}, {6, 0, 8, 7}}
• Output: {{1, 2, 4}, {3, 5}, {0, 6, 7, 8}}
• Explanation: Each row is sorted independently: [4, 2, 1] → [1, 2, 4], [3, 5] → [3, 5], [6, 0, 8, 7] → [0, 6, 7, 8].
• Input: matrix = {{}, {1}, {3, 2}}
• Output: {{}, {1}, {2, 3}}
• Explanation: Empty row stays empty, single-element row stays unchanged, and [3, 2] → [2, 3].

Pseudocode

FUNCTION sortRows(matrix)
    IF matrix is null OR matrix is empty THEN
        RETURN
    ENDIF
    FOR each row in matrix
        IF row is not null THEN
            SORT row in ascending order
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testMatrices to jagged 2D arrays
    FOR each matrix in testMatrices
        PRINT original matrix
        CALL sortRows(matrix)
        PRINT sorted matrix
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Check if the input matrix is null or empty. If so, return without modifying anything.
2. Iterate through each row of the matrix: a. If the row is not null, sort it in ascending order using a sorting function.
3. The matrix is modified in-place, with each row sorted independently.
4. In the main method, create test matrices with varying row lengths and call sortRows to verify correctness, printing the matrix before and after sorting.

Java Implementation

import java.util.Arrays;

public class RowSorting {
    // Sorts each row of a jagged array independently in ascending order
    public void sortRows(int[][] matrix) {
        // Check for null or empty matrix
        if (matrix == null || matrix.length == 0) {
            return;
        }
        // Iterate through each row
        for (int[] row : matrix) {
            // Sort non-null rows
            if (row != null) {
                Arrays.sort(row);
            }
        }
    }

    // Main method to test sortRows with various inputs
    public static void main(String[] args) {
        RowSorting sorter = new RowSorting();

        // Test case 1: Jagged matrix with different row lengths
        int[][] matrix1 = {{4, 2, 1}, {3, 5}, {6, 0, 8, 7}};
        System.out.println("Test case 1:");
        System.out.println("Before sorting:");
        printMatrix(matrix1);
        sorter.sortRows(matrix1);
        System.out.println("After sorting:");
        printMatrix(matrix1);

        // Test case 2: Matrix with empty and single-element rows
        int[][] matrix2 = {{}, {1}, {3, 2}};
        System.out.println("\nTest case 2:");
        System.out.println("Before sorting:");
        printMatrix(matrix2);
        sorter.sortRows(matrix2);
        System.out.println("After sorting:");
        printMatrix(matrix2);

        // Test case 3: Matrix with all zeros
        int[][] matrix3 = {{0, 0}, {0}, {0, 0, 0}};
        System.out.println("\nTest case 3:");
        System.out.println("Before sorting:");
        printMatrix(matrix3);
        sorter.sortRows(matrix3);
        System.out.println("After sorting:");
        printMatrix(matrix3);

        // Test case 4: Matrix with negative numbers
        int[][] matrix4 = {{-3, -1, -2}, {-5}, {-4, -6, -7}};
        System.out.println("\nTest case 4:");
        System.out.println("Before sorting:");
        printMatrix(matrix4);
        sorter.sortRows(matrix4);
        System.out.println("After sorting:");
        printMatrix(matrix4);

        // Test case 5: Null matrix
        int[][] matrix5 = null;
        System.out.println("\nTest case 5:");
        System.out.println("Before sorting:");
        printMatrix(matrix5);
        sorter.sortRows(matrix5);
        System.out.println("After sorting:");
        printMatrix(matrix5);
    }

    // Helper method to print jagged matrix
    private static void printMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            System.out.println("null");
            return;
        }
        System.out.println("[");
        for (int i = 0; i < matrix.length; i++) {
            System.out.print("  [");
            if (matrix[i] == null || matrix[i].length == 0) {
                System.out.print("]");
            } else {
                for (int j = 0; j < matrix[i].length; j++) {
                    System.out.print(matrix[i][j]);
                    if (j < matrix[i].length - 1) {
                        System.out.print(", ");
                    }
                }
                System.out.print("]");
            }
            System.out.println();
        }
        System.out.println("]");
    }
}

Output

Running the main method produces:

Test case 1:
Before sorting:
[
  [4, 2, 1]
  [3, 5]
  [6, 0, 8, 7]
]
After sorting:
[
  [1, 2, 4]
  [3, 5]
  [0, 6, 7, 8]
]

Test case 2:
Before sorting:
[
  []
  [1]
  [3, 2]
]
After sorting:
[
  []
  [1]
  [2, 3]
]

Test case 3:
Before sorting:
[
  [0, 0]
  [0]
  [0, 0, 0]
]
After sorting:
[
  [0, 0]
  [0]
  [0, 0, 0]
]

Test case 4:
Before sorting:
[
  [-3, -1, -2]
  [-5]
  [-4, -6, -7]
]
After sorting:
[
  [-3, -2, -1]
  [-5]
  [-7, -6, -4]
]

Test case 5:
Before sorting:
null
After sorting:
null

Explanation:

• Test case 1: Sorts rows [4, 2, 1] → [1, 2, 4], [3, 5] → [3, 5], [6, 0, 8, 7] → [0, 6, 7, 8].
• Test case 2: Empty row stays empty, [1] stays [1], [3, 2] → [2, 3].
• Test case 3: Rows of zeros remain unchanged.
• Test case 4: Sorts rows with negatives: [-3, -1, -2] → [-3, -2, -1], [-5] → [-5], [-4, -6, -7] → [-7, -6, -4].
• Test case 5: Null matrix remains unchanged.

How It Works

• Step 1: The sortRows method checks if the matrix is null or empty. For {{4, 2, 1}, {3, 5}, {6, 0, 8, 7}}, it proceeds.
• Step 2: Iterate through rows:
  • Row 0: [4, 2, 1] → sort to [1, 2, 4].
  • Row 1: [3, 5] → sort to [3, 5] (already sorted).
  • Row 2: [6, 0, 8, 7] → sort to [0, 6, 7, 8].
• Example Trace: For test case 1, each row is sorted independently using Arrays.sort, modifying the matrix in-place.
• Main Method: Tests with jagged matrices of varying row lengths, including empty rows, all zeros, negative numbers, and a null matrix, printing before and after sorting.
• Sorting Property: Each row is sorted independently, preserving the jagged structure and handling varying lengths.

Complexity Analysis Table

Note:

• r_i is the length of the i-th row, r_max is the maximum row length.
• Time complexity: O(Σ(r_i * log r_i)), where each row of length r_i is sorted using Arrays.sort (Timsort, O(r_i * log r_i)). The total is the sum over all rows.
• Space complexity: O(log r_max), as Timsort uses O(log r_i) space for each row, and the maximum row length dominates.
• Worst case: O(N * log N) where N is the total number of elements if one row contains all elements.

✅ Tip: Use Arrays.sort for efficient row sorting. Test with empty rows, single-element rows, and negative numbers to ensure robustness across different jagged array configurations.

⚠ Warning: Check for null rows to avoid NullPointerException. Ensure the matrix is not null to prevent unexpected behavior during sorting.