Numerically sorting the String Arrays

Question

I already know that we can sort string arrays numerically, by converting them to integer array then using Arrays.sort() or using any comparator.

So my question is if those strings are beyond the limit of integer or long int then how can we sort them. For example consider the following string array:

14829435897932384626433832795
4159265358979323846264338327
1937286535897932384626433832795296523
23746289

in those cases traditional comparator or any sorting method won't work because in turn they use integer (or any other datatype).

Option 1: BigInteger Option 2: compare by length first, if that is equal, compare as String — gaborsch
– gaborsch, Commented Nov 14, 2017 at 13:53
BigInteger seems a better option specifically for cases where the String can start with a bunch of zeros, e.g. 000133124953. Length comparison would be problematic here. — Everyone
– Everyone, Commented Nov 14, 2017 at 13:55
yes biginteger seems better . Thanks @Eran , @ GaborSch , @ Everyone — Sandip Kumar
– Sandip Kumar, Commented Nov 14, 2017 at 13:57
I would prefer option 2 (compare string length then compare as String) with a comparator that skips any leading zeros. It would probably be more efficient as you won't be creating new objects and allocating arrays to hold the BigInteger values. If readability is the only requirement, then use BigInteger. — Klitos Kyriacou
– Klitos Kyriacou, Commented Nov 14, 2017 at 14:02

Henrik Aasted Sørensen · Accepted Answer · 2017-11-15 06:50:51Z

9

As suggested by Eran: Convert to BigInteger and do the comparison:

Collections.sort(list, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        BigInteger bi1 = new BigInteger(o1);
        BigInteger bi2 = new BigInteger(o2);
        return bi1.compareTo(bi2);
    }
});

And because @tobias_k doesn't care about karma:

If you're running Java 8, you can use the many new default methods of the Comparator interface to do it in one line:

Arrays.sort(arr, Comparator.comparing(BigInteger::new))

Just added a counter to the Comparator to see how many times a String was converted to a BigInteger. It counted 10 conversions in my simple run of 4 strings.

This made me think that there might be a performance gain by converting each string once, sorting the BigInteger instances and converting them back. Something like this:

List<BigInteger> list1 = list.stream().map(BigInteger::new)
     .sorted().collect(Collectors.toList());

edited Nov 15, 2017 at 6:50

answered Nov 14, 2017 at 13:54

Henrik Aasted Sørensen

7,18811 gold badges55 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

tobias_k Over a year ago

Java 8: Arrays.sort(arr, Comparator.comparing(BigInteger::new))

Henrik Aasted Sørensen Over a year ago

@tobias_k: Nice! You should add that as answer.

tobias_k Over a year ago

Meh, it's basically the same. Feel free to add it to yours if you like.

azro · Accepted Answer · 2017-11-14 14:28:22Z

8

You can use Arrays.sort(array, comparator)

Arrays.sort(array, Comparator.comparing(BigInteger::new));

The comparator can take as parameter a function that maps an object into another one (here String into BigInteger)

With details (from shorter to longer, Intellij will propose you to use 1st one) : :

= Comparator.comparing(BigInteger::new)
= Comparator.comparing(val -> new BigInteger(val))
= Comparator.comparing((o1, o2) -> new BigInteger(o1).compareTo(new BigInteger(o2)))

String[] array = new String[]{"14829435897932384626433832795", 
                              "4159265358979323846264338327", 
                              "1937286535897932384626433832795296523", "23746289"};
Arrays.sort(array, Comparator.comparing(BigInteger::new));
System.out.println(Arrays.toString(array));

//Will result in 
[23746289, 4159265358979323846264338327, 14829435897932384626433832795, 1937286535897932384626433832795296523]

edited Nov 14, 2017 at 14:28

answered Nov 14, 2017 at 13:57

azro

54.2k9 gold badges38 silver badges75 bronze badges

3 Comments

Sandip Kumar Over a year ago

Its a great solution definately , but there are some efficiency issue with it .

azro Over a year ago

@SandipKumar details ?^^ You have a lot of String to convert and sort ?

Sandip Kumar Over a year ago

yep , the one which i have given are just sample ones , actual ones are way too larger .

Juan Carlos Mendoza · Accepted Answer · 2017-11-14 15:23:26Z

3

You can also create a custom comparator:

List<String> list = Arrays.asList("14829435897932384626433832795", "4159265358979323846264338327", "1937286535897932384626433832795296523", "23746289", "4159265358979323846264338326");

// comparing by String if the length is equal
Collections.sort(list, Comparator.comparingInt(String::length).thenComparing(String::compareTo));

System.out.println(list);

Output:

[23746289, 4159265358979323846264338326, 4159265358979323846264338327, 14829435897932384626433832795, 1937286535897932384626433832795296523]

edited Nov 14, 2017 at 15:23

answered Nov 14, 2017 at 14:05

Juan Carlos Mendoza

5,8547 gold badges28 silver badges50 bronze badges

3 Comments

gaborsch Over a year ago

As noted above, it works only if there are no leading zeros. But it we can assume it, this is the most effective. +1

Klitos Kyriacou Over a year ago

Arrays.sort(array, Comparator.comparingInt(String::length).thenComparing(String::compareTo));

Sandip Kumar Over a year ago

This was the exact solution i was looking for , it is correct as well as efficient , thanks .

Collectives™ on Stack Overflow

Numerically sorting the String Arrays

3 Answers 3

3 Comments

3 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related