Very soon we’ll talk about the details of sorting algorithms, but before that let’s look at how Java’s built-in library handles sorting. In this set of notes, we’ll look at sorting arrays, sorting collections (like an ArrayList), and how you can set up your own objects so they can be sorted using the library sort routines.
If you have an array that you want to sort, you can simply use Arrays.sort() from java.util.Arrays.
int[] someArray = { 54, 37, 48, 23, 84, 73, 21 };
Arrays.sort(someArray);
System.out.println(Arrays.toString(someArray));This will output [21, 23, 37, 48, 54, 73, 84].
Arrays.sort() does not return a sorted array. It sorts the existing array in-place.
If you have a collection (such as Java’s ArrayList and LinkedList) then you can simply use Collections.sort() from java.util.Collections.
ArrayList<Integer> someList = new ArrayList<Integer>();
someList.add(54);
someList.add(37);
someList.add(48);
someList.add(23);
someList.add(84);
someList.add(73);
someList.add(21);
Collections.sort(someList);
System.out.println(someList);This will output [21, 23, 37, 48, 54, 73, 84].
Much like dealing with arrays, Collections.sort() does not return a sorted collection. It sorts the existing collection in place.
When sorting using Arrays.sort():
If you are sorting primitive types (such as int, float, double, etc) then quicksort is used.
If you are sorting objects, then merge sort is used. (This is to guarantee stability.)
When sorting using Collects.sort():
Both of these techniques for sorting things work on either primitive types or objects. However, when dealing with objects, we need to consider an important complication: It isn’t always clear how to order objects.
Consider the following sample class:
public class Person {
private String firstName;
private String lastName;
private int age;
public Person(String firstName, String lastName, int age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return firstName;
}
public String getLastName() {
return lastName;
}
public int getAge() {
return age;
}
public String toString() {
return "Person [firstName=" + firstName + ", lastName=" + lastName + ", age=" + age + "]";
}
}Now, imagine we have an ArrayList of Person objects and we want to sort it with Collections.sort(). How will Java know how to order the objects? Should it sort by first name? last name? age? Some combination? The Person class doesn’t specify how to compare two people, so we can’t sort them.
If you want to be able to sort a set of objects, you need to specify the natural ordering for those objects.
The natural order for an object defines the default way to compare two of that type of object and determine their order. It can be thought of as, “When in doubt, order them like this.”
Now that we know what a natural order is, we need to look at how to specify it in Java.
In order to specify the natural ordering of an object, that object needs to be comparable to other objects of the same type. We do that by having the class implement the Comparable interface. As part of that interface, the class must have a compareTo method.
Let’s modify the person class to define the natural order to be based on age:
public class Person implements Comparable<Person> {
private String firstName;
private String lastName;
private int age;
public Person(String firstName, String lastName, int age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return firstName;
}
public String getLastName() {
return lastName;
}
public int getAge() {
return age;
}
public String toString() {
return "Person [firstName=" + firstName + ", lastName=" + lastName + ", age=" + age + "]";
}
/**
* Compare this person to another Person.
*
* @param p The other Person to compare to.
*
* @returns -1 if this person is less-than the other person, 1 if this person is
* greater than the other person, and 0 otherwise.
*/
public int compareTo(Person p) {
if (this.age < p.age) {
return -1;
} else if (this.age > p.age) {
return 1;
} else {
return 0;
}
}
}There are a few important things to notice about this example.
The Person class now implements Comparable<Person>. This tells Java that a Person object can be compared to other Person objects.
The new compareTo method should compare the current object (this) to the object passed as a parameter (p) and return a negative number if this < p, a positive number if this > p, and 0 if this == p. In this case, since we’re going to compare based on age, this makes the implementation straight-forward.
The compareTo method can be further simplified as…
/**
* Compare this person to another Person.
*
* @param p The other Person to compare to.
*
* @returns -1 if this person is less-than the other person, 1 if this person is
* greater than the other person, and 0 otherwise.
*/
public int compareTo(Person p) {
return this.age - p.age;
}This has almost identical functionality to the version with the if statements given previously. Can you see why?
Our compareTo method is not very good. It specifies that objects are equal based only on their age (which seems like an over-simplification for people) and ignores all of the other fields. Let’s come up with a better way to order people.
Here’s a simple proposal: Order by the last name, then first name, then age. This means that last name is most important, but if those are equal then look at first name, too. If both last and first name are equal, then look at age.
public class Person implements Comparable<Person> {
private String firstName;
private String lastName;
private int age;
public Person(String firstName, String lastName, int age) {
this.firstName = firstName;
this.lastName = lastName;
this.age = age;
}
public String getFirstName() {
return firstName;
}
public String getLastName() {
return lastName;
}
public int getAge() {
return age;
}
public String toString() {
return "Person [firstName=" + firstName + ", lastName=" + lastName + ", age=" + age + "]";
}
/**
* Compare this person to another Person.
*
* @param p The other Person to compare to.
*
* @returns -1 if this person is less-than the other person, 1 if this person is
* greater than the other person, and 0 otherwise.
*/
public int compareTo(Person p) {
// Check last name
int ret = this.lastName.compareTo(p.lastName);
if (ret != 0) {
return ret;
}
// Last names were equal, now check first names
ret = this.firstName.compareTo(p.firstName);
if (ret != 0) {
return ret;
}
// Both last and first names were equal, now do age
if (this.age < p.age) {
return -1;
} else if (this.age > p.age) {
return 1;
} else {
return 0;
}
}
}Note that this method makes use of the existing compareTo method for String. (That’s because the String class implements Comparable<String>, so that method exists.)
If we do this, then the following code:
ArrayList<Person> theList = new ArrayList<Person>();
theList.add(new Person("Fred", "Jones", 40));
theList.add(new Person("Bob", "Jones", 25));
theList.add(new Person("Fred", "Jones", 15));
theList.add(new Person("Tamim", "AlKuwari", 35));
Collections.sort(theList);
System.out.println(theList);Produces the following order:
Person [firstName=Tamim, lastName=AlKuwari, age=35]
Person [firstName=Bob, lastName=Jones, age=25]
Person [firstName=Fred, lastName=Jones, age=15]
Person [firstName=Fred, lastName=Jones, age=40]Which is sorted exactly how we want.
So, you have an object and you’ve given it a natural ordering. What if, in your program, you want to sort by something else, just once or a few times. For example, let’s say that I do want to order by age, even though that isn’t the natural ordering. (Maybe I want to find the youngest people in the list.) You don’t change the natural ordering, instead, you create a new class that implements the Comparator and has a compare method that does what you want and specify it as an argument to the sort method.
public class CompareAge implements Comparator<Person> {
public int compare(Person p1, Person p2) {
if (p1.getAge() < p2.getAge()) {
return -1;
} else if (p1.getAge() > p2.getAge()) {
return 1;
} else {
return 0;
}
}
}This is a new class that implements the Comparator interface. That interface requires a compare method that can be used to compare two objects. It has the same return convention as compareTo from before.
If you want to use this comparator to actually sort something:
ArrayList<Person> theList = new ArrayList<Person>();
theList.add(new Person("Fred", "Jones", 40));
theList.add(new Person("Bob", "Jones", 25));
theList.add(new Person("Fred", "Jones", 15));
theList.add(new Person("Tamim", "AlKuwari", 35));
CompareAge c = new CompareAge();
Collections.sort(theList, c);
System.out.println(theList); Which produces the following order:
Person [firstName=Fred, lastName=Jones, age=15]
Person [firstName=Bob, lastName=Jones, age=25]
Person [firstName=Tamim, lastName=AlKuwari, age=35]
Person [firstName=Fred, lastName=Jones, age=40]So, if you want to sort by something other than the natural ordering, you can simply create a new object that implements Comparator and use that with the existing sort methods.