Home > Net >  Sorting one list based on order defined in another list in Java 8
Sorting one list based on order defined in another list in Java 8

Time:12-16

I have this scenario where I have to sort listA based on the order of elements in listB.

But the problem I am facing is that if there is that if listA contains an element which is not defined in the listB then the sort result has all contents of listA sorted as per order in listB but the element which is not defined in listB as the first element.

Example

Input:

listA = [us,au,in,gb]
listB = [au,us,in]    // sort order list

Current Output:

listA = [gb,au,us,in]  // result after sorting

Expected Output:

listA = [au,us,in,gb]  // result after sorting

Here, since "gb" is not present in the sort list listB, the result has "gb" as the first element, but I want that to be the last element.

I am using the below code to sort the listA:

listA.sort(Comparator.comparingInt(listB::indexOf));

CodePudding user response:

It would be performance wise to generate a HashMap associating the string elements with the corresponding indices (i.e. Map<String,Integer>), instead of relaying on List.indexOf() method which performs iteration under the hood. And then define a Comparator based on this Map.

In order to place the elements that not are not present in the listB at the end of the sorted list, we can make use of the method Map.getOrDefault() providing the size of the map as a default value.

List<String> listA = new ArrayList<>(List.of("us","au","in","gb"));
List<String> listB = new ArrayList<>(List.of("au","us","in"));
        
Map<String, Integer> order = IntStream.range(0, listB.size())
    .boxed()
    .collect(Collectors.toMap(
        listB::get,
        Function.identity()
    ));
        
Comparator<String> comparator = Comparator.comparingInt(s -> order.getOrDefault(s, order.size()));
        
listA.sort(comparator);
    
System.out.println(listA);

Output:

[au, us, in, gb]

In case in you want to preserve the initial order of the elements in listA that are not present in the listB (i.e. group them at the very end of the list according to their initial ordering), you can generate an additional Map. This time based on the listA, which associate each element like gb with a unique Value greater or equal to the size of listB:

List<String> listA = new ArrayList<>(List.of("fr","us","nl","au","in","gb"));
List<String> listB = new ArrayList<>(List.of("au","us","in"));
        
Map<String, Integer> order = IntStream.range(0, listB.size())
    .boxed()
    .collect(Collectors.toMap(
        listB::get,
        Function.identity()
    ));
    
Map<String, Integer> resolver = IntStream.range(0, listA.size())
    .filter(i -> !order.containsKey(listA.get(i))) // to reduce the size of the Map
    .boxed()
    .collect(Collectors.toMap(
        listA::get,
        i -> i   order.size()
    ));
        
Comparator<String> comparator = Comparator.comparingInt(
    s -> order.getOrDefault(s, resolver.get(s))
);
        
listA.sort(comparator);

Output:

[au, us, in, fr, nl, gb]   // the order of "fr","nl","gb" is preserved

CodePudding user response:

just a quick hack but,

public class ExList extends ArrayList<String> {
    public int indexOf(String s) {
       int returnValue = super.indexOf(s);
       if ( returnValue == -1 ) {
           return size();
       }
       return returnValue;
    }
}

and create listB as instance of ExList, it would give you a desired result.

  • Related