Interview Questions

Java Comparator and Comparable Interface

In this section lets discuss about comparator and comparable interface in java.

Consider a scenario where you want to sort a collection for eg. Arraylist of type Strings. It can be done using Collections.sort(..) method. But how exactly the strings are getting sorted?

Lets take a closer look in to the Collections.sort() method. It is a static method taking a List as input parameter. The list elements should implement comparable interface. So what are the methods in comparable interface?

public interface Comparable<T>
{
    public int compareTo(T o);
}

Most of the immutable objects like String, Integer, Double implements this comparable interface. This is the method where the objects in the list are compared and based on it sorting will be done. Lets see an example of how to use the comparable interface.

Consider a scenario where you want to sort a set of employee objects based on name, age and salary in ascending order (similar to sql query SELECT * FROM
EMPLOYEE ORDER BY NAME,AGE,SALARY;).

Take a look at the employee class below. It consist of empId,name, age and salary attributes.

Employee Class

/**
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

package in.techdive.java.examples;

class Employee implements Comparable<Employee>
{
    private int    empId;
    private String name;
    private int    age;
    private int    salary;

    public int getAge()
    {
        return age;
    }

    public void setAge(int age)
    {
        this.age = age;
    }

    public int getEmpId()
    {
        return empId;
    }

    public void setEmpId(int empId)
    {
        this.empId = empId;
    }

    public String getName()
    {
        return name;
    }

    public void setName(String name)
    {
        this.name = name;
    }

    public int getSalary()
    {
        return salary;
    }

    public void setSalary(int salary)
    {
        this.salary = salary;
    }

    public Employee(int empId, String name, int age, int salary)
    {
        this.empId = empId;
        this.name = name;
        this.age = age;
        this.salary = salary;
    }

    public int compareTo(Employee o)
    {
        if (!this.name.equalsIgnoreCase(o.name))
        {
            return this.name.compareToIgnoreCase(o.name);
        }
        if (this.age == o.age)
        {
            return this.age - o.age;
        }
        return this.salary - o.salary;
    }
}

Consider the compareTo() method above. It takes an employee object as parameter. It first compares employee names if they are same then compares age and salary. It returns int value, 0 if the objects are equal 1 if the current object is greater than given object(passed as argument). -1 if the current object is lesser than given object.

Ok this fine... but what exactly is the sorting algorithm used...
hmm... that's homework for you..... what fun would it be if I said everything out here... Smile Time for you to dig in to collection api in java... Cheers!

Its time to test how our employee objects are getting sorted. Consider the Test class below.

Test Class

/**
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

package in.techdive.java.examples;

public class Test
{
    public static void main(String argv[])
    {
        List<Employee> col = new ArrayList<Employee>();
        col.add(new Employee(5, "Frank", 28, 5000));
        col.add(new Employee(1, "Jorge", 19, 6000));
        col.add(new Employee(6, "Bill", 34, 7000));
        col.add(new Employee(3, "Michel", 10, 8000));
        col.add(new Employee(7, "Simpson", 8, 7500));
        col.add(new Employee(4, "Frank", 60, 6000));
        col.add(new Employee(8, "Lee", 40, 5000));
        col.add(new Employee(2, "Mark", 30, 6500));

        Collections.sort(coll);
        printList(coll);
    }

    private static void printList(List<Employee> list)
    {
        System.out.println("EmpId\tName\tAge");
        for (Employee e : list)
        {
            System.out.println(e.getEmpId() + "\t" + e.getName() + "\t"
                    + e.getAge() + "\t" + e.getSalary());
        }
    }
}

Since the Employee class implements comparable interface we can sort the list of employees using Collections.sort(..) method. Here is the output for your reference.

Output

EmpId Name Age
6 Bill 34 7000
5 Frank 28 5000
4 Frank 60 6000
1 Jorge 19 6000
8 Lee 40 5000
2 Mark 30 6500
3 Michel 10 8000
7 Simpson 8 7500

Cool... we compareTo() method in Employee class is working fine and our Employee objects are sorted.
Wait a minute...! have we missed something... Oh yeah... but what the heck is that comparator interface?

Imagine a scenario where the Employee class or we want to sort some other class which did not implement comparable interface. Then how will we able to sort the those objects. That's where Comparator interface comes to our rescue. Consider the Comparator interface below

public interface Comparator<T>
{
    int compare(T o1, T o2);
}

It consist of compare(T o1, T o2) method. We can create a new class for example
EmpSortByEmpId which implements Comparator interface. It will compare its two arguments and returns a negative integer, 0, or a positive integer if the first argument is less than, equal to, or greater than the second respectively. Consider the EmpSortByEmpId class below.

class EmpSortByEmpId implements Comparator<Employee>
{
    public int compare(Employee o1, Employee o2)
    {
        if (!o1.name.equalsIgnoreCase(o2.name))
        {
            return o1.name.compareToIgnoreCase(o2.name);
        }
        if (o1.age == o2.age)
        {
            return this.age - o2.age;
        }

        return o1.salary - o2.salary;
    }
}

We have implemented the same logic as in the compareTo() method earlier. Now to sort the employee objects we can use the same Collections.sort() method in the following way

//use Comparator implementation
Collections.sort(col, new EmpSortByEmpId());

The output will be same as above.
Use comparable interface if you want to sort user defined objects. Use comparator interface if you want to sort any api objects which do not implement comparable interface. In some cases, combination of both the interfaces can be used.