Many data types, especially primitives such as strings, integers, and so on, have a natural sort order: A comes before B, B comes before C, and so on. A natural comparator is simply a comparator that supports this natural ordering of objects. You will see that it is possible to create a single comparator that can sort any object that has a natural sorting order by basing it on a convention established by the Java language itself. Java has the concept of Comparable— an interface that can be implemented by any class you are using to provide a natural sort order.

public interface Comparable {
    public int compareTo(Object other);
}

public void testLessThan() {
        assertTrue(NaturalComparator.INSTANCE.compare("A", "B") < 0);
    }

public void testGreaterThan() {
        assertTrue(NaturalComparator.INSTANCE.compare("B", "A") > 0);
    }

public void testEqualTo() {
        assertTrue(NaturalComparator.INSTANCE.compare("A", "A") == 0);
    }

The test case contains one test method for each of the three cases we identified above. Each test method assumes that the NaturalComparator provides a single static instance that you can use without needing to instantiate it. Each test method uses two simple character strings as test data to validate that the NaturalComparator behaves as expected.

public final class NaturalComparator implements Comparator {
    public static final NaturalComparator INSTANCE =
        new NaturalComparator();

    private NaturalComparator() {
    }
    ...
}

To ensure this, you mark the constructor as private to prevent instantiation and instead provide a publicly accessible static variable holding the single instance of the class. You must also be sure to mark the class as final to prevent it from being extended erroneously.

Next you implement compare(). Because you are implementing this on top of the Comparable interface, most of the actual work will be performed by the arguments themselves, making the implementation almost trivial:

public int compare(Object left, Object right) {
        assert left != null : "left can't be null";
        return ((Comparable) left).compareTo(right);
    }

After first ensuring you haven't been passed a NULL argument, you cast the left argument to a Comparable and call the defined compareTo() method, passing the right argument.

You never check to see whether the left argument is actually an instance of Comparable because the Comparator interface specifically allows a ClassCastException to be thrown, meaning you can perform the cast without the additional check.

The NaturalComparator is designed to compare two objects that implement the Comparable interface. Many built-in Java objects implement this interface, and classes you create are free to implement it as well. The code only needs to cast the left operand to the Comparable interface so that it can call the compareTo() method, passing in the right operand for the comparison to be performed by the left operand itself. The comparator here is not actually required to implement any comparison logic because it is all handled by the objects themselves.

Often, you will want to sort things in reverse order. For example, when looking at a list of files on your computer, you may want to see the files from smallest to largest, or in reverse order from largest to smallest. One way to achieve a reverse version of the NaturalComparator described previously is to copy its implementation and reimplement the compare() method, as shown here:

public int compare(Object left, Object right) {
        assert right != null : "right can't be null";
        return ((Comparable) right).compareTo(left);
    }

You swap the right and left arguments, confirming that the right argument is not null and then passing the left argument to its compare() method.

Although this approach works perfectly well in this particular case, it isn't very extensible. For each complex type, such as Person or File, you always end up creating two comparators: one to sort ascending, and one to sort descending.

A better approach, which you take in the next Try It Out, is to create a generic comparator that wraps (or "decorates") another comparator and reverse the result. This way, you only need one comparator for each complex type you wish to sort. You use the generic ReverseComparator to sort in the opposite direction.

If the left argument would normally sort before the right, you want the ReverseComparator to cause the opposite to occur; that is, if the underlying comparator returns a negative integer, indicating that the left argument is less than the right argument, you need to ensure that the result from the ReverseComparator is a positive integer:

public void testLessThanBecomesGreaterThan() {
        ReverseComparator comparator =
            new ReverseComparator(NaturalComparator.INSTANCE);

        assertTrue(comparator.compare("A", "B") > 0);
    }

If the underlying comparator returns a positive integer, indicating that the left argument would normally sort after the right, the result should be a negative integer:

public void testGreaterThanBecomesLessThan() {
        ReverseComparator comparator =
            new ReverseComparator(NaturalComparator.INSTANCE);

        assertTrue(comparator.compare("B", "A") < 0);
    }

If the two arguments are equal, then the result must be zero:

public void testEqualsRemainsUnchanged() {
        ReverseComparator comparator =
            new ReverseComparator(NaturalComparator.INSTANCE);

        assertTrue(comparator.compare("A", "A") == 0);
    }

