Ordenar array 2D lexicográficamente

Dada una array 2D arr[] que tiene N filas de tamaño variable, la tarea es ordenar la array en orden lexicográfico, es decir, ordenar lexicográficamente cada fila y luego ordenar esas filas ordenadas.

Ejemplos:

Entrada: arr[][] = { {23}, {59}, {23, 59} }
Salida: { {23}, {23, 59}, {59} }
Explicación: Las filas están ordenadas lexicográficamente.
Aquí, la fila {23, 59} es lexicográficamente más pequeña que {59} 
porque el primer elemento (23) es más pequeño que 59.
Aunque {23} y {23, 59} tienen 23 como primer elemento, {23} solo tiene un elemento
Por lo tanto, {23} es lexicográficamente más pequeño que {23, 59}

Entrada: arr[][] ={ {3, 2, 5, 6}, {1, 2, 3}, {6, 3}, {5, 4, 2} } Salida: { {1, 2
, 3 }, {2, 3, 5, 6}, {2, 4, 5}, {3, 6} }

Entrada: arr[][] = { {3, 2, 5, 6}, {, 2, 3, 5}, {2, 4, 2, 1}, {6, 3, 7, 8} } Salida
: { {1, 2, 2, 4}, {1, 2, 3, 5}, {2, 3, 5, 6}, {3, 6, 7, 8} }

 

Planteamiento: La idea para resolver el problema es la siguiente: 

El orden lexicográfico más pequeño se puede obtener ordenando los elementos de cada fila y luego ordenando toda la array 2D según el orden lexicográfico de los elementos en cada fila.

Siga los pasos a continuación para resolver este problema:

  • Primero, ordene lexicográficamente cada fila de la array 2D dada.
  • Ordene toda la array 2D según el orden lexicográfico de los elementos de cada fila. La fila que sea lexicográficamente más pequeña llegará primero en la array ordenada.
  • Imprima la array 2D.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort the 2D array
// lexicographically
void sort_lexicographically(vector<vector<int> >& arr)
{
    for (int i = 0; i < arr.size(); ++i) {
 
        // Initially sorting the array row-wise
        sort(arr[i].begin(), arr[i].end());
    }
 
    // Sort the whole array in lexicographically
    sort(arr.begin(), arr.end());
}
 
// Driver's code
int main()
{
    vector<vector<int> > arr
        = { { 3, 2, 5, 6 }, { 1, 2, 3 }, { 5, 4, 2 }, { 6, 3 }, { 9, 99 }, { 6, 3, 2 } };
    sort_lexicographically(arr);
 
    // Resultant 2-d array after
    // sorting lexicographically
    for (int i = 0; i < arr.size(); ++i) {
        for (int j = 0; j < arr[i].size();
             ++j) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
    // Function to sort the 2D array
    // lexicographically
    public static void sort_lexicographically(int arr[][])
    {
        for (int i = 0; i < arr.length; ++i) {
 
            // Initially sorting the array row-wise
            Arrays.sort(arr[i]);
        }
 
        // Sort the whole array in lexicographically
        Arrays.sort(arr,
                    (a, b) -> Integer.compare(a[0], b[0]));
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[][]
            = { { 3, 2, 5, 6 }, { 1, 2, 3 }, { 6, 3 },
                { 9, 99 },      { 6, 3, 2 }, { 5, 4, 2 } };
        sort_lexicographically(arr);
 
        // Resultant 2-d array after
        // sorting lexicographically
        for (int i = 0; i < arr.length; ++i) {
            for (int j = 0; j < arr[i].length; ++j) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python program for above approach
   
# Function to sort the 2D array
# lexicographically
def sort_lexicographically(arr) :
     
    for i in range(0, len(arr)) :
 
        # Initially sorting the array row-wise
        arr[i].sort()
     
 
    # Sort the whole array in lexicographically
    arr.sort()
 
 
# Driver code
if __name__ == "__main__":
     
    arr = [[ 3, 2, 5, 6 ], [ 1, 2, 3 ], [ 5, 4, 2 ], [ 6, 3 ], [ 9, 99 ], [ 6, 3, 2 ]]
    sort_lexicographically(arr)
 
    # Resultant 2-d array after
    # sorting lexicographically
    for i in range(0, len(arr)) :
        for j in range(0, len(arr[i])) :
            print(arr[i][j] , end = " ")
         
        print()
 
        # This code is contributed by code_hunt.

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to sort the 2D array
  // lexicographically
  public static void sort_lexicographically(int[][] arr)
  {
    for (int i = 0 ; i < arr.Length ; ++i) {
 
      // Initially sorting the array row-wise
      Array.Sort(arr[i]);
    }
 
    // Sort the whole array in lexicographically
    Array.Sort(arr, new comp());
  }
 
  public static void Main(string[] args){
 
    int[][] arr = new int[][]{
      new int[]{ 3, 2, 5, 6 },
      new int[]{ 1, 2, 3 },
      new int[]{ 6, 3 },
      new int[]{ 9, 99 },
      new int[]{ 6, 3, 2 },
      new int[]{ 5, 4, 2 }
    };
    sort_lexicographically(arr);
 
    // Resultant 2-d array after
    // sorting lexicographically
    for (int i = 0 ; i < arr.Length ; ++i) {
      for (int j = 0 ; j < arr[i].Length ; ++j) {
        Console.Write(arr[i][j] + " ");
      }
      Console.WriteLine("");
    }
 
  }
}
 
class comp : IComparer<int[]>{
  public int Compare(int[] a1, int[] a2){
    return a1[0]-a2[0];
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

<script>
// JavaScript code to implement the approach
 
// Function to sort the 2D array
// lexicographically
function sort_lexicographically(arr)
{
    for (var i = 0; i < arr.length; i++)
     
        // Initially sorting the array row-wise
        arr[i].sort();
         
    // Sort the whole array in lexicographically
    arr.sort();
}
 
// Driver's code
arr = [ [ 3, 2, 5, 6 ], [ 1, 2, 3 ], [ 5, 4, 2 ],
[ 6, 3 ], [ 9, 99 ], [ 6, 3, 2 ]];
sort_lexicographically(arr);
 
// Resultant 2-d array after
// sorting lexicographically
for (var i = 0; i < arr.length; ++i)
{
    for (var j = 0; j < arr[i].length; ++j)
    {
        document.write(arr[i][j] + " ");
    }
    document.write("\n");
}
     
// This code is contributed by phasing17
</script>
Producción

1 2 3 
2 3 5 6 
2 3 6 
2 4 5 
3 6 
9 99 

Complejidad del tiempo:
Espacio Auxiliar:

Publicación traducida automáticamente

Artículo escrito por mkrishnasai y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *