2D array sorting in Java
Sorting in 2D array sorting in Java is a technique for arranging the elements of a 2D array in a specific order.
Java Program to Sort the 2D Array Across Rows
Sort each row so that the first column for each row has the minimum element among their respective rows.
Example 1:
Input:
1 9 8 5 7 6 3 2 5 4 0 1 7 3 5 5 9 2 1 0 3 6 7 8 2
Output:
1 5 7 8 9 2 3 4 5 6 0 1 3 5 7 0 1 2 5 9 2 3 6 7 8
Example 2:
Input:
8 6 4 5 3 5 2 1 9 7 4 2 7 8 9 5
Output:
4 5 6 8 1 2 3 5 2 4 7 9 5 7 8 9
Approach: Using library function Arrays.sort()
The idea is to use Arrays.sort() for every matrix row.
Algorithm using library function Arrays.sort()
Step 1: Import all the necessary libraries.
Step 2: Sort individual rows one at a time.
Step 3: Apply the Arrays.sort() function.
Step 4: Print the sorted matrix and show it.
Filename: ArraySorting.java
import java.util.Arrays; public class ArraySorting { static int sortrowWise ( int array [][]) { for (int i =0; i< array.length; i++) Arrays.sort(array[i]); for (int i =0; i < array.length;i++) { for( int j=0; j < array[i].length; j++) System.out.print(array[i][j] + ""); System.out.println(); } return 0; } public static void main(String args[]){ int array[][] = { { 8,3,7,9,5}, { 7,4,3,1,6}, { 9,2,7,8,3}, { 4,7,9,2,0} }; sortrowWise(array); } }
Output:
35789 13467 23789 02479
Complexity analysis:
Time Complexity: O(r*c*log(c)) where r is rows and c is columns.
Space Complexity: O(1)
Java Program to Sort the 2D Array Across Columns
Sorting a 2D array across columns involves arranging the elements in each column in a specific order.
Example 1:
Input:
9 2 5 4 3 2 4 1 9 5 1 8 0 5 6 6 7 6 1 7
Output:
1 2 0 1 3 2 4 1 4 5 6 7 5 5 6 9 8 6 9 7
Example 2:
Input:
7 2 0 5 1 3 8 2 9 14 5 1 0 5 2 4 2 6 0 1
Output:
3 1 0 0 1 4 2 0 5 1 5 2 2 5 2 7 8 6 9 14
Approach: Using Vector class
The Vector class implements a growable array of objects. Although vectors are part of legacy classes, collections can use them efficiently. We may utilise all of the List interface's methods here because it implements the List interface and is included in java.util package. The 2D array is sorted across columns using this program. To sort each column, we shall make use of the vector notion.
Algorithm:
Step 1: Go through every column one by one.
Step 2: In vector v, add the elements from Column 1.
Step 3: Sort the vector.
Step 4: push back the vector elements that have been sorted to the column.
Step 5: Remove every element from the vector to make space for new sorting.
Step 6: Repeat the same way until all columns are completed.
Filename: ArraySorting1.java
import java.util.*; public class ArraySorting1 { public static void main(String[] args) throws java.lang.Exception{ int[][] array = { { 9, 2, 5, 4, 3 }, { 2, 4, 1, 9, 5 }, { 1, 8, 0, 5, 6 }, { 6, 7, 6, 1, 7 } }; System.out.println("Matrix before sorting\n"); for (int i = 0; i < 4; i++) { for (int j = 0; j < 5; j++) { System.out.print(array[i][j] + " "); } System.out.println(); } Vector<Integer> v = new Vector<>(); for (int i = 0; i < 5; i++) { for (int j = 0; j < 4; j++) { v.add(array[j][i]); } Collections.sort(v); for (int j = 0; j < 4; j++) { array[j][i] = v.get(j); } v.removeAll(v); } System.out.println("Matrix after sorting\n"); for (int i = 0; i < 4; i++) { for (int j = 0; j < 5; j++) { System.out.print(array[i][j] + " "); } System.out.println(); } } }
Output
Matrix before sorting 9 2 5 4 3 2 4 1 9 5 1 8 0 5 6 6 7 6 1 7 Matrix after sorting 1 2 0 1 3 2 4 1 4 5 6 7 5 5 6 9 8 6 9 7
Complexity analysis:
Time Complexity: O(r*c*log(c)) where r is rows and c is columns.
Space Complexity: O(1)