Sorting Big Integers
Given a array of n positive integers where each integer can have digits upto 106, print the array elements in ascending order.
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
A naive approach is to use arbitrary precision data type such as int in python or Biginteger class in Java. But that approach will not be fruitful because internal conversion of string to int and then perform sorting will leads to slow down the calculations of addition and multiplications in binary number system.
C++
#include <algorithm> #include <iostream> #include <vector> int main() { // Taking input array std::vector< long long > arr = { 54, 724523015759812365462, 870112101220845, 8723 }; // Sorting the array in ascending order std::sort(arr.begin(), arr.end()); // Printing the sorted array for ( long long i : arr) { std::cout << i << std::endl; } return 0; } |
Java
import java.util.Arrays; import java.math.BigInteger; public class Main { public static void main(String[] args) { // Taking input array BigInteger[] arr = { new BigInteger( "54" ), new BigInteger( "724523015759812365462" ), new BigInteger( "870112101220845" ), new BigInteger( "8723" ) }; // Sorting the array in ascending order Arrays.sort(arr); // Printing the sorted array for (BigInteger i : arr) { System.out.println(i); } } } |
Python3
# Taking input array arr = [ 54 , 724523015759812365462 , 870112101220845 , 8723 ] # Sorting the array in ascending order arr.sort() # Printing the sorted array for i in arr: print (i) # Output: # 54 # 8723 # 870112101220845 # 724523015759812365462 # Note: The sorting is based on lexicographic order, i.e., based on |
C#
using System; using System.Collections.Generic; class Program { static void Main() { // Taking input array as strings List< string > arrStrings = new List< string > { "54" , "724523015759812365462" , "870112101220845" , "8723" }; // Sorting the array in ascending order arrStrings.Sort(); // Printing the sorted array foreach ( string str in arrStrings) { Console.WriteLine(str); } } } |
Javascript
// Taking input array let arr = [54, 724523015759812365462, 870112101220845, 8723]; // Sorting the array in ascending order arr.sort(); // Printing the sorted array for (let i = 0; i < arr.length; i++){ console.log(arr[i]); } |
54 8723 870112101220845 724523015759812365462
Efficient Solution : As size of integer is very large even it can’t be fit in long long data type of C/C++, so we just need to input all numbers as strings and sort them using a comparison function. Following are the key points compare function:-
- If lengths of two strings are different, then we need to compare lengths to decide sorting order.
- If Lengths are same then we just need to compare both the strings in lexicographically order.
Assumption : There are no leading zeros.
C++
// 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; } |
Java
import java.util.Arrays; import java.util.Comparator; public class Main { // comp function to perform sorting static class comp implements Comparator<String> { public int compare(String left, String right) { // if length of both string are equals then sort // them in lexicographically order if (left.length() == right.length()) { return left.compareTo(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 static void SortingBigIntegers(String[] arr, int n) { // Copy the arr[] elements to sortArr[] String[] sortArr = Arrays.copyOf(arr, n); // Inbuilt sort function using function as comp Arrays.sort(sortArr, new comp()); // Print the final sorted array for (String ele : sortArr) { System.out.print(ele + " " ); } } // Driver code of above implementation public static void main(String[] args) { String[] arr = { "54" , "724523015759812365462" , "870112101220845" , "8723" }; int n = arr.length; SortingBigIntegers(arr, n); } } |
Python
# 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) |
C#
using System; using System.Linq; using System.Collections.Generic; public class Program { // comp function to perform sorting public class Comp : IComparer< string > { public int Compare( string left, string right) { // if length of both string are equals then sort // them in lexicographically order if (left.Length == right.Length) { return String.Compare(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 public static void SortingBigIntegers( string [] arr, int n) { // Copy the arr[] elements to sortArr[] string [] sortArr = ( string [])arr.Clone(); // Inbuilt sort function using function as comp Array.Sort(sortArr, new Comp()); // Print the final sorted array foreach ( string ele in sortArr) { Console.Write(ele + " " ); } } // Driver code of above implementation public static void Main() { string [] arr = { "54" , "724523015759812365462" , "870112101220845" , "8723" }; int n = arr.Length; SortingBigIntegers(arr, n); } } |
Javascript
<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
Time complexity: O(sum * log(n)) where sum is the total sum of all string length and n is size of array
Auxiliary space: O(n)
Similar Post :
Sort an array of large numbers
Contact Us