The preceding code works by instantiating ReverseComparator objects and passing to them a NaturalComparator to which the comparison logic can be delegated. The first two test methods then make what look like nonsensical assertions: You know that A comes before B, but the opposite is true in this case, and the first test method makes sure this is the case. The second test method is similarly counterintuitive. The final test method ensures that objects that are equal remain equal when the ReverseComparator is used.

In the following Try It Out, you implement your ReverseComparator.

package com.wrox.algorithms.sorting;

public class ReverseComparator implements Comparator {
    private final Comparator _comparator;

    public ReverseComparator(Comparator comparator) {
        assert comparator != null : "comparator can't be null";
        _comparator = comparator;
    }
    ...
}

You start, of course, by implementing the Comparator interface and defining a constructor that accepts the underlying Comparator to which you will eventually delegate the compare call.

Then comes the actual implementation of compare:

public int compare(Object left, Object right) {
        return _comparator.compare(right, left);
    }

At first glance, the code looks rather innocuous, simply delegating to the underlying comparator, but if you look carefully at the code, you will see that the two arguments are reversed before you pass them. If the ReverseComparator was called with (A, B), then the underlying comparator would be passed (B, A), thereby inducing the opposite result.

Because you don't actually need to access any of the attributes for either argument, this solution is completely generic; you need only implement it once to have a solution for all situations. You can now start to build your first sorting algorithm, the bubble sort algorithm.

The first two lines of the test method create the sorting algorithm implementation and use it to sort the unsorted list. You pass a natural comparator because your expected results have been set up in the natural sequence of the strings themselves. The bulk of the test verifies that the result of the sort matches the expected result list. You do this by creating an iterator over the lists and comparing each item in turn to ensure an item-by-item exact match. Every one of your sorting algorithms must be able to pass this test or it will be of very little use in practice!

In the following Try It Out, you make a test that is specific to your bubble sort implementation.

package com.wrox.algorithms.sorting;

public class BubblesortListSorterTest extends AbstractListSorterTest {
    protected ListSorter createListSorter(Comparator comparator) {
        return new BubblesortListSorter(comparator);
    }
}

That's all you need to do to complete the test for the BubblesortListSorter. Of course, the preceding code won't compile yet, as we don't have a BubblesortListSorter class; that's what we'll do now. In the next Try It Out, you implement your bubble sort.

Despite the fact that you only implemented a single method with a single line of code, the key point here is that you are extending the AbstractListSorterTest class in the preceding code. The abstract class provides the test data and several test methods; all you need to do is provide the ListSorter implementation for these tests to use, and that's what you have done here.

With these guidelines in place, you begin implementation with the constructor, as shown here:

package com.wrox.algorithms.sorting;

import com.wrox.algorithms.lists.List;

public class BubblesortListSorter implements ListSorter {
    private final Comparator _comparator;

    public BubblesortListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }
    ...
}

You now need to implement the bubble sort algorithm itself. Recall from the description of the algorithm that it is comprised of a number of passes through the data, with each pass resulting in one item being moved into its final sorted position. The first thing to determine is how many passes are needed. When all but the last item have been moved into their final sorted position, the last item has nowhere to go and must therefore also be in its final position, so you need a number of passes that is one less than the number of items. The code that follows calls this the outer loop.

On each pass, you compare each pair of items and swap them if they are out of order (as determined by the comparator you have been given). Remember, however, that on each pass, one item is moved into final sorted position and can therefore be ignored on subsequent passes. Therefore, each pass deals with one less item than the previous pass. If N is the number of items in the list, then on the first pass, the number of comparisons you need to make is (N – 1), on the second pass it is (N – 2), and so on. This is why the inner loop in the following code has the condition left < (size – pass) to control how many comparisons are performed:

public List sort(List list) {
        assert list != null : "list cannot be null";

        int size = list.size();

        for (int pass = 1; pass < size; ++pass) {                // outer loop
            for (int left = 0; left < (size - pass); ++left) {   // inner loop
                int right = left + 1;
                if (_comparator.compare(list.get(left), list.get(right)) > 0) {
                    swap(list, left, right);
                }
            }
        }

        return list;
    }

The preceding code uses the supplied comparator to determine whether the two items under scrutiny are out of order. If they are, then it calls the swap() method to correct their relative placement in the list. Here is the code for swap():

private void swap(List list, int left, int right) {
        Object temp = list.get(left);
        list.set(left, list.get(right));
        list.set(right, temp);
    }
}

When you compile and run this test, it passes with flying colors. Just to make sure, you can place a deliberate mistake in the test's expectation and run it again to see that it will indeed catch you if you slip up when implementing your next sorting algorithm.

Despite the fact that you only implemented a single method with a single line of code, the key point here is that you are extending the AbstractListSorterTest class in the preceding code. The abstract class provides the test data and several test methods; all you need to do is provide the ListSorter implementation for these tests to use, which is what you have done here.

package com.wrox.algorithms.sorting;

import com.wrox.algorithms.lists.List;

public class SelectionSortListSorter implements ListSorter {
    private final Comparator _comparator;

    public SelectionSortListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }
    ...
}

The implementation has both an outer loop and an inner loop, like bubble sort, but there are subtle differences that might escape your attention if you don't look at this code closely. First, the outer loop index ranges between zero and (N – 2), rather than between 1 and (N – 1) in bubble sort. Note that this is still the same number of passes (N – 1), but it reflects your focus in the selection sort on filling a given "slot" with the right object on each pass. For example, on the first pass, your goal is to get the right object into position zero of the list. On the second pass, the goal is to fill position 1, and so on. Once again, you can get by with only (N – 1) passes because the last object naturally ends up in sorted position as a result of sorting every other object first.

No swapping occurs during the inner loop, as it did in bubble sort. During the inner loop, the only requirement is to remember the position of the smallest item. When the inner loop finishes, you then swap the smallest item into the slot you are trying to fill. This is slightly different from the earlier bookshelf example, in which the books were sorted from largest to smallest, but the algorithm would work just as well in that case. In fact, you simply plug in the ReverseComparator you created earlier in this chapter:

public List sort(List list) {
        assert list != null : "list cannot be null";

        int size = list.size();

        for (int slot = 0; slot < size − 1; ++slot) {            // outer loop
            int smallest = slot;
            for (int check = slot + 1; check < size; ++check) {  // inner loop
                if (_comparator.compare(list.get(check), list.get(smallest)) < 0) {
                    smallest = check;
                }
            }
            swap(list, smallest, slot);
        }
        return list;
    }

There is also one small difference in the implementation of swap() for a selection sort when compared to a bubble sort. You add a guard clause to ignore requests to swap a slot with itself, which can occur quite easily with a selection sort, but not a bubble sort:

private void swap(List list, int left, int right) {
        if (left == right) {
            return;
        }
        Object temp = list.get(left);
        list.set(left, list.get(right));
        list.set(right, temp);
    }
}

Although you implemented a single method with a single line of code, the key point here is that you are extending the AbstractListSorterTest class in the preceding code. The abstract class provides the test data and several test methods; all you need to do is provide the ListSorter implementation for these tests to use, and that's what you have done here.

package com.wrox.algorithms.sorting;

import com.wrox.algorithms.lists.List;
import com.wrox.algorithms.lists.LinkedList;
import com.wrox.algorithms.iteration.Iterator;

public class InsertionSortListSorter implements ListSorter {
    private final Comparator _comparator;

    public InsertionSortListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }
    ...
}

The implementation of the sort() method is very different from the two algorithms you have seen earlier in the chapter. This algorithm does not sort the objects in place by rearranging the order of the list it is given; rather, this algorithm creates a new, empty list and inserts each item from the original list into the result list in sorted order.

In addition, the original list is processed using an iterator instead of accessing the items by index because you have no need for direct access to the items in the original list. You simply process each one in turn, which is the natural idiom for an iterator:

public List sort(List list) {
        assert list != null : "list cannot be null";

        final List result = new LinkedList();

        Iterator it = list.iterator();

        for (it.first(); !it.isDone(); it.next()) {
            int slot = result.size();
            while (slot > 0) {
                if (_comparator.compare(it.current(), result.get(slot − 1)) >= 0) {
                    break;
                }
                −−slot;
            }
            result.insert(slot, it.current());
        }

        return result;
}

Finally, notice that the inner loop is a while loop, rather than a for loop. Its task is to find the right position in the result list to insert the next item. After it finds the right position (or falls off the end of the result list), it exits the inner loop. The current item is then inserted into the result list. At all times, the result list is entirely sorted; each item is placed into position relative to those items already in the list, thereby maintaining the overall sorted sequence. This example uses a LinkedList for the result list because it is better suited to insertion operations.

Note also that the algorithm searches backwards through the result list looking for the right position, rather than forwards. This is a big advantage when it comes to sorting already sorted or nearly sorted objects, as demonstrated in the section "Comparing the Basic Sorting Algorithms," later in this chapter. It is also the reason why this algorithm is stable, which is the subject of the next section.