Java programming course: 6.4 Sorting arrays

In the previous lesson we showed how to loop over an array.

• Previous lesson: 6.3 Looping over an array
• Course contents 

Sorting arrays

The Arrays class (which exists in package java.util) contains a number of static utility methods to facilitate the sorting of arrays.

Sorting primitive arrays

If you need to iterate over an array ensuring that the elements are processed in some particular order, then this is straightforward for arrays of primitives. Insert the following code in Experiments to declare an array of five int primitives with some values assigned for each element:

int[] values = new int[5];
values[0] = 17;
values[1] = 12;
values[2] = 24;
values[3] = 97;
values[4] = 3;
 

Currently, if you iterate over the elements they will be output in the same sequence as above:

for (int v : values) {
    System.out.println(v);
}
 

To get the values listed in ascending numerical order insert the following statement before the for block:

Arrays.sort(values); 

• The sort() method of Arrays simply sorts the values of the array passed as the argument
• You will need to import java.util

You will now find the values listed in ascending numerical order.

Sorting object arrays

You have seen how an array of int primitives can be sorted by simply passing the array to the Arrays.sort() method. This works because int (and the other numeric primitives) have a built-in natural ordering, being their numerical value.

However, objects do not have any built-in natural ordering, since they could consist of any user defined attributes, which may themselves be primitives or other objects, and Java cannot predict what the natural ordering of your classes might be. To see what happens if you attempt to sort an array of objects you will return to the array returned from the Pen class:

Pen penguinPen = new Pen("Penguin Pen");
penguinPen.add(new Penguin("Petra", Gender.FEMALE, 1));
penguinPen.add(new Penguin("Oswald", Gender.MALE, 2));
        
Animal[] animalsInPen = penguinPen.getAnimals();
Arrays.sort(animalsInPen);

for (Animal anAnimal : animalsInPen) {
    System.out.println(anAnimal);
}
 

When you run the above you will receive a ClassCastException. This is because, in order to sort an array of objects you need to define its natural ordering by changing the Animal class so that it implements the Comparable interface. This interface specifies a compareTo() method which you must implement, and in which you can write the necessary code to manage the ordering.

Change the class declaration in Animal to implement the Comparable interface:

public abstract class Animal implements Comparable<Animal> { 

Note the following:

• The <Animal> part that immediately follows Comparable is known as the formal type parameter. It specifies that you only want to compare the current Animal object with other Animal objects. It is possible to omit the <Animal> part but this is not recommended

The compareTo() method that you need to implement will provide the other Animal object to compare against. The method returns an int value, which gets interpreted as follows:

• If a negative value is returned, it means the current object should be sorted before the other object
• If a positive value is returned, it means the current object should be sorted after the other object
• If zero is returned, then the current object and the other object are identical as far as sorting is concerned

Armed with this knowledge you can now implement the required compareTo() method to first sort as follows:

1. Alphabetically by the animal's name
2. If the names are the same, then by gender
3. If the genders are the same, then by the animal's ages
4. If the ages are the same, then a tie-breaker is needed – see the later discussion for why

Add the following method to Animal: 

@Override
public int compareTo(Animal otherAnimal) {
    // Sort alphabetically by name
    int result = getName().compareTo(otherAnimal.getName());
    if (result != 0) return result;

    // Names are the same, so sort by gender
    // TO DO
}

 

• The method argument must be of type Animal due to the fact you specified Comparable<Animal> on the class definition
• •The getName() method is used to obtain the name attribute of both the current Animal and the other Animal being compared against. This method returns a String, and therefore the compareTo() method being used is that defined for the String class, and compares the two strings alphabetically
• If the result is not zero then you know that the two names are different, so you can therefore return straightaway. However, if the result is zero then the names are the same so you need to add some additional code to compare the genders

@Override
public int compareTo(Animal otherAnimal) {
    // Sort alphabetically by name
    int result = getName().compareTo(otherAnimal.getName());
    if (result != 0) return result;

    // Names are the same, so sort by gender
    result = getGender().compareTo(otherAnimal.getGender());
    if (result != 0) return result;

    // Genders are the same, so sort by age
    // TO DO
}
 

• This time, the getGender() method returns the enum value of the animals, and therefore the compareTo() method being used is that defined for enums, which also sorts alphabetically by the constant values
• If the result is not zero then you know that the two genders are different, so you can therefore return straight away. However if the result is zero then the genders are the same so you need to add some additional code to compare the ages

@Override
public int compareTo(Animal otherAnimal) {
    // Sort alphabetically by name
    int result = getName().compareTo(otherAnimal.getName());
    if (result != 0) return result;

    // Names are the same, so sort by gender
    result = getGender().compareTo(otherAnimal.getGender());
    if (result != 0) return result;

    // Genders are the same, so sort by age
    result = getAge() - otherAnimal.getAge();
    if (result != 0) return result;

    // If reached here name, gender and age are the same.
    // TO DO
}
 

• The getAge() method returns an int primitive value, and you cannot invoke methods on primitives. Therefore, a simple subtraction is used to determine whether the ages are the same value
• If the result is not zero then you know that the two ages are different, so you can therefore return straightaway. However, if the result is zero then the ages are the same, and for this class special provision needs to be made to correctly handle this situation

If all the attributes of the other animal match those of the current animal, then you need to ascertain if it is because they both point to the same single object or whether they are two independent objects which just happen to have the same attribute values. The reason you have to check for this is that the compareTo() method must be consistent with equals(), that is, if two objects are equal according to the equals() method then compareTo() should return zero; conversely, if two objects are not equal according to the equals() method then compareTo() should return a non-zero result.

The equals() method has not been overridden in Animal, so it uses the inherited version which compares object identity. Therefore, the only time the equals() method will return true is if the object references being compared are in fact pointing to the same single object. In this case, they will also have the same hash code and so compareTo() should return zero in order to be consistent. In all other cases the hash codes will be different and compareTo() should return a non-zero value, which will match the fact that equals() will return false. Had the Animal object overridden the equals() method then the compareTo() method would need to be based on only the same attributes as uses within equals().

You can now add the appropriate code to the end of the method:

@Override
public int compareTo(Animal otherAnimal) {
    // Sort alphabetically by name
    int result = getName().compareTo(otherAnimal.getName());
    if (result != 0) return result;
        
    // Names are the same, so sort by gender
    result = getGender().compareTo(otherAnimal.getGender());
    if (result != 0) return result;
        
    // Genders are the same, so sort by age
    result = getAge() - otherAnimal.getAge();
    if (result != 0) return result;
        
    /* If reached here name, gender and age are the same.
     * So that method is consistent with equals() will now
     * sort on hash code.
     */
    return hashCode() - otherAnimal.hashCode();
}
 

• You just return the result of deducting one hash code from the other. If the result is zero then it should mean that the two references are in fact the same object, otherwise they must point to two different objects (that just happen to have the same attribute values). In either case, your compareTo() method is now consistent with the equals() method.

You should now find that the animal objects will be sorted.

You can take a similar approach so that that the natural ordering of ZooKeeper is by each zookeeper's name, and if they happen to be the same then by their email address. Change the ZooKeeper class signature to implement Comparable:

public class ZooKeeper implements Emailable, Comparable<ZooKeeper> { 

And define its compareTo() method:

@Override
public int compareTo(ZooKeeper otherZooKeeper) {
    // Sort alphabetically by name
    int result = getName().compareTo(otherZooKeeper.getName());
    if (result != 0) return result;

    // Names are the same, so sort by email
    result = getEmail().compareTo(otherZooKeeper.getEmail());
    if (result != 0) return result;

    /* If reached here name and email are the same.
     * So that method is consistent with equals() will now
     * sort on hash code.
     */
    return hashCode() - otherZooKeeper.hashCode();
}
 

The Visitor class can also be made Comparable:

public class Visitor implements Emailable, Comparable<Visitor> { 

The natural ordering for the Visitor class will also be firstly by name and then by email address:

@Override
public int compareTo(Visitor otherVisitor) {
    // Sort alphabetically by name
    int result = getName().compareTo(otherVisitor.getName());
    if (result != 0) {
        return result;
    }

    // Names are the same, so sort by email
    result = getEmail().compareTo(otherVisitor.getEmail());
    if (result != 0) {
        return result;
    }

    // If reached here name and email are the same.
    // So method is consistent with equals() will now sort by hash
    return hashCode() - otherVisitor.hashCode();
}
 

In the next lesson we will show how to sort in alternative sequences.

Next lesson: 6.5 Sorting in alternative sequences