Re-order ArrayList Based on String Array's Order - Java

Question

I have one arraylist and one String array. The String array contains IDs and the Array List contains the ids and information related to those Ids. This ArrayList is in an undesirable order. I have a String Array of the Ids in the order in which I want them to be in the ArrayList.

Semi-Pseudocode Example:

ArrayList<MyObject> myList = new ArrayList<MyObject>();
for (every username)
{
    myList.add(new MyObject(id, username, content, country);
}

String[] ids = new String[myList.size()];
...Ids are added and sorted here...

I now have a list of Ids, in their correct order. Each Id in "myList" corresponds to an Id in the "ids" String Array. I want to sort "myList" based on the order of it's corresponding id in the "ids" String Array.

How can I re-sort my ArrayList in such a way?

Eg. if in Array list I have:

1. 123, Bob, test, USA
2. 1234, Vladimir, test, USA
3. 12345, Yoseph, test, USA

and in the String[] I have:

1. 1234
2. 123
3.12345

How can I reorder the ArrayList based off of the Ids in the String Array, thus producing:

1. 1234, Vladimir, test, USA
2. 123, Bob, test, USA
3. 12345, Yoseph, test, USA

Answer 1

One solution would be to iterate over the ids array, and search the object for the current id in the array. We know its final (desired) position: it is the index in the array (because we want the list sorted just like the array), so we can move this element to its final place in the list (we do this by swapping it with the element being at the position we're at currently in the array).

for (int i = ids.length - 1; i > 0; i--) { // Downward for efficiency
    final String id = ids[i];
    // Big optimization: we don't have to search the full list as the part
    // before i is already sorted and object for id can only be on the remaining
    for (int j = i; j >= 0; j--) // NOTE: loop starting at i
        if (id.equals(myList.get(j).getId()) {
            Collections.swap(myList, j, i);
            break;
        }
}

Note: the for loop omits the last element (i==0) because if all other elements are in place, the last is also in (its) place.

This is much faster than creating a comparator and using a sorting algorithm (which Collections.sort() does for example) because the order of the elements is already known (defined by the ids array) and sorting algorithms (no matter how smart the algorithms are) can only use the info [less | equals | greater] returned by comparators.

Answer 2

You could write your own Comparator based on the index in the array:

public class MyObjectComparator implements Comparator<MyObject> {
    private List<String> ids;

    public MyObjectComparator(String[] ids) {
        this.ids = Arrays.asList(ids); // Copying the array would be safer
    }

    public int compare (MyObject obj1, MyObject obj2) {
        return Integer.compare(ids.indexOf(obj1), ids.indexOf(obj2));
    }
}

// Use it:
Collections.sort (myList, new MyObjectComparator(ids));