In Java, how do you quickly sort an ArrayList of objects in which the sort field has multiple layers?

Question

Basically, I have a Container class called Employees, which has 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 the names of the employees).

Here is 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 last name. 

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

---

Here is the 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 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, these are classes. I don’t know how to implement "sorting" in the "Employees" class so that it sorts the ArrayList by the "last" variable of the "EmployeeData" class.

Answer 1

Best practice is to encapsulate the sorting logic into a class stored in an ArrayList, Employee in this case. Deploy Comparable by creating the 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 2

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 the TreeSet to sort on insert using this comparator, or make Employee a comparable sortable object using Collections or SortedSet.

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

Answer 3

Define Employee implements Comparable<Employee> .

In the compareTo method, go to the layers and compare the lines you need. Then you can use Collections.sort() , or you can save the data in a SortedSet , which is naturally ordered.

Answer 4

Peter DeWeese and others gave you very good answers. you can use

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

to sort myList using your comparator. & lt == == What does this mean?

In Java, if something implements Comparable (java.lang.comparable) , then you can determine the order for your elements. It looks like you know that Java Generics , since you used them to declare your ArrayList as type <Employee>. This is awesome because you can store an Employee object in every entry in an ArrayList. So far so good?

However, if you want to sort objects, you must first determine the order. Since objects can have different properties, perhaps I want to sort my employees by ear size. In this case, I just tell Java that my class implements Comparable. With generics, I have to point out that it implements Comparable <Employee> because I am defining the order for my Employee objects (peons, minions, whatever).

Peter Davy mentioned:

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

and Jason Goemat mentioned:

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

What does it mean? If I say that my class implements Comparable, then I need to define a compareTo function. (An interface is a set of methods that must be implemented). The compareTo function determines the order of my elements.

From the comparative <T> spec:

int compareTo(T o)

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

If I compare the sizes of the ears and say that I want the big ears to come first on 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 Guo’s question, we put the this keyword in our comparator, because when we call the compareTo method

 x.compareTo(y); 

this keyword will refer to x .

You may think that compareTo is a method of the x object, so when you call x.compareTo (y), you really say this.compareTo (y) from the scope of the x object.

We can also see an example line:

This means that if I want “Medvedev” to appear before “Putin” (since “M” comes to “P” in the English alphabet), I would have to say that I want to compare in order to return -1 when comparing Medvedev with Putin

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

that line

 TheMString.compareTo(ThePString); 

will be evaluated as -1.

Now a standard procedure, such as Collections.sort ( list , comparator), will be able to use these values, which compareTo returns to determine the [absolute] order of the list . As you know, sorting is a comparison-based operation, and we need to know which value is “less” or “more” of another value in order to have a meaningful look.

One big caveat is that if you call compareTo on Strings, the alphabetical order is used by default, so you can just say that compareTo returns A.compareto (B), and it will make sure the strings are ok.

Usually (well, I have to say, in other cases) when overriding the compareTo method, you should explicitly specify the return value neg / zero / pos.

I hope this helps.