Dada una array xn. El problema es ordenar la array por filas y por columnas.
Ejemplos:
Input : mat[][] = { {4, 1, 3},
{9, 6, 8},
{5, 2, 7} }
Output : 1 3 4
2 5 7
6 8 9
Input : mat[][] = { {12, 7, 1, 8},
{20, 9, 11, 2},
{15, 4, 5, 13},
{3, 18, 10, 6} }
Output : 1 5 8 12
2 6 10 15
3 7 11 18
4 9 13 20
Enfoque: Los siguientes son los pasos:
- Ordena cada fila de la array.
- Obtener la transpuesta de la array.
- Nuevamente ordene cada fila de la array.
- Nuevamente obtenga la transposición de la array.
Algoritmo para ordenar cada fila de array usando C++ STL sort():
for (int i = 0 ; i < n; i++)
sort(mat[i], mat[i] + n);
Algoritmo para obtener la transpuesta de la array:
for (int i = 0; i < n; i++) {
for (int j = i + 1; i < n; i++) {
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}
}
C++
// C++ implementation to sort the matrix row-wise
// and column-wise
#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 10
// function to sort each row of the matrix
void sortByRow(int mat[MAX_SIZE][MAX_SIZE], int n)
{
for (int i = 0; i < n; i++)
// sorting row number 'i'
sort(mat[i], mat[i] + n);
}
// function to find transpose of the matrix
void transpose(int mat[MAX_SIZE][MAX_SIZE], int n)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
// swapping element at index (i, j)
// by element at index (j, i)
swap(mat[i][j], mat[j][i]);
}
// function to sort the matrix row-wise
// and column-wise
void sortMatRowAndColWise(int mat[MAX_SIZE][MAX_SIZE],
int n)
{
// sort rows of mat[][]
sortByRow(mat, n);
// get transpose of mat[][]
transpose(mat, n);
// again sort rows of mat[][]
sortByRow(mat, n);
// again get transpose of mat[][]
transpose(mat, n);
}
// function to print the matrix
void printMat(int mat[MAX_SIZE][MAX_SIZE], int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << mat[i][j] << " ";
cout << endl;
}
}
// Driver program to test above
int main()
{
int mat[MAX_SIZE][MAX_SIZE] = { { 4, 1, 3 },
{ 9, 6, 8 },
{ 5, 2, 7 } };
int n = 3;
cout << "Original Matrix:\n";
printMat(mat, n);
sortMatRowAndColWise(mat, n);
cout << "\nMatrix After Sorting:\n";
printMat(mat, n);
return 0;
}
Java
// Java implementation to sort the
// matrix row-wise and column-wise
import java.util.Arrays;
class GFG
{
static final int MAX_SIZE=10;
// function to sort each row of the matrix
static void sortByRow(int mat[][], int n)
{
for (int i = 0; i < n; i++)
// sorting row number 'i'
Arrays.sort(mat[i]);
}
// function to find transpose of the matrix
static void transpose(int mat[][], int n)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
// swapping element at index (i, j)
// by element at index (j, i)
int temp=mat[i][j];
mat[i][j]=mat[j][i];
mat[j][i]=temp;
}
}
// function to sort the matrix row-wise
// and column-wise
static void sortMatRowAndColWise(int mat[][],int n)
{
// sort rows of mat[][]
sortByRow(mat, n);
// get transpose of mat[][]
transpose(mat, n);
// again sort rows of mat[][]
sortByRow(mat, n);
// again get transpose of mat[][]
transpose(mat, n);
}
// function to print the matrix
static void printMat(int mat[][], int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
System.out.print(mat[i][j] + " ");
System.out.println();
}
}
// Driver code
public static void main (String[] args)
{
int mat[][] = { { 4, 1, 3 },
{ 9, 6, 8 },
{ 5, 2, 7 } };
int n = 3;
System.out.print("Original Matrix:\n");
printMat(mat, n);
sortMatRowAndColWise(mat, n);
System.out.print("\nMatrix After Sorting:\n");
printMat(mat, n);
}
}
// This code is contributed by Anant Agarwal.
Python 3
# Python 3 implementation to
# sort the matrix row-wise
# and column-wise
MAX_SIZE = 10
# function to sort each
# row of the matrix
def sortByRow(mat, n):
for i in range (n):
# sorting row number 'i'
for j in range(n-1):
if mat[i][j] > mat[i][j + 1]:
temp = mat[i][j]
mat[i][j] = mat[i][j + 1]
mat[i][j + 1] = temp
# function to find
# transpose of the matrix
def transpose(mat, n):
for i in range (n):
for j in range(i + 1, n):
# swapping element at
# index (i, j) by element
# at index (j, i)
t = mat[i][j]
mat[i][j] = mat[j][i]
mat[j][i] = t
# function to sort
# the matrix row-wise
# and column-wise
def sortMatRowAndColWise(mat, n):
# sort rows of mat[][]
sortByRow(mat, n)
# get transpose of mat[][]
transpose(mat, n)
# again sort rows of mat[][]
sortByRow(mat, n)
# again get transpose of mat[][]
transpose(mat, n)
# function to print the matrix
def printMat(mat, n):
for i in range(n):
for j in range(n):
print(str(mat[i][j] ), end = " ")
print();
# Driver Code
mat = [[ 4, 1, 3 ],
[ 9, 6, 8 ],
[ 5, 2, 7 ]]
n = 3
print("Original Matrix:")
printMat(mat, n)
sortMatRowAndColWise(mat, n)
print("\nMatrix After Sorting:")
printMat(mat, n)
# This code is contributed
# by ChitraNayal
C#
// C# implementation to sort the
// matrix row-wise and column-wise
using System;
class GFG
{
// function to sort each
// row of the matrix
static void sortByRow(int [,]mat,
int n)
{
// sorting row number 'i'
for (int i = 0; i < n ; i++)
{
for(int j = 0;
j < n - 1; j++)
{
if(mat[i, j] > mat[i, j + 1])
{
var temp = mat[i, j];
mat[i, j] = mat[i, j + 1];
mat[i, j + 1] = temp;
}
}
}
}
// function to find transpose
// of the matrix
static void transpose(int [,]mat,
int n)
{
for (int i = 0; i < n; i++)
for (int j = i + 1;
j < n; j++)
{
// swapping element at
// index (i, j) by
// element at index (j, i)
var temp = mat[i, j];
mat[i, j] = mat[j, i];
mat[j, i] = temp;
}
}
// function to sort
// the matrix row-wise
// and column-wise
static void sortMatRowAndColWise(int [,]mat,
int n)
{
// sort rows of mat[,]
sortByRow(mat, n);
// get transpose of mat[,]
transpose(mat, n);
// again sort rows of mat[,]
sortByRow(mat, n);
// again get transpose of mat[,]
transpose(mat, n);
}
// function to print the matrix
static void printMat(int [,]mat, int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
Console.Write(mat[i, j] + " ");
Console.Write("\n");
}
}
// Driver code
public static void Main ()
{
int [,]mat = {{4, 1, 3},
{9, 6, 8},
{5, 2, 7}};
int n = 3;
Console.Write("Original Matrix:\n");
printMat(mat, n);
sortMatRowAndColWise(mat, n);
Console.Write("\nMatrix After Sorting:\n");
printMat(mat, n);
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP implementation to sort
// the matrix row-wise and
// column-wise
$MAX_SIZE = 10;
// function to sort each
// row of the matrix
function sortByRow(&$mat, $n)
{
for ($i = 0; $i < $n; $i++)
// sorting row number 'i'
sort($mat[$i]);
}
// function to find
// transpose of the matrix
function transpose(&$mat, $n)
{
for ($i = 0; $i < $n; $i++)
{
for ($j = $i + 1;
$j < $n; $j++)
{
// swapping element at index (i, j)
// by element at index (j, i)
$t = $mat[$i][$j];
$mat[$i][$j] = $mat[$j][$i];
$mat[$j][$i] = $t;
}
}
}
// function to sort
// the matrix row-wise
// and column-wise
function sortMatRowAndColWise(&$mat, $n)
{
// sort rows of mat[][]
sortByRow($mat, $n);
// get transpose of mat[][]
transpose($mat, $n);
// again sort rows of mat[][]
sortByRow($mat, $n);
// again get transpose of mat[][]
transpose($mat, $n);
}
// function to print the matrix
function printMat(&$mat, $n)
{
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
echo $mat[$i][$j] . " ";
echo "\n";
}
}
// Driver Code
$mat = array(array( 4, 1, 3 ),
array( 9, 6, 8 ),
array( 5, 2, 7 ));
$n = 3;
echo "Original Matrix:\n";
printMat($mat, $n);
sortMatRowAndColWise($mat, $n);
echo "\nMatrix After Sorting:\n";
printMat($mat, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript implementation to sort the
// matrix row-wise and column-wise
let MAX_SIZE=10;
// function to sort each row of the matrix
function sortByRow(mat,n)
{
for (let i = 0; i < n; i++)
// sorting row number 'i'
mat[i].sort(function(a,b){return a-b;});
}
// function to find transpose of the matrix
function transpose(mat,n)
{
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
{
// swapping element at index (i, j)
// by element at index (j, i)
let temp=mat[i][j];
mat[i][j]=mat[j][i];
mat[j][i]=temp;
}
}
// function to sort the matrix row-wise
// and column-wise
function sortMatRowAndColWise(mat,n)
{
// sort rows of mat[][]
sortByRow(mat, n);
// get transpose of mat[][]
transpose(mat, n);
// again sort rows of mat[][]
sortByRow(mat, n);
// again get transpose of mat[][]
transpose(mat, n);
}
// function to print the matrix
function printMat(mat,n)
{
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++)
document.write(mat[i][j] + " ");
document.write("<br>");
}
}
// Driver code
let mat = [[ 4, 1, 3 ],
[ 9, 6, 8 ],
[ 5, 2, 7 ]];
let n = 3;
document.write("Original Matrix:<br>");
printMat(mat, n);
sortMatRowAndColWise(mat, n);
document.write("\nMatrix After Sorting:<br>");
printMat(mat, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Original Matrix: 4 1 3 9 6 8 5 2 7 Matrix After Sorting: 1 3 4 2 5 7 6 8 9
Complejidad temporal: O(n 2 log 2 n).
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA