• Learn how to sort collections of objects (such as PlayList of Songs) by implementing the Comparable interface.

• There are many sorting algorithms.
• The simple-to-understand bubble sort is among the least efficient sorting algorithms.
• More sophisticated algorithms will be covered in later courses.
• Modern programming languages make it largely unnecessary for programmers to write their own sorting algorithms.
• Java has java.util.Array.sort() and java.util.Collections.sort() that can be used to sort Arrays and ArrayLists of objects that have a natural sorting order.
  • Natural sorting order: Numeric types (int, double), Strings

• Problem: Not all user-defined types have a natural sorting order
  • Solution: The Comparable and Comparator interfaces (We will cover the Comparable interface only.)
  • An object that implements the Comparable interface is capable of comparing itself with another object of the same class.
    • The object's class itself must implements the java.lang.Comparable interface in order to be able to compare its instances.

• The compareTo() method of the Comparable interface:
  • java.lang.Comparable: int compareTo(Object obj1)
  • This method compares *this* object with the obj1 object. The returned int value has the following meanings:

         1. positive - this object is greater than obj1
         2. zero - this object equals to obj1
         3. negative - this object is less than obj1

• BlueJ project zip: ComparableEmployee

         // The original Employee class:
         public class Employee {
             private int empId;
             private String name;
             private int age;

             public Employee(int empId, String name, int age) {
                 // set values of fields
             }
             // getters & setters
         }

• Next create a list of Employees.
• Employees are added to an ArrayList without any specific order in the following class.

         import java.util.*;

         public class Util {
             
             public static ArrayList<Employee> getEmployees() {
                 
                 ArrayList<Employee> col = new ArrayList<Employee>();
                 
                 col.add(new Employee(5, "Frank", 28));
                 col.add(new Employee(1, "Jorge", 19));
                 col.add(new Employee(6, "Bill", 34));
                 col.add(new Employee(3, "Michel", 10));
                 col.add(new Employee(7, "Simpson", 8));
                 col.add(new Employee(4, "Clerk",16 ));
                 col.add(new Employee(8, "Lee", 40));
                 col.add(new Employee(2, "Mark", 30));
                 
                 return col;
             }
         }

• Sorting in natural ordering:
• Employee's natural ordering would be done according to the employee id.
  • For that, above Employee class must be altered to add the comparing ability as follows:

         public class Employee implements Comparable<Employee> {
             private int empId;
             private String name;
             private int age;
             
             /**
              * Compare a given Employee with this object.
              * If employee id of this object is 
              * greater than the received object,
              * then this object is greater than the other.
              */

             public int compareTo(Employee o) {
                 return this.empId - o.empId ;
             }

             // ....
         }

• The new compareTo() method does the trick of implementing the natural ordering of the instances.
  • So if a collection of Employee objects is sorted using the Collections.sort(ArrayList) method, sorting happens according to the ordering done inside this method.

• We'll write a class to test this natural ordering mechanism.
  • Following class uses the Collections.sort(ArrayList) method to sort the given list in natural order.

         import java.util.*;

         public class TestEmployeeSort {
             
             public static void main(String[] args) {     
                 ArrayList coll = Util.getEmployees();  // use static Util.getEmployees()
                 Collections.sort(coll); // sort method
                 printList(coll);
             }
             
             private static void printList(ArrayList<Employee> list) {
                 System.out.println("EmpId\tName\tAge");
                 for (Employee e: list) {
                     System.out.println(e.getEmpId() + "\t" + e.getName() + "\t" + e.getAge());
                 }
             }
         }

• When we last looked at the Song/PlayList example, we were unable to sort an ArrayList of Song objects because Song objects did not have a natural sorting order (were not comparable to each other).

• By implementing the Comparable interface, we can make Songs comparable.
  • This will allow Songs to be sorted using the Java Collections.sort() method.

• Basic example that sorts Songs by song name
  • See the comparablesong1 package in the Comparable project.

• More advanced example in which the Songs can be sorted by other Song fields, such as artist, album and year
  • This version uses a static Song.setSortBy() method.
  • See the comparablesong2 package in the Comparable project.