How could I sort Employee list1 based on list2 by name property?

In addition, we need to maintain a list1 of unordered elements

Code:

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class SortEmployee {
    public static void main(String[] args) {
        List<Employee> list1 = Stream.of(
                        new Employee("Zach","Boston","Massachusetts"),
                        new Employee("Alex","Atlanta","Georgia"),
                        new Employee("Jijo","pleasanton","California"),
                        new Employee("Sai","Decatur","Texas"),
                        new Employee("Yohan","Cumming","Atlanta"),
                        new Employee("Agni","sula","Maine"),
                        new Employee("Bajan","Duluth","Ohio"))
                .collect(Collectors.toList());

        List<Employee> list2 = Stream.of(
                        new Employee("Alex","Atlanta","Georgia"),
                        new Employee("Sai","Decatur","Texas"),
                        new Employee("Musa","Fremont","California"),
                        new Employee("Zach","Boston","Massachusetts"),
                        new Employee("Bajan","Duluth","Rhode Island"),
                        new Employee("Khan","Kalan","Ohio"),
                        new Employee("Jijo","pleasanton","California"))
                .collect(Collectors.toList());

        System.out.println("##### List-1 ####");
        list1.forEach(System.out::println);
        System.out.println("##### List-2 ####");
        list2.forEach(System.out::println);
    }
}

Employee Object :

@Data
public class Employee {
    String name;
    String city;
    String state;
}

Expected output:

List1= 

 - Employee{name='Alex', city='Atlanta', state='Georgia'},
   Employee{name='Sai', city='Decatur', state='Texas'},
   Employee{name='Zach', city='Boston', state='Massachusetts'},
   Employee{name='Bajan', city='Duluth', state='Ohio'},
   Employee{name='Jijo', city='pleasanton', state='California'},
   Employee{name='Yohan', city='Cumming', state='Atlanta'},
   Employee{name='Agni', city='sula', state='Maine'}

CodePudding user response：

Naive approach

A naive way would be to create Comparator using comparingInt() by the logic for retrieving the indexed of the element with the matching name. And then apply sort() on the first list.

In case if equals() and hashCode() are not based on the name property only, we can create a wrapper class and implement its equals/hashCode contract in such a way that only name will be taken into account during comparison.

And then based on the list1 and list2 generate two lists EmployeeWrapper objects (the code below is incomplete and provided only to illustrate the idea).

public class EmployeeWrapper {
    private String name;
    private Employee employee;
    
    // getters, constructor, equals/hashCode
}

Comparator<EmployeeWrapper> comparator = Comparator.comparingInt(wrappedList2::indexOf);

wrappedList1.sort(comparator);

List<Employee> sortedList = wrappedList.stream()
    .map(EmployeeWrapper::getEmployee)
    .collect(Collectors.toList());

But it would be terribly inefficient to iterate over the second list multiple times. To be precise, time complexity would be O(m * n log n) (where n - number of elements in the first list, m - the size of the second list).

Storing indices in the Map

Since the positions of the elements in the second list don't change, we can index them in a single pass through the list and store it in the map. And then generate a comparator based on this map.

The time complexity would be O(m n log n) (it means the impact of the second list far more moderate).

public static Comparator<Employee> compareByName(List<Employee> base) {
    
    Map<String, Integer> indexByName = getIndexByName(base);
    
    return Comparator.comparingInt(employee ->
        indexByName.getOrDefault(employee.getName(), Integer.MAX_VALUE)); // employee that have no matching pair will be grouped at the end of the resulting list
}

public static Map<String, Integer> getIndexByName(List<Employee> list) {
    
    Map<String, Integer> indexByName = new HashMap<>();
    
    for (int i = 0; i < list.size(); i  ) {
        indexByName.putIfAbsent(list.get(i).getName(), i);
    }
    return indexByName;
}

main()

public static void main(String[] args) {

    List<Employee> list1 = // initialing the list

    List<Employee> list2 = // initialing the list

    Comparator<Employee> comparator = compareByName(list2);
    list1.sort(comparator);

    System.out.println("##### List-1 ####");
    list1.forEach(System.out::println);
    System.out.println("##### List-2 ####");
    list2.forEach(System.out::println);
}

In certain conditions, this code can be optimized further.

For instance, if there would be no duplicated names, it's possible to make it run in a linear time.