In Java, How do you quicksort an ArrayList of objects in which the sorting field is multiple layers deep?

Question

Basically, I have a Container class called "Employees" which has in it an ArrayList. This ArrayList contains "Employee" objects, which in turn contain "EmployeeData" objects which in turn contain String objects such as "first" or "last" (which are employee names).

Here's a diagram of the ArrayList structure:

ArrayList[Employee] emps ==> 1:Many ==> Employee emp
Employee emp ==> 1:1 ==> EmployeeData data
EmployeeData data ==> 1:2 ==> String last // A string that contains employee's last name.

How in the world would I perform a quicksort on the ArrayList so that the "Employee" objects in it are in alphabetical order based on the String object "last"? It seems kinda complicated!

---

Here's a basic design of my classes:

class Employees{
    //data:
        private ArrayList<Employee> emps = new ArrayList<Employee>();

    //Some constructors go here

    //Methods to add, remove, toString, etc, go here

    public /*output a sorted ArrayList?*/ sort(){
        // Some kind of "quicksort" in here to modify or create a new ArrayList sorted by employee's las name...
    }
}

class Employee{
    //data:
    EmployeeData data;
    // Some methods to construct and modify EmployeeData data.
}

class EmployeeData{
    //data:
        String first, last; // I wish to sort with "last". How do you do it?
        double payrate, hours;
    //...methods...
}

As you can see, those are the classes. I have no idea how to implement "sort" in the "Employees" class so that it sorts the ArrayList by the "last" variable of the "EmployeeData" class.

Answer 1

You can make a comparator, something like:

public class MyComparator implements Comparator<Employee>
{
  public int compare(Employee e1, Employee e2)
  {
    return e1.getData().getLast().compareTo(e2.getData().getLast());
  }
}

Then use it to sort the list.

Collections.sort(myList, new MyComparator());

Alternatively, you can use a TreeSet to sort on insertion using this comparator or make the Employee a comparable object to sort using Collections or a SortedSet.

public class Employee implements Comperable<Employee>
{
  ...
  public int compareTo(Employee e)
  {
    return this.getData().getLast().compareTo(e.getData().getLast());
  }
  ...
}

Answer 2

Define Employee implements Comparable<Employee>.

In the compareTo method, dig into the layers and compare the strings you need. Then you can use Collections.sort(), or you can store the data in a SortedSet, which is naturally ordered.