Sorting a List of Objects based on a List of other Objects having common fields

This logic works correctly but I feel there might some faster or easier way to do this.

Your current solution utilizes a brute force approach, repeatedly checking the position of every protocol (which doesn't change) multiple times, and has a time complexity of O(n * m).

We can improve it by indexing the position of each protocol in a list.

UPDATE - Linear time solution

(covers examples containing duplicates added with the recent question update)

This solution is based on the simplest case solution provided earlier in this answer. And it would run in a linear time.

Current solution covers the following cases:

• list of sensors can be larger than the list of protocols;
• duplicates might appear in both lists;
• a sensor might have no matching pair in the list of protocols, and vice versa.

The resulting list of sensors expected to contain all sensors that have a matching pair, ordered accordingly to indices of their pairs in the list of protocols, and sensors having matching pair grouped at the end of the list accordingly to their initial order.

Assumption for the case of duplicates (based on the example data in the question):

• Let's consider there are 5 sensors and 2 protocols having the same properties. The 2 sensors would be ordered in accordance with the indices of 2 protocols. And the remained 3 sensors will be considered having no matching pair and would be placed at the end of the list.

In order to meet these conditions, array of sensors should be initialized to the maximum size of two lists. Some positions in the populated array could hold null values which have to be filtered.

As well as in the simplest case solution positions would be stored in the map.

To facilitate the ability to handle duplicates, we need to store all the positions of each protocol in a queue. So the map would be of type Map<String,Queue<Integer>>. And then while placing the sensors in to the array, required positions would be extracted from the queue one by one. If the queue is empty or there's no matching protocol (the call to the map will return null) then sensors would be added into a separate list which afterwards would be appended to the end of the resulting list.

Implementation:

Method responsible for creation of the map.

public static Map<String, Queue<Integer>> getPositions(List<Protocol> protocols) {

    Map<String, Queue<Integer>> positionByKey = new HashMap<>();

    for (int i = 0; i < protocols.size(); i++) {
        Protocol next = protocols.get(i);
        String key = getKey(next.getReferenceName(), next.getValue());
    
        positionByKey.computeIfAbsent(key, k -> new ArrayDeque<>()).add(i);
    }
    return positionByKey;
}

main()

public static void main(String[] args) {

    List<Protocol> protocols =
        List.of(new Protocol("343443678", "09866567897874334"),
                new Protocol("9876543", "009876546546534"),
                new Protocol("31543678", "09866546534"),
                new Protocol("41563678", "0663846546534"),
                new Protocol("343443678", "09866567897874334"),
                new Protocol("343443678", "09866567897874334"));
    
    List<Sensor> sensors =
        List.of(new Sensor("31543678", "09866546534"),
                new Sensor("41563678", "0663846546534"),
                new Sensor("343443678", "09866567897874334"),
                new Sensor("9876543", "009876546546534"),
                new Sensor("343443678", "09866567897874334"),
                new Sensor("343443678", "09866567897874334"),
                new Sensor("41563678", "0663846546534"),
                new Sensor("41563678", "0663846546534"),
                new Sensor("67534567", "66565656"));
    
    Map<String, Queue<Integer>> positionByKey = getPositions(protocols);

    Sensor[] orderedSensors = new Sensor[Math.max(sensors.size(), protocols.size())];
    List<Sensor> sensorsWithNoPair = new ArrayList<>();
    
    for (Sensor next : sensors) {
        String key = getKey(next.getReferenceName(), next.getValue());
        Queue<Integer> positions = positionByKey.get(key);
        
        if (positions == null || positions.isEmpty()) { // matching protocol doesn't exist at all, or we run out of indices in the queue
            sensorsWithNoPair.add(next);
            continue;
        }
        
        int position = positionByKey.get(key).remove();
        orderedSensors[position] = next;
    }

    List<Sensor> result = new ArrayList<>();
    
    for (Sensor next : orderedSensors) {
        if (next != null) result.add(next);
    }
    
    result.addAll(sensorsWithNoPair);
    // printing the result
    result.forEach(System.out::println);
}

Output:

Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=9876543, value=009876546546534]
Sensor [referenceName=31543678, value=09866546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=343443678, value=09866567897874334]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=41563678, value=0663846546534]
Sensor [referenceName=67534567, value=66565656]

A link to the Online Demo

The simplest case

Let's start with the simplest case that corresponds to the example of data you've provided:

• list of Protocols and list of Sensors are of the same size;
• each sensor has a matching pair (by referenceName and value) in the list of protocols;
• each combination of the referenceName and value is unique.

In this case, sorting can be done in linear time O(n).

