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

Peter DeWeese and others have given you very good answers. You can use

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

to sort myList using a Comparator you have defined. <=== What the heck does that mean?

In Java, if something implements Comparable (java.lang.comparable) then you can define an order for your elements. It seems like you know what Java Generics are, as you used them to declare your ArrayList as being of type < Employee >. This is awesome, because you can store an Employee object into each entry in the ArrayList. So far so good?

However, if you want to sort objects, first you have to define an order. Since objects can have various properties, maybe I want to sort my employees by ear-size. In this case, I simply tell Java that my class implements Comparable. With generics, I have to specify that it implements Comparable< Employee > because I am defining an order for my Employee objects (peons, minions, whatever).

Peter DeWeese mentioned:

 public int compareTo(Employee e)
 {
     return this.getData().getLast().compareTo(e.getData().getLast());
 }

and Jason Goemaat mentioned:

public int compareTo(Employee other)
{
    return Data.Last.compareTo(other.Data.Last);
}

What the heck does this mean? If I say that my class implements Comparable then I need to define a compareTo function. (An interface is a collection of methods that need to be implemented) The function compareTo defines the order of my elements.

From the Comparable< T> spec:

int compareTo(T o)

Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

If I am comparing ear sizes, and let's say I want big ears to come first in my list, then I could (re)define compareTo as:

public int compareTo(Employee e)
{
    if (this.earSize > e.earSize) //big ears come first
        return -1;
    if (this.earSize == e.earSize) //equality
        return 0;
    else
        return 1; // if e.earSize > this.earSize then return 1
}

To answer Steve Kuo's question, we put the keyword this in our comparator because when we call the compareTo method

x.compareTo(y); 

the keyword this will refer to x.

You can think of compareTo as being a method of the object x, so when you call x.compareTo(y) you are really saying this.compareTo(y) from within the scope of object x.

We can also look at a String example:

This means that if I want "Medvedev" to come before "Putin" (as 'M' comes before 'P' in the English alphabet) I would have to state that I want compareTo to return -1 when comparing Medvedev to Putin.

String TheMString = "Medvedev";
String ThePString = "Putin";

then the line

TheMString.compareTo(ThePString);

will evaluate to -1.

Now a standard routine such as Collections.sort(list, comparator) will be able to use these values that compareTo returns to figure out the [absolute] order of list. As you may know, sorting is a comparison based operation and we need to know what value is "less than" or "greater than" another value in order to have a meaningful sort.

One big caveat is that if you call compareTo on Strings, it defaults to alphabetical order, so you may simply tell compareTo to return A.compareto(B) and it will make sure the strings are in order.

Normally (well, I should say, in other cases) when redefining the compareTo method, you must explicitly state a neg/zero/pos return value.

I hope that helps.

Answer 2

The best practice is to encapsulate the sorting logic in the class stored in the ArrayList, Employee in this case. Implement Comparable by creating a compareTo(Employee) method.

import java.util.*;

public class Employee  implements Comparable<Employee> {
    public EmployeeData Data;

    public Employee(String first, String last)
    {
        Data = new EmployeeData(first, last);
    }

    public int compareTo(Employee other)
    {
        return Data.Last.compareTo(other.Data.Last);
    }

    public String toString() {
        return Data.First + " " + Data.Last;
    }

    public static void main(String[] args) throws java.io.IOException {
        ArrayList list = new ArrayList();
        list.add(new Employee("Andy", "Smith"));
        list.add(new Employee("John", "Williams"));
        list.add(new Employee("Bob", "Jones"));
        list.add(new Employee("Abraham", "Abrams"));
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++)
        {
            System.out.println(list.get(i));
        }
        System.in.read();
    }
}

public class EmployeeData {
    public String First;
    public String Last;
    public EmployeeData(String first, String last)
    {
        First = first;
        Last = last;
    }
}

Output:

Abraham Abrams
Bob Jones
Andy Smith
John Williams

Answer 3

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 4

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.