Introduction to Searching and Sorting
• Comparable Interface
Comparator Interface
1
The Comparable Interface
• The Comparable interface is in the
[Link] package, and so is automatically
available to any program
• It has only the following method heading that
must be implemented:
public int compareTo(Object other);
• It is the programmer's responsibility to follow
the semantics of the Comparable interface
when implementing it
2
The Comparable Interface Semantics
• The method compareTo must return
– A negative number if the calling object "comes
before" the parameter other
– A zero if the calling object "equals" the parameter
other
– A positive number if the calling object "comes after"
the parameter other
• If the parameter other is not of the same type
as the class being defined, then a
ClassCastException should be thrown
3
The Comparable Interface Semantics
• Almost any reasonable notion of "comes
before" is acceptable
– In particular, all of the standard less-than
relations on numbers and lexicographic
ordering on strings are suitable
• The relationship "comes after" is just the
reverse of "comes before"
4
The Comparable Interface
• Several core Java classes implement
Comparable interface.
• It is also preferable for
[Link](object2) to return 0 if
and only if [Link](object2) is true.
5
The Comparable Interface (cont’d)
• Example 1: A BankAccount defining the
natural ordering as the ascending order of
account numbers.
import [Link].*;
class BankAccount implements Comparable
{
private int accountNumber;
private String name;
private double balance;
6
The Comparable Interface (cont’d)
public int compareTo(Object object)
{
BankAccount account = (BankAccount) object;
if(accountNumber < [Link])
return -1;
else if(accountNumber == [Link])
return 0;
else
return 1;
}
7
The Comparable Interface (cont’d)
• Assuming that account1 and account2 are
BankAccount objects, a typical call to the
compareTo method is:
int comparisonResult = [Link](account2);
if(comparisonResult == 0)
[Link](“Same account”);
else if (comparisonResult < 0)
[Link](“acountNumber1 is smaller”);
else
[Link](“accountNumber2 is smaller”);
8
Example
public class Student implements
Comparable<Student> {
private int roll;
private String name;
//getter setter
@Override
public int compareTo(Student o) {
if ([Link] > [Link])
return 1;
else if ([Link] < [Link])
return -1;
else
return 0;
}
} 9
for (int i = 0; i < [Link]; i++) {
st[i] = new Student();
st[i].setRoll(roll[i]);
public class StudentSimulator {
st[i].setName(name[i]);
public static void
[Link](st[i]);
main(String[] args) {
}
Student st[] =
[Link]("\nStudent
new Student[3];
Information \n");
for (Student student : list) {
int roll[] = {
1003, 1001, 1002 }; [Link]([Link](
String name[] = ) + "\t" + [Link]());
{ "javed", "sakina", "mahmud" }; }
[Link](list);
ArrayList<Student> list = new
ArrayList<Student>();
10
The Comparator Interface
• If we want to sort objects of a class which
does not implement Comparable interface, or
the class implements Comparable but we
want To order its objects in a way different
from the natural ordering defined by
Comparable, the [Link]
interface should be used.
• The Comparator interface is one of the java
collections framework interfaces.
11
The Comparator Interface
• The Java collection framework is a set of
important utility classes and interfaces in
the [Link] package for working with
collections.
• A collection is a group of objects.
• Comparator interface defines how
collection objects are compared.
12
The Comparator Interface
public interface Comparator
{
int compare(Object object1, Object object2);
boolean equals(Object object);
}
A class that implements Comparator should
implement the compare method such that its
returned value is:
0 if object1 “is equal to” object2
> 0 if object1 “is greater than” object2
< 0 if object1 “is less than” object2
13
The Comparator Interface (cont’d)
• It is also preferable for the compare
method to return 0 if and only if
[Link](object2) is true.
• The compare method throws a
ClassCastException if the type of object1
and that of object2 are not compatible for
comparison.
14
The Comparator Interface (cont’d)
• Example 2: This example sorts the strings in
reverse order of the alphabetical one.
import [Link].*;
class StringReverseComparator implements Comparator
{
public int compare(Object object1, Object object2)
{
String string1 = [Link]();
String string2 = [Link]();
// Reverse the comparison
return [Link](string1);
}
}
15
The Comparator Interface (cont’d)
class Test
{
public static void main(String[] args)
{
String[] array =
{"Ahmad","Mohammad","Ali","Hisham","Omar",
"Bilal","Hassan"};
[Link](array, new
StringReverseComparator());
[Link]([Link](array));
}
}
16
The Comparator Interface (cont’d)
-The sort method ,in the Arrays class,
sorts the array “array” according to the
comparator object. Notice the
comparator object is provided as a
parameter for the sorting method; it is
an object from the class
StringReverseComparator .
- After printing, we get the following
order:
[Omar, Mohammad, Hisham, Hassan,
Bilal, Ali, Ahmad]
17
Example class EmployeeSortBySal implements
Comparator<Employee> {
@Override
public int compare(Employee
o1, Employee o2) {
public class Employee return new
{ Float([Link]()).compareTo([Link]-
Salary());
private int id; }
private String name; }
private float salary;
class EmployeeSortById implements
//getter Comparator<Employee> {
//setter @Override
public int compare(Employee
o1, Employee o2) {
return new
Integer([Link]()).compareTo([Link]())
;
}
} 18
public class EmployeeMain {
public static void main(String[] args) {
int id[] = { 1003, 1001,
1002 };
String name[] = { "rahma", "sakib",
class EmployeeSortByName "mahmud" };
implements float salary[] = { 20000, 10000, 30000 };
Comparator<Employee> {
List<Employee> elist = new
ArrayList<Employee>();
@Override
public int compare(Employee o1, Employee emp[] = new Employee[3];
Employee o2) { for (int i = 0; i < [Link]; i++) {
return emp[i] = new Employee();
[Link]().compareTo([Link]-
Name()); emp[i].setId(id[i]);
}
emp[i].setName(name[i]);
}
emp[i].setSalary(salary[i]);
[Link](emp[i]);
19
}
[Link](elist, new
EmployeeSortBySal());
[Link](elist, new
EmployeeSortById()); [Link]("Sorted
Employee list by salary");
[Link]("Sorted
Employee list"); for (Employee employee : elist) {
[Link]([Link]-
for (Employee employee : elist) { tId() + "\t" + [Link]()
[Link]([Link]- + "\t" + [Link]());
tId() + "\t" + [Link]() }
+ "\t" + [Link]());
}
20