We need a single iteration over the list of protocols to index the position of each protocol. We can store it in the map.

And for that we need an intermediate object that would be used as a key. The simplest approach to obtain the key is to concatenate the referenceName and value. A more generalized approach will be to use a record (or class) for that purpose. For now, I'll go with the simplest one - a map Map<String,Integer>, index of each protocol by key.

The next step is to order the sensors in accordance with the map of indices. We can create an array of length equal to the size of the list of sensors, and then iterate over the list of sensors by placing every sensor at a position retrieved from a map.

In order to turn the array of sensors into a list, we can use static method List.of() available with Java 9, or Arrays.asList() for earlier versions.

That's how it might look like:

public static void main(String[] args) {
    List<Protocol> protocols =
        List.of(new Protocol("343443678", "09866567897874334"),
                new Protocol("41563678", "0663846546534"),
                new Protocol("31543678", "09866546534"),
                new Protocol("9876543", "009876546546534"));

    List<Sensor> sensors =
        List.of(new Sensor("31543678", "09866546534"),
                new Sensor("343443678", "09866567897874334"),
                new Sensor("41563678", "0663846546534"),
                new Sensor("9876543", "009876546546534"));

    Sensor[] orderedSensors = new Sensor[sensors.size()];
    Map<String, Integer> positionByKey = new HashMap<>();

    for (int i = 0; i < protocols.size(); i++) {
        Protocol next = protocols.get(i);
        positionByKey.put(getKey(next.getReferenceName(), next.getValue()), i);
    }

    for (Sensor next: sensors) {
        int position = positionByKey.get(getKey(next.getReferenceName(), next.getValue()));
        orderedSensors[position] = next;
    }
    
    List<Sensor> result = List.of(orderedSensors); // or for Java 8 and earlier Arrays.asList(orderedSensors);
}

public static String getKey(String first, String second) {
    return first + ":" + second;
}

General case

General case solution doesn't require any assumption, i.e. it should be capable to deal with the following scenarios:

• the sizes of the lists might be unequal;
• combinations of the referenceName and value are not guaranteed to be unique;
• a sensor might have no matching pair in the list of protocols.

The overall approach remains the same: we need to index the position of each protocol and store it in a map.

But we will not access this map directly, instead it will be used by the comparator. And in this solution, a custom object will be used as a key. To avoid the necessity to override equals and hashCode it's implemented as a Java 16 record:

public record Key(String first, String second) {
    
    public Key(Sensor item) {
        this(item.getReferenceName(), item.getValue());
    }
    
    public Key(Protocol item) {
        this(item.getReferenceName(), item.getValue());
    }
}

To create a comparator, first we have to build a map, and then we can make use of the static method Comparator.comparingInt:

public static Comparator<Sensor> compareByKey(List<Protocol> base) {
    
    Map<Key, Integer> orderByKey = new HashMap<>();
    
    for (int i = 0; i < base.size(); i++) {
        Protocol next = base.get(i);
        orderByKey.put(new Key(next), i);
    }
    
    return Comparator.comparingInt((Sensor item) ->
        orderByKey.getOrDefault(new Key(item), -1)); // sensors that have no matching pair in the list of protocols will be grouped at the beginning of the resulting list
}

The main method will require only one line to do the sorting because the comparator does all the heavy lifting. And because now we are dealing with the sorting, the time complexity would be linear-logarithmic.

public static void main(String[] args) {

    List<Protocol> protocols = // initializing the list of protocols
    List<Sensor> sensors =     // initializing the list of sensors
    
    List<Sensor> orderedSensors = new ArrayList<>(sensors); // making a defensive copy, omit this line it's not required to preserve the unsorted list of sensors

    orderedSensors.sort(compareByKey(protocols);
}

Note: that this approach can be generalized further by making use of generic type parameters, so that it would be possible to apply it to any pair of objects. That would require making the Key class generic, and the method responsible for generating the comparator in order to be able to extract the needed attributes from an arbitrary object should be provided with a couple of functions.

The key is obtaining order strategy from protocolList

1.Implement equals & hashCode for Protocol, e.g.,

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Protocol)) return false;
    Protocol protocol = (Protocol) o;
    return Objects.equals(getReferenceName(), protocol.getReferenceName()) && Objects.equals(getValue(), protocol.getValue());
}

@Override
public int hashCode() {
    return Objects.hash(getReferenceName(), getValue());
}

2.Sort sensorList using custom Comparator

sensorList.sort(Comparator.comparingInt(one -> protocolList.indexOf(new Protocol(one.getReferenceName(), one.getValue()))));

P.S.hashCode() is optional if u don't put Protocol into hash collections