Ordenar enteros grandes

Dada una array de n enteros positivos donde cada entero puede tener dígitos hasta 10 ⁶ , imprima los elementos de la array en orden ascendente. 
 

Input: arr[] = {54, 724523015759812365462, 870112101220845, 8723} 
Output: 54 8723 870112101220845 724523015759812365462
Explanation:
All elements of array are sorted in non-descending(i.e., ascending)
order of their integer value

Input: arr[] = {3643641264874311, 451234654453211101231,
                4510122010112121012121}
Output: 3641264874311 451234654453211101231 4510122010112121012121

Un enfoque ingenuo es utilizar un tipo de datos de precisión arbitraria, como int en python o la clase Biginteger en Java. Pero ese enfoque no será fructífero porque la conversión interna de string a int y luego realizar la clasificación conducirá a ralentizar los cálculos de suma y multiplicación en el sistema numérico binario.
Solución eficiente: como el tamaño del entero es muy grande, incluso no puede caber en un tipo de datos largo y largo de C/C++, por lo que solo necesitamos ingresar todos los números como strings y ordenarlos usando una función de comparación. Los siguientes son los puntos clave de la función de comparación: – 
 

1. Si las longitudes de dos strings son diferentes, entonces debemos comparar las longitudes para decidir el orden de clasificación.
2. Si las longitudes son iguales, solo necesitamos comparar ambas strings en orden lexicográfico.

Suposición: No hay ceros a la izquierda.
 

// Below is C++ code to sort the Big integers in
// ascending order
#include<bits/stdc++.h>
using namespace std;
 
// comp function to perform sorting
bool comp(const string &left, const string &right)
{
    // if length of both string are equals then sort
    // them in lexicographically order
    if (left.size() == right.size())
        return left < right;
 
    // Otherwise sort them according to the length
    // of string in ascending order
    else
        return left.size() < right.size();
}
 
// Function to sort arr[] elements according
// to integer value
void SortingBigIntegers(string arr[], int n)
{
    // Copy the arr[] elements to sortArr[]
    vector<string> sortArr(arr, arr + n);
 
    // Inbuilt sort function using function as comp
    sort(sortArr.begin(), sortArr.end(), comp);
 
    // Print the final sorted array
    for (auto &ele : sortArr)
        cout << ele << " ";
}
 
// Driver code of above implementation
int main()
{
    string arr[] = {"54", "724523015759812365462",
                    "870112101220845", "8723"};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    SortingBigIntegers(arr, n);
 
    return 0;
}

# Below is Python code to sort the Big integers
# in ascending order
def SortingBigIntegers(arr, n):
   
  # Direct sorting using lambda operator
  # and length comparison
  arr.sort(key = lambda x: (len(x), x))
 
# Driver code of above implementation
arr = ["54", "724523015759812365462",
        "870112101220845", "8723"]
n = len(arr)
 
SortingBigIntegers(arr, n)
 
# Print the final sorted list using
# join method
print " ".join(arr)

<script>
// Below is Javascript code to sort the Big integers in
// ascending order
 
// comp function to perform sorting
function comp(left, right)
{
 
    // if length of both string are equals then sort
    // them in lexicographically order
    if (left.length == right.length)
        return left < right;
 
    // Otherwise sort them according to the length
    // of string in ascending order
    else
        return left.length - right.length;
}
 
// Function to sort arr[] elements according
// to integer value
function SortingBigIntegers(arr, n)
{
 
    // Copy the arr[] elements to sortArr[]
    let sortArr = [...arr]
 
    // Inbuilt sort function using function as comp
 
    sortArr.sort(comp);
 
    // Print the final sorted array
    for (ele of sortArr)
        document.write(ele + " ");
}
 
// Driver code of above implementation
let arr = ["54", "724523015759812365462",
    "870112101220845", "8723"]
let n = arr.length
 
SortingBigIntegers(arr, n);
 
// This code is contributed by gfgking.
</script>

Output: 54 8723 870112101220845 724523015759812365462

Complejidad de tiempo: O(suma * log(n)) donde suma es la suma total de todas las longitudes de string y n es el tamaño de la array 
Espacio auxiliar: O(n)
Publicación similar: 
ordenar una array de números grandes
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.