How do I sort a small list of items based on a master sequence list of items?

Question

If I have a conceptual master list of items ordered by priority/sequence:

1. dog

2. cat

3. fish

4. bunny

5. hamster

And another list comes along with the values

["bunny", "dog", "fish"]

How do I sort the incoming list based on the master list? So, in this example, I would expect the second list to result in

["dog", "fish", "bunny"]

after it has been sorted.

I could manually write a function to implement this, but I feel like Java already would have some sort of built-in and optimized way to do this sort of thing. What is the best way to accomplish this type of list sorting in Java?

Related http://stackoverflow.com/questions/18129807/in-java-how-do-you-sort-one-list-based-on-another — Tunaki, Jun 13 '16 at 21:10
Use TreeSet<>(). It also implements Collection, like ArrayList<>(); You can add TreeSet to your ArrayList. TreeSet sorts Strings automatically. — LowLevel, Jun 13 '16 at 23:01

score 2 · Answer 1 · answered Jun 13 '16 at 21:02

Process the list into a map so that masterList.get("bunny") = 4, etc.

Write your own Comparator with

int compare(String a, String b) {
  return masterList.get(a) - masterList.get(b);
}

Any solution has to be O(# of items in the largest list) in the worst case because you will have to search the entire large list just to find the positions of the items in the list you are sorting.

Michael Markidis · Accepted Answer · 2016-06-13T21:14:56.300

What you can do is create a copy of the master and use the List#retainAll method to retain the ordering as it is in the master.

Example:

// Master list
List<String> master = new ArrayList<>(Arrays.asList("dog", "cat", "fish", "bunny", "hamster"));

// list to sort with respect to master      
List<String> listToSort = new ArrayList<>(Arrays.asList("bunny", "dog", "fish"));

// copy of master   
List<String> masterCopy = new ArrayList<>(master);

// keep only the items in masterCopy that are in the listToSort
masterCopy.retainAll(listToSort);

System.out.println(masterCopy);

Outputs:

[dog, fish, bunny]

How do I sort a small list of items based on a master sequence list of items?

2 Answers2