Selection Sort

For example, here’s an implementation of a simple algorithm called selection sort (see http://thinkdast.com/selectsort):

public class SelectionSort {

    /**
     * Swaps the elements at indexes i and j.
     */
    public static void swapElements(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * Finds the index of the lowest value
     * starting from the index at start (inclusive)
     * and going to the end of the array.
     */
    public static int indexLowest(int[] array, int start) {
        int lowIndex = start;
        for (int i = start; i < array.length; i++) {
            if (array[i] < array[lowIndex]) {
                lowIndex = i;
            }
        }
        return lowIndex;
    }

    /**
     * Sorts the elements (in place) using selection sort.
     */
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int j = indexLowest(array, i);
            swapElements(array, i, j);
        }
    }
}

The first method, swapElements, swaps two elements of the array. Reading and writing elements are constant time operations, because if we know the size of the elements and the location of the first, we can compute the location of any other element with one multiplication and one addition, and those are constant time operations. Since everything in swapElements is constant time, the whole method is constant time.

The second method, indexLowest, finds the index of the smallest element of the array starting at a given index, start. Each time through the loop, it accesses two elements of the array and performs one comparison. Since these are all constant time operations, it doesn’t really matter which ones we count. To keep it simple, let’s count the number of comparisons:

1. If start is 0, indexLowest traverses the entire array, and the total number of comparisons is the length of the array, which I’ll call n.

2. If start is 1, the number of comparisons is n – 1.

3. In general, the number of comparisons is n – start, so indexLowest is linear.

The third method, selectionSort, sorts the array. It loops from 0 to n – 1, so the loop executes n times. Each time, it calls indexLowest and then performs a constant time operation, swapElements.

The first time indexLowest is called, it performs n comparisons. The second time, it performs n – 1 comparisons, and so on. The total number of comparisons is

The sum of this series is , which is proportional to n²; this means that selectionSort is quadratic.

To get to the same result a different way, we can think of indexLowest as a nested loop. Each time we call indexLowest, the number of operations is proportional to n. We call it n times, so the total number of operations is proportional to n².

Big O Notation

All constant time algorithms belong to a set called O(1). So another way to say that an algorithm is constant time is to say that it is in O(1). Similarly, all linear algorithms belong to O(n), and all quadratic algorithms belong to O(n²). This way of classifying algorithms is called big O notation.

NOTE: I am providing a casual definition of big O notation. For a more mathematical treatment, see http://thinkdast.com/bigo.

This notation provides a convenient way to write general rules about how algorithms behave when we compose them. For example, if you perform a linear time algorithm followed by a constant algorithm, the total runtime is linear. Using to mean “is a member of”:

If and , .

If you perform two linear operations, the total is still linear:

If and , .

In fact, if you perform a linear operation any number of times, k, the total is linear, as long as k is a constant that does not depend on n:

If and k is a constant, .

But if you perform a linear operation n times, the result is quadratic:

If , .

In general, we only care about the largest exponent of n. So if the total number of operations is 2n + 1, it belongs to O(n). The leading constant, 2, and the additive term, 1, are not important for this kind of analysis. Similarly, n² + 100n + 1000 is in O(n²). Don’t be distracted by the big numbers!

Order of growth is another name for the same idea. An order of growth is a set of algorithms whose runtimes are in the same big O category; for example, all linear algorithms belong to the same order of growth because their runtimes are in O(n).

In this context, an “order” is a group, like the Order of the Knights of the Round Table, which is a group of knights, not a way of lining them up. So you can imagine the Order of Linear Algorithms as a set of brave, chivalrous, and particularly efficient algorithms.

Exercise 2

The exercise for this chapter is to implement a List that uses a Java array to store the elements.

In the code repository for this book (see “Working with the Code”), you’ll find the source files you’ll need:

• MyArrayList.java contains a partial implementation of the List interface. Four of the methods are incomplete; your job is to fill them in.

• MyArrayListTest.java contains JUnit tests you can use to check your work.

You’ll also find the Ant build file build.xml. From the code directory, you should be able to run ant MyArrayList to run MyArrayList.java, which contains a few simple tests. Or you can run ant MyArrayListTest to run the JUnit test.

When you run the tests, several of them should fail. If you examine the source code, you’ll find four TODO comments indicating the methods you should fill in.

Before you start filling in the missing methods, let’s walk through some of the code. Here are the class definition, instance variables, and constructor:

public class MyArrayList<E> implements List<E> {
    int size;                    // keeps track of the number of elements
    private E[] array;           // stores the elements
    
    public MyArrayList() {
        array = (E[]) new Object[10];
        size = 0;
    }
}

As the comments indicate, size keeps track of how many elements are in MyArrayList, and array is the array that actually contains the elements.

The constructor creates an array of 10 elements, which are initially null, and sets size to 0. Most of the time, the length of the array is bigger than size, so there are unused slots in the array.

One detail about Java: you can’t instantiate an array using a type parameter; for example, the following will not work:

        array = new E[10];

To work around this limitation, you have to instantiate an array of Object and then typecast it. You can read more about this issue at http://thinkdast.com/generics.

Next we’ll look at the method that adds elements to the list:

    public boolean add(E element) {
        if (size >= array.length) {
            // make a bigger array and copy over the elements
            E[] bigger = (E[]) new Object[array.length * 2];
            System.arraycopy(array, 0, bigger, 0, array.length);
            array = bigger;
        } 
        array[size] = element;
        size++;
        return true;
    }

If there are no unused spaces in the array, we have to create a bigger array and copy over the elements. Then we can store the element in the array and increment size.

It might not be obvious why this method returns a boolean, since it seems like it always returns true. As always, you can find the answer in the documentation: http://thinkdast.com/colladd. It’s also not obvious how to analyze the performance of this method. In the normal case, it’s constant time, but if we have to resize the array, it’s linear. I’ll explain how to handle this in “Classifying add”.

Finally, let’s look at get; then you can get started on the exercise:

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return array[index];
    }

Actually, get is pretty simple: if the index is out of bounds, it throws an exception; otherwise it reads and returns an element of the array. Notice that it checks whether the index is less than size, not array.length, so it’s not possible to access the unused elements of the array.

In MyArrayList.java, you’ll find a stub for set that looks like this:

    public T set(int index, T element) {
        // TODO: fill in this method.
        return null;
    }

Read the documentation of set at http://thinkdast.com/listset, then fill in the body of this method. If you run MyArrayListTest again, testSet should pass.

HINT: Try to avoid repeating the index-checking code.

Your next mission is to fill in indexOf. As usual, you should read the documentation at http://thinkdast.com/listindof so you know what it’s supposed to do. In particular, notice how it is supposed to handle null.

I’ve provided a helper method called equals that compares an element from the array to a target value and returns true if they are equal (and it handles null correctly). Notice that this method is private because it is only used inside this class; it is not part of the List interface.

When you are done, run MyArrayListTest again; testIndexOf should pass now, as well as the other tests that depend on it.

Only two more methods to go, and you’ll be done with this exercise. The next one is an overloaded version of add that takes an index and stores the new value at the given index, shifting the other elements to make room, if necessary.

Again, read the documentation at http://thinkdast.com/listadd, write an implementation, and run the tests for confirmation.

HINT: Avoid repeating the code that makes the array bigger.

Last one: fill in the body of remove. The documentation is at http://thinkdast.com/listrem. When you finish this one, all tests should pass.

Once you have your implementation working, compare it to mine, which you can read at http://thinkdast.com/myarraylist.