In this section, we show you the first of several sorting algorithms. A sorting algorithm rearranges the elements of a collection so that they are stored in sorted order. To keep the examples simple, we will discuss how to sort an array of integers before going on to sorting strings or more complex data. Consider the following array a:

An obvious first step is to find the smallest element. In this case the smallest element is 5, stored in a[3]. We should move the 5 to the beginning of the array. Of course, there is already an element stored in a[0], namely 11. Therefore we cannot simply move a[3] into a[0] without moving the 11 somewhere else. We don't yet know where the 11 should end up, but we know for certain that it should not be in a[0]. We simply get it out of the way by swapping it with a[3].

Now the first element is in the correct place. In the foregoing figure, the darker color indicates the portion of the array that is already sorted.

Next we take the minimum of the remaining entries a[1] ... a[4]. That minimum value, 9, is already in the correct place. We don't need to do anything in this case and can simply extend the sorted area by one to the right:

Repeat the process. The minimum value of the unsorted region is 11, which needs to be swapped with the first value of the unsorted region, 17:

Now the unsorted region is only two elements long, but we keep to the same successful strategy. The minimum value is 12, and we swap it with the first value, 17.

That leaves us with an unprocessed region of length 1, but of course a region of length 1 is always sorted. We are done.

Let's program this algorithm. For this program, as well as the other programs in this chapter, we will use a utility method to generate an array with random entries. We place it into a class ArrayUtil so that we don't have to repeat the code in every example. To show the array, we call the static toString method of the Arrays class in the Java library and print the resulting string.

This algorithm will sort any array of integers. If speed were not an issue, or if there simply were no better sorting method available, we could stop the discussion of sorting right here. As the next section shows, however, this algorithm, while entirely correct, shows disappointing performance when run on a large data set.

Special Topic 14.1 on page 604 discusses insertion sort, another simple sorting algorithm.

ch14/selsort/SelectionSorter.java

1  /**
 2     This class sorts an array, using the selection sort
 3     algorithm.
 4  */
 5  public class SelectionSorter
 6  {
 7     private int[] a;
 8
 9     /**
10        Constructs a selection sorter.
11        @param anArray the array to sort
12     */
13     public SelectionSorter(int[] anArray)
14     {
15        a = anArray;
16     }
17
18     /**
19        Sorts the array managed by this selection sorter.
20     */
21     public void sort()
22     {

23        for (int i = 0; i < a.length - 1; i++)
24        {
25           int minPos = minimumPosition(i);
26           swap(minPos, i);
27        }
28     }
29
30     /**
31          Finds the smallest element in a tail range of the array.
32          @param from the first position in a to compare
33          @return the position of the smallest element in the
34          range    a[from] ... a[a.length - 1]
35     */
36     private int minimumPosition(int from)
37     {
38          int minPos = from;
39          for (int i = from + 1; i < a.length; i++)
40             if (a[i] < a[minPos]) minPos = i;
41          return minPos;
42     }
43
44     /**
45          Swaps two entries of the array.
46          @param i the first position to swap
47          @param j   the second position to swap
48     */
49     private void swap(int i, int j)
50     {
51          int temp = a[i];
52          a[i] = a[j];
53          a[j] = temp;
54     }
55  }

ch14/selsort/SelectionSortDemo.java

1  import java.util.Arrays;
 2
 3  /**
 4     This program demonstrates the selection sort algorithm by
 5     sorting an array that is filled with random numbers.
 6  */
 7  public class SelectionSortDemo
 8  {
 9     public static void main(String[] args)
10     {
11        int[] a = ArrayUtil.randomIntArray(20, 100);
12        System.out.println(Arrays.toString(a));
13
14        SelectionSorter sorter = new SelectionSorter(a);
15        sorter.sort();
16
17        System.out.println(Arrays.toString(a));
18     }
19  }

ch14/selsort/ArrayUtil.java

1  import java.util.Random;
 2
 3  /**
 4     This class contains utility methods for array manipulation.
 5  */
 6  public class ArrayUtil
 7  {
 8     private static Random generator = new Random();
 9
10     /**
11        Creates an array filled with random values.
12        @param length the length of the array
13        @param n the number of possible random values
14        @return an array filled with length numbers between
15        0 and n - 1
16     */
17     public static int[] randomIntArray(int length, int n)
18     {
19        int[] a = new int[length];
20        for (int i = 0; i < a.length; i++)
21           a[i] = generator.nextInt(n);
22
23       return a;
24     }
25  }

Typical Output

[65, 46, 14, 52, 38, 2, 96, 39, 14, 33, 13, 4, 24, 99, 89, 77, 73, 87, 36, 81]
[2, 4, 13, 14, 14, 24, 33, 36, 38, 39, 46, 52, 65, 73, 77, 81, 87, 89, 96, 99]

2. What steps does the selection sort algorithm go through to sort the sequence 6 5 4 3 2 1?

To measure the performance of a program, you could simply run it and use a stopwatch to measure how long it takes. However, most of our programs run very quickly, and it is not easy to time them accurately in this way. Furthermore, when a program takes a noticeable time to run, a certain amount of that time may simply be used for loading the program from disk into memory and displaying the result (for which we should not penalize it).

In order to measure the running time of an algorithm more accurately, we will create a StopWatch class. This class works like a real stopwatch. You can start it, stop it, and read out the elapsed time. The class uses the System.currentTimeMillis method, which returns the milliseconds that have elapsed since midnight at the start of January 1, 1970. Of course, you don't care about the absolute number of seconds since this historical moment, but the difference of two such counts gives us the number of milliseconds of a time interval.

Here is the code for the StopWatch class:

ch14/selsort/StopWatch.java

1  /**
2     A stopwatch accumulates time when it is running. You can
3     repeatedly start and stop the stopwatch. You can use a
4     stopwatch to measure the running time of a program.
5  */
6  public class StopWatch
7  {
8     private long elapsedTime;
9     private long startTime;
10     private boolean isRunning;
11
12     /**
13        Constructs a stopwatch that is in the stopped state
14        and has no time accumulated.
15     */
16     public StopWatch()
17     {
18        reset();
19     }
20
21     /**
22        Starts the stopwatch. Time starts accumulating now.
23     */
24     public void start()
25     {
26        if (isRunning) return;
27        isRunning = true;
28        startTime = System.currentTimeMillis();
29     }
30
31     /**
32        Stops the stopwatch. Time stops accumulating and is
33        is added to the elapsed time.
34     */
35     public void stop()
36     {
37        if (!isRunning) return;
38        isRunning = false;
39        long endTime = System.currentTimeMillis();
40        elapsedTime = elapsedTime + endTime - startTime;
41     }
42
43     /**
44        Returns the total elapsed time.
45        @return the total elapsed time
46     */
47     public long getElapsedTime()
48     {
49        if (isRunning)
50        {
51           long endTime = System.currentTimeMillis();
52           return elapsedTime + endTime - startTime;
53        }
54        else
55            return elapsedTime;

56     }
57
58     /**
59        Stops the watch and resets the elapsed time to 0.
60     */
61       public void reset()
62     {
63          elapsedTime = 0;
64          isRunning = false;
65     }
66  }

Here is how we will use the stopwatch to measure the performance of the sorting algorithm:

ch14/selsort/SelectionSortTimer.java

1  import java.util.Scanner;
 2
 3  /**
 4     This program measures how long it takes to sort an
 5     array of a user-specified size with the selection
 6     sort algorithm.
 7  */
 8  public class SelectionSortTimer
 9  {
10     public static void main(String[] args)
11     {
12        Scanner in = new Scanner(System.in);
13        System.out.print("Enter array size: ");
14        int n = in.nextInt();
15
16        // Construct random array
17
18        int[] a = ArrayUtil.randomIntArray(n, 100);
19        SelectionSorter sorter = new SelectionSorter(a);
20
21        // Use stopwatch to time selection sort
22
23        StopWatch timer = new StopWatch();
24
25        timer.start();
26        sorter.sort();
27        timer.stop();
28
29        System.out.println("Elapsed time: "
30              + timer.getElapsedTime() + " milliseconds");
31     }
32  }

Program Run

Enter array size: 100000
Elapsed time: 27880 milliseconds

Figure 14.1. Time Taken by Selection Sort

By starting to measure the time just before sorting, and stopping the stopwatch just after, you get the time required for the sorting process, without counting the time for input and output.

The table in Figure 1 shows the results of some sample runs. These measurements were obtained with a Intel processor with a clock speed of 2 GHz, running Java 6 on the Linux operating system. On another computer the actual numbers will look different, but the relationship between the numbers will be the same.

The graph in Figure 1 shows a plot of the measurements. As you can see, doubling the size of the data set more than doubles the time needed to sort it.

4. Look at the graph in Figure 1. What mathematical shape does it resemble?

Let us count the number of operations that the program must carry out to sort an array with the selection sort algorithm. We don't actually know how many machine operations are generated for each Java instruction, or which of those instructions are more time-consuming than others, but we can make a simplification. We will simply count how often an array element is visited. Each visit requires about the same amount of work by other operations, such as incrementing subscripts and comparing values.

Let n be the size of the array. First, we must find the smallest of n numbers. To achieve that, we must visit n array elements. Then we swap the elements, which takes two visits. (You may argue that there is a certain probability that we don't need to swap the values. That is true, and one can refine the computation to reflect that observation. As we will soon see, doing so would not affect the overall conclusion.) In the next step, we need to visit only n − 1 elements to find the minimum. In the following step, n − 2 elements are visited to find the minimum. The last step visits two elements to find the minimum. Each step requires two visits to swap the elements. Therefore, the total number of visits is

because

After multiplying out and collecting terms of n, we find that the number of visits is

We obtain a quadratic equation in n. That explains why the graph of Figure 1 looks approximately like a parabola.

Now simplify the analysis further. When you plug in a large value for n (for example, 1,000 or 2,000), then ½n² is 500,000 or 2,000,000. The lower term, 5/2n – 3, doesn't contribute much at all; it is only 2,497 or 4,997, a drop in the bucket compared to the hundreds of thousands or even millions of comparisons specified by the ½n² term. We will just ignore these lower-level terms. Next, we will ignore the constant factor ½. We are not interested in the actual count of visits for a single n. We want to compare the ratios of counts for different values of n. For example, we can say that sorting an array of 2,000 numbers requires four times as many visits as sorting an array of 1,000 numbers:

The factor ½ cancels out in comparisons of this kind. We will simply say, "The number of visits is of order n²". That way, we can easily see that the number of comparisons increases fourfold when the size of the array doubles: (2n)² = 4n².

To indicate that the number of visits is of order n², computer scientists often use big-Oh notation: The number of visits is O(n²). This is a convenient shorthand.

In general, the expression f(n) = O(g(n)) means that f grows no faster than g, or, more formally, that for all n larger than some threshold, the ratio for some constant value C. The function g is usually chosen to be very simple, such as n² in our example.

To turn an exact expression such as

into big-Oh notation, simply locate the fastest-growing term, n², and ignore its constant coefficient, no matter how large or small it may be.

We observed before that the actual number of machine operations, and the actual amount of time that the computer spends on them, is approximately proportional to the number of element visits. Maybe there are about 10 machine operations (increments, comparisons, memory loads, and stores) for every element visit. The number of machine operations is then approximately 10 × ½n². As before, we aren't interested in the coefficient, so we can say that the number of machine operations, and hence the time spent on the sorting, is of the order of n² or O(n²).

The sad fact remains that doubling the size of the array causes a fourfold increase in the time required for sorting it with selection sort. When the size of the array increases by a factor of 100, the sorting time increases by a factor of 10,000. To sort an array of a million entries, (for example, to create a telephone directory) takes 10,000 times as long as sorting 10,000 entries. If 10,000 entries can be sorted in about 1/2 of a second (as in our example), then sorting one million entries requires well over an hour. We will see in the next section how one can dramatically improve the performance of the sorting process by choosing a more sophisticated algorithm.

6. How large does n need to be so that ½n² is bigger than 5/2 n – 3?

Insertion Sort

Insertion sort is another simple sorting algorithm. In this algorithm, we assume that the initial sequence

a[0] a[1] ... a[k]

of an array is already sorted. (When the algorithm starts, we set k to 0.) We enlarge the initial sequence by inserting the next array element, a[k + 1], at the proper location. When we reach the end of the array, the sorting process is complete.

For example, suppose we start with the array

Of course, the initial sequence of length 1 is already sorted. We now add a[1], which has the value 9. The element needs to be inserted before the element 11. The result is

Next, we add a[2], which has the value 16. As it happens, the element does not have to be moved.

We repeat the process, inserting a[3] or 5 at the very beginning of the initial sequence.

Finally, a[4] or 7 is inserted in its correct position, and the sorting is completed.

The following class implements the insertion sort algorithm:

public class InsertionSorter
{
    private int[] a;

    /**
      Constructs an insertion sorter.
      @param anArray the array to sort
    */
    public InsertionSorter(int[] anArray)
    {
      a = anArray;
    }

    /**
      Sorts the array managed by this insertion sorter.
    */
    public void sort()
    {
       for (int i = 1; i < a.length; i++)
       {
         int next = a[i];
         // Find the insertion location
         // Move all larger elements up
         int j = i;
         while (j > 0 && a[j - 1] > next)
         {
            a[j] = a[j - 1];
            j--;
         }
         // Insert the element
         a[j] = next;
       }
    }
}

How efficient is this algorithm? Let n denote the size of the array. We carry out n − 1 iterations. In the kth iteration, we have a sequence of k elements that is already sorted, and we need to insert a new element into the sequence. For each insertion, we need to visit the elements of the initial sequence until we have found the location in which the new element can be inserted. Then we need to move up the remaining elements of the sequence. Thus, k + 1 array elements are visited. Therefore, the total number of visits is

We conclude that insertion sort is an O(n²) algorithm, on the same order of efficiency as selection sort.

Insertion sort has a desirable property: Its performance is O(n) if the array is already sorted—see Exercise R14.13. This is a useful property in practical applications, in which data sets are often partially sorted.

Note

Insertion sort is an O(n²) algorithm.

In this section, you will learn about the merge sort algorithm, a much more efficient algorithm than selection sort. The basic idea behind merge sort is very simple.

Suppose we have an array of 10 integers. Let us engage in a bit of wishful thinking and hope that the first half of the array is already perfectly sorted, and the second half is too, like this:

Now it is simple to merge the two sorted arrays into one sorted array, by taking a new element from either the first or the second subarray, and choosing the smaller of the elements each time:

In fact, you may have performed this merging before if you and a friend had to sort a pile of papers. You and the friend split the pile in half, each of you sorted your half, and then you merged the results together.

That is all well and good, but it doesn't seem to solve the problem for the computer. It still must sort the first and second halves of the array, because it can't very well ask a few buddies to pitch in. As it turns out, though, if the computer keeps dividing the array into smaller and smaller subarrays, sorting each half and merging them back together, it carries out dramatically fewer steps than the selection sort requires.

Let's write a MergeSorter class that implements this idea. When the MergeSorter sorts an array, it makes two arrays, each half the size of the original, and sorts them recursively. Then it merges the two sorted arrays together:

public void sort()
{
   if (a.length <= 1) return;
   int[] first = new int[a.length / 2];
   int[] second = new int[a.length - first.length];
   // Copy the first half of a into first, the second half into second
   ...
   MergeSorter firstSorter = new MergeSorter(first);
   MergeSorter secondSorter = new MergeSorter(second);
   firstSorter.sort();
   secondSorter.sort();
   merge(first, second);
}

The merge method is tedious but quite straightforward. You will find it in the code that follows.

ch14/mergesort/MergeSorter.java

1  /**
 2     This class sorts an array, using the merge sort algorithm.
 3  */
 4  public class MergeSorter
 5  {
 6     private int[] a;
 7
 8     /**
 9        Constructs a merge sorter.
10        @param anArray  the array to sort
11     */
12     public MergeSorter(int[] anArray)
13     {
14        a = anArray;
15     }
16
17     /**
18        Sorts the array managed by this merge sorter.
19     */
20     public void sort()
21     {
22        if (a.length <= 1) return;
23        int[] first = new int[a.length / 2];
24        int[] second = new int[a.length - first.length];
25        // Copy the first half of a into first, the second half into second
26        for (int i = 0; i < first.length; i++) { first[i] = a[i]; }
27        for (int i = 0; i < second.length; i++)
28        {
29            second[i] = a[first.length + i];
30        }

31         MergeSorter firstSorter = new MergeSorter(first);
32         MergeSorter secondSorter = new MergeSorter(second);
33         firstSorter.sort();
34         secondSorter.sort();
35         merge(first, second);
36     }
37
38     /**
39          Merges two sorted arrays into the array managed by this merge sorter.
40          @param first the first sorted array
41          @param second the second sorted array
42     */
43     private void merge(int[] first, int[] second)
44     {
45          int iFirst = 0;  // Next element to consider in the first array
46          int iSecond = 0;  // Next element to consider in the second array
47          int j = 0;  // Next open position in a
48
49          // As long as neither iFirst nor iSecond past the end, move
50          // the smaller element into  a
51          while (iFirst < first.length && iSecond < second.length)
52          {
53             if (first[iFirst] < second[iSecond])
54             {
55                a[j] = first[iFirst];
56                iFirst++;
57             }
58             else
59             {
60                a[j] = second[iSecond];
61                iSecond++;
62             }
63             j++;
64          }
65
66          // Note that only one of the two loops below copies entries
67          // Copy any remaining entries of the first array
68          while (iFirst < first.length)
69          {
70             a[j] = first[iFirst];
71             iFirst++; j++;
72          }
73          // Copy any remaining entries of the second half
74          while (iSecond < second.length)
75          {
76             a[j] = second[iSecond];
77             iSecond++; j++;
78          }
79       }
80   }

ch14/mergesort/MergeSortDemo.java

1     import java.util.Arrays;
2
3    /**
4       This program demonstrates the merge sort algorithm by
5       sorting an array that is filled with random numbers.
6    */

7    public class MergeSortDemo
8    {
9     public static void main(String[] args)
10     {
11         int[] a = ArrayUtil.randomIntArray(20, 100);
12         System.out.println(Arrays.toString(a));
13
14         MergeSorter sorter = new MergeSorter(a);
15         sorter.sort();
16        System.out.println(Arrays.toString(a));
17     }
18    }

Typical Output

[8, 81, 48, 53, 46, 70, 98, 42, 27, 76, 33, 24, 2, 76, 62, 89, 90, 5, 13, 21]
[2, 5, 8, 13, 21, 24, 27, 33, 42, 46, 48, 53, 62, 70, 76, 76, 81, 89, 90, 98]

8. Manually run the merge sort algorithm on the array 8 7 6 5 4 3 2 1.

The merge sort algorithm looks a lot more complicated than the selection sort algorithm, and it appears that it may well take much longer to carry out these repeated subdivisions. However, the timing results for merge sort look much better than those for selection sort.

Figure 2 shows a table and a graph comparing both sets of performance data. As you can see, merge sort is a tremendous improvement. To understand why, let us estimate the number of array element visits that are required to sort an array with the merge sort algorithm. First, let us tackle the merge process that happens after the first and second halves have been sorted.

Figure 14.2. Merge Sort Timing versus Selection Sort

Each step in the merge process adds one more element to a. That element may come from first or second, and in most cases the elements from the two halves must be compared to see which one to take. We'll count that as 3 visits (one for a and one each for first and second) per element, or 3n visits total, where n denotes the length of a. Moreover, at the beginning, we had to copy from a to first and second, yielding another 2n visits, for a total of 5n.

If we let T(n) denote the number of visits required to sort a range of n elements through the merge sort process, then we obtain

because sorting each half takes T(n/2) visits. Actually, if n is not even, then we have one subarray of size (n − 1)/2 and one of size (n − 1)/2. Although it turns out that this detail does not affect the outcome of the computation, we will nevertheless assume for now that n is a power of 2, say n = 2^m. That way, all subarrays can be evenly divided into two parts.

Unfortunately, the formula

does not clearly tell us the relationship between n and T(n). To understand the relationship, let us evaluate T(n/2), using the same formula:

Therefore

Let us do that again:

hence

This generalizes from 2, 4, 8, to arbitrary powers of 2:

Recall that we assume that n = 2^m; hence, for k = m,

Because n = 2^m, we have m = log₂(n).

To establish the growth order, we drop the lower-order term n and are left with 5n log₂(n). We drop the constant factor 5. It is also customary to drop the base of the logarithm, because all logarithms are related by a constant factor. For example,

Hence we say that merge sort is an O(n log(n)) algorithm.

Is the O(n log(n)) merge sort algorithm better than the O(n²) selection sort algorithm? You bet it is. Recall that it took 100² = 10,000 times as long to sort a million records as it took to sort 10,000 records with the O(n²) algorithm. With the O( nlog(n)) algorithm, the ratio is

Suppose for the moment that merge sort takes the same time as selection sort to sort an array of 10,000 integers, that is, 3/4 of a second on the test machine. (Actually, it is much faster than that.) Then it would take about 0.75 × 150 seconds, or under 2 minutes, to sort a million integers. Contrast that with selection sort, which would take over 2 hours for the same task. As you can see, even if it takes you several hours to learn about a better algorithm, that can be time well spent.

In this chapter we have barely begun to scratch the surface of this interesting topic. There are many sorting algorithms, some with even better performance than merge sort, and the analysis of these algorithms can be quite challenging. These important issues are often revisited in later computer science courses.

10. If you double the size of an array, how much longer will the merge sort algorithm take to sort the new array?

The Quicksort Algorithm

Quicksort is a commonly used algorithm that has the advantage over merge sort that no temporary arrays are required to sort and merge the partial results.

The quicksort algorithm, like merge sort, is based on the strategy of divide and conquer. To sort a range a[from] ... a[to] of the array a, first rearrange the elements in the range so that no element in the range a[from] ... a[p] is larger than any element in the range a[p + 1] ... a[to]. This step is called partitioning the range.

For example, suppose we start with a range

Here is a partitioning of the range. Note that the partitions aren't yet sorted.

You'll see later how to obtain such a partition. In the next step, sort each partition, by recursively applying the same algorithm on the two partitions. That sorts the entire range, because the largest element in the first partition is at most as large as the smallest element in the second partition.

Quicksort is implemented recursively as follows:

public void sort(int from, int to)
{
   if (from >= to) return;
   int p = partition(from, to);
   sort(from, p);
   sort(p + 1, to);
}

Let us return to the problem of partitioning a range. Pick an element from the range and call it the pivot. There are several variations of the quicksort algorithm. In the simplest one, we'll pick the first element of the range, a[from], as the pivot.

Now form two regions a[from] ... a[i], consisting of values at most as large as the pivot and a[j] ... a[to], consisting of values at least as large as the pivot. The region a[i + 1] ... a[j - 1] consists of values that haven't been analyzed yet. (See the figure below.) At the beginning, both the left and right areas are empty; that is, i = from - 1 and j = to + 1.

Partitioning a Range

Then keep incrementing i while a[i] < pivot and keep decrementing j while a[j] > pivot. The figure below shows i and j when that process stops.

Extending the Partitions

Now swap the values in positions i and j, increasing both areas once more. Keep going while i < j. Here is the code for the partition method:

private int partition(int from, int to)
{
   int pivot = a[from];
   int i = from - 1;
   int j = to + 1;
   while (i < j)
   {
       i++; while (a[i] < pivot) i++;
       j--; while (a[j] > pivot) j--;
      if (i < j) swap(i, j);
   }
   return j;
}

On average, the quicksort algorithm is an O(n log(n)) algorithm. Because it is simpler, it runs faster than merge sort in most cases. There is just one unfortunate aspect to the quicksort algorithm. Its worst-case run-time behavior is O(n²). Moreover, if the pivot element is chosen as the first element of the region, that worst-case behavior occurs when the input set is already sorted—a common situation in practice. By selecting the pivot element more cleverly, we can make it extremely unlikely for the worst-case behavior to occur. Such "tuned" quicksort algorithms are commonly used, because their performance is generally excellent. For example, the sort method in the Arrays class uses a quicksort algorithm.

Another improvement that is commonly made in practice is to switch to insertion sort when the array is short, because the total number of operations of insertion sort is lower for short arrays. The Java library makes that switch if the array length is less than 7.

The First Programmer

Before pocket calculators and personal computers existed, navigators and engineers used mechanical adding machines, slide rules, and tables of logarithms and trigonometric functions to speed up computations. Unfortunately, the tables—for which values had to be computed by hand—were notoriously inaccurate. The mathematician Charles Babbage (1791–1871) had the insight that if a machine could be constructed that produced printed tables automatically, both calculation and typesetting errors could be avoided. Babbage set out to develop a machine for this purpose, which he called a Difference Engine because it used successive differences to compute polynomials. For example, consider the function f(x) = x³. Write down the values for f(1), f(2), f(3), and so on. Then take the differences between successive values:

1
    7
8
     19
27
     37
64
     61
125
     91
216

Repeat the process, taking the difference of successive values in the second column, and then repeat once again:

1
    7
8        12
    19        6
27       18
    37        6
64       24
    61        6
125      30
    91
216

Now the differences are all the same. You can retrieve the function values by a pattern of additions—you need to know the values at the fringe of the pattern and the constant difference. You can try it out yourself: Write the highlighted numbers on a sheet of paper, and fill in the others by adding the numbers that are in the north and northwest positions.

A Replica of Babbage's Difference Engine

This method was very attractive, because mechanical addition machines had been known for some time. They consisted of cog wheels, with ten cogs per wheel, to represent digits, and mechanisms to handle the carry from one digit to the next. Mechanical multiplication machines, on the other hand, were fragile and unreliable. Babbage built a successful prototype of the Difference Engine and, with his own money and government grants, proceeded to build the table-printing machine. However, because of funding problems and the difficulty of building the machine to the required precision, it was never completed.

While working on the Difference Engine, Babbage conceived of a much grander vision that he called the Analytical Engine. The Difference Engine was designed to carry out a limited set of computations—it was no smarter than a pocket calculator is today. But Babbage realized that such a machine could be made programmable by storing programs as well as data. The internal storage of the Analytical Engine was to consist of 1,000 registers of 50 decimal digits each. Programs and constants were to be stored on punched cards—a technique that was, at that time, commonly used on looms for weaving patterned fabrics.

Ada Augusta, Countess of Lovelace (1815–1852), the only child of Lord Byron, was a friend and sponsor of Charles Babbage. Ada Lovelace was one of the first people to realize the potential of such a machine, not just for computing mathematical tables but for processing data that were not numbers. She is considered by many the world's first programmer. The Ada programming language, a language developed for use in U.S. Department of Defense projects, was named in her honor.

Suppose you need to find your friend's telephone number. You look up the friend's name in the telephone book, and naturally you can find it quickly, because the telephone book is sorted alphabetically. Now suppose you have a telephone number and you must know to what party it belongs. You could of course call that number, but suppose nobody picks up on the other end. You could look through the telephone book, a number at a time, until you find the number. That would obviously be a tremendous amount of work, and you would have to be desperate to attempt it.

This thought experiment shows the difference between a search through an unsorted data set and a search through a sorted data set. The following two sections will analyze the difference formally.

If you want to find a number in a sequence of values that occur in arbitrary order, there is nothing you can do to speed up the search. You must simply look through all elements until you have found a match or until you reach the end. This is called a linear or sequential search.

How long does a linear search take? If we assume that the element v is present in the array a, then the average search visits n/2 elements, where n is the length of the array. If it is not present, then all n elements must be inspected to verify the absence. Either way, a linear search is an O(n) algorithm.

Here is a class that performs linear searches through an array a of integers. When searching for the value v, the search method returns the first index of the match, or −1 if v does not occur in a.

ch14/linsearch/LinearSearcher.java

1   /**
2       A class for executing linear searches through an array.
3   */
4   public class LinearSearcher
5   {
6      private int[] a;
7
8      /**
9         Constructs the LinearSearcher  .
10         @param anArray  an array of integers
11      */
12         public LinearSearcher(int[] anArray)
13      {
14         a = anArray;
15      }
16
17      /**
18         Finds a value in an array, using the linear search
19         algorithm.
20         @param v the value to search
21         @return the index at which the value occurs, or  −1
22         if it does not occur in the array
23      */
24      public int search(int v)
25      {
26         for (int i = 0; i < a.length; i++)
27         {
28            if (a[i] == v)
29               return i;
30         }
31          return −1;
32      }
33   }

ch14/linsearch/LinearSearchDemo.java

1  import java.util.Arrays;
2  import java.util.Scanner;
3
4  /**
5     This program demonstrates the linear search algorithm.
6  */
7  public class LinearSearchDemo
8  {
9     public static void main(String[] args)
10     {
11        int[] a = ArrayUtil.randomIntArray(20, 100);
12        System.out.println(Arrays.toString(a));
13        LinearSearcher searcher = new LinearSearcher(a);
14
15        Scanner in = new Scanner(System.in);
16
17        boolean done = false;
18        while (!done)
19        {
20           System.out.print("Enter number to search for, −1 to quit: ");
21           int n = in.nextInt();
22           if (n == −1)
23              done = true;
24           else
25           {
26               int pos = searcher.search(n);
27              System.out.println("Found in position " + pos);
28           }
29        }
30     }
31  }

Typical Output

[46, 99, 45, 57, 64, 95, 81, 69, 11, 97, 6, 85, 61, 88, 29, 65, 83, 88, 45, 88]
Enter number to search for, −1 to quit: 11
Found in position 8

12. Why can't you use a "for each" loop for (int element : a) in the search method?

Now let us search for an item in a data sequence that has been previously sorted. Of course, we could still do a linear search, but it turns out we can do much better than that.

Consider the following sorted array a. The data set is:

We would like to see whether the value 15 is in the data set. Let's narrow our search by finding whether the value is in the first or second half of the array. The last point in the first half of the data set, a[3], is 9, which is smaller than the value we are looking for. Hence, we should look in the second half of the array for a match, that is, in the sequence:

Now the last value of the first half of this sequence is 17; hence, the value must be located in the sequence:

The last value of the first half of this very short sequence is 12, which is smaller than the value that we are searching, so we must look in the second half:

It is trivial to see that we don't have a match, because 15 ≠ 17. If we wanted to insert 15 into the sequence, we would need to insert it just before a[5].

This search process is called a binary search, because we cut the size of the search in half in each step. That cutting in half works only because we know that the sequence of values is sorted.

The following class implements binary searches in a sorted array of integers. The search method returns the position of the match if the search succeeds, or −1 if v is not found in a.

ch14/binsearch/BinarySearcher.java

1  /**
2     A class for executing binary searches through an array.
3  */
4  public class BinarySearcher
5  {
6     private int[] a;
7
8     /**
9        Constructs a BinarySearcher.
10        @param anArray a sorted array of integers
11     */
12     public BinarySearcher(int[] anArray)
13     {
14        a = anArray;
15     }
16
17     /**
18        Finds a value in a sorted array, using the binary
19        search algorithm.
20        @param v the value to search
21        @return the index at which the value occurs, or −1
22        if it does not occur in the array
23     */

24     public int search(int v)
25     {
26        int low = 0;
27        int high = a.length - 1;
28        while (low <= high)
29        {
30           int mid = (low + high) / 2;
31           int diff = a[mid] - v;
32
33           if (diff == 0) // a[mid] == v
34              return mid;
35           else if (diff < 0) // a[mid] < v
36              low = mid + 1;
37             else
38                high = mid - 1;
39          }
40          return −1;
41       }
42    }

Now let's determine the number of visits to array elements required to carry out a binary search. We can use the same technique as in the analysis of merge sort. Because we look at the middle element, which counts as one visit, and then search either the left or the right subarray, we have

Using the same equation,

By plugging this result into the original equation, we get

That generalizes to

As in the analysis of merge sort, we make the simplifying assumption that n is a power of 2, n = 2^m, where m = log₂(n). Then we obtain

Therefore, binary search is an O(log(n)) algorithm.

That result makes intuitive sense. Suppose that n is 100. Then after each search, the size of the search range is cut in half, to 50, 25, 12, 6, 3, and 1. After seven comparisons we are done. This agrees with our formula, because log₂(100) ≈ 6.64386, and indeed the next larger power of 2 is 2⁷ = 128.

Because a binary search is so much faster than a linear search, is it worthwhile to sort an array first and then use a binary search? It depends. If you search the array only once, then it is more efficient to pay for an O(n) linear search than for an O(n log(n)) sort and an O(log(n)) binary search. But if you will be making many searches in the same array, then sorting it is definitely worthwhile.

The Arrays class contains a static binarySearch method that implements the binary search algorithm, but with a useful enhancement. If a value is not found in the array, then the returned value is not −1, but −k − 1, where k is the position before which the element should be inserted. For example,

int[] a = { 1, 4, 9 };
int v = 7;
int pos = Arrays.binarySearch(a, v);
   // Returns −3; v should be inserted before position 2

14. Why is it useful that the Arrays.binarySearch method indicates the position where a missing element should be inserted?

15. Why does Arrays.binarySearch return −k − 1 and not −k to indicate that a value is not present and should be inserted before position k?

When you write Java programs, you don't have to implement your own sorting algorithms. The Arrays class contains static sort methods to sort arrays of integers and floating-point numbers. For example, you can sort an array of integers simply as

int[] a = ...;
Arrays.sort(a);

That sort method uses the quicksort algorithm—see Special Topic 14.3 on page 611 for more information about that algorithm.

Of course, in application programs, there is rarely a need to search through a collection of integers. However, it is easy to modify these techniques to search through real data.

The Arrays class also supplies a static sort method for sorting arrays of objects. However, the Arrays class cannot know how to compare arbitrary objects. Suppose, for example, that you have an array of Coin objects. It is not obvious how the coins should be sorted. You could sort them by their names, or by their values. The Arrays.sort method cannot make that decision for you. Instead, it requires that the objects belong to classes that implement the Comparable interface. That interface has a single method:

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

The call

a.compareTo(b)

must return a negative number if a should come before b, 0 if a and b are the same, and a positive number otherwise.

Several classes in the standard Java library, such as the String and Date classes, implement the Comparable interface.

You can implement the Comparable interface for your own classes as well. For example, to sort a collection of coins, the Coin class would need to implement this interface and declare a compareTo method:

public class Coin implements Comparable
{
    ...
   public int compareTo(Object otherObject)
   {
      Coin other = (Coin) otherObject;
       if (value < other.value) return −1;
       if (value == other.value) return 0;
      return 1;
   }
    ...
}

When you implement the compareTo method of the Comparable interface, you must make sure that the method defines a total ordering relationship, with the following three properties:

Once your Coin class implements the Comparable interface, you can simply pass an array of coins to the Arrays.sort method:

Coin[] coins = new Coin[n];
// Add coins
...
Arrays.sort(coins);

If the coins are stored in an ArrayList, use the Collections.sort method instead; it uses the merge sort algorithm:

ArrayList<Coin> coins = new ArrayList<Coin>();
// Add coins
...
Collections.sort(coins);

As a practical matter, you should use the sorting and searching methods in the Arrays and Collections classes and not those that you write yourself. The library algorithms have been fully debugged and optimized. Thus, the primary purpose of this chapter was not to teach you how to implement practical sorting and searching algorithms. Instead, you have learned something more important, namely that different algorithms can vary widely in performance, and that it is worthwhile to learn more about the design and analysis of algorithms.

17. What steps would you need to take to sort an array of BankAccount objects by increasing balance?

if (a.compareTo(b) == −1) // ERROR!

if (a.compareTo(b) < 0) // OK

char c1 = charAt(i);
char c2 = other.charAt(i);

if (c1 != c2) return c1 - c2;

public interface Comparable<T>
{
   int compareTo(T other)
}

public class Coin implements Comparable<Coin>
{
    ...
   public int compareTo(Coin other)
   {
       if (value < other.value) return −1;
       if (value == other.value) return 0;
      return 1;
   }
    ...
}

public interface Comparator<Coin>
{
   int compare(Coin a, Coin b);
}

comp.compare(a, b)

public class CoinComparator implements Comparator<Coin>
{
   public int compare(Coin a, Coin b)
    {
       if (a.getValue() < b.getValue()) return −1;
       if (a.getValue() == b.getValue()) return 0;
      return 1;
    }
}

Arrays.sort(coins, new CoinComparator());

java.lang.Comparable<T>            java.util.Collections
   compareTo                                binarySearch
java.lang.System                            sort
   currentTimeMillis                     java.util.Comparator<T>
java.util.Arrays                            compare
   binarySearch
     sort
     toString

Review Exercises

R14.1 What is the difference between searching and sorting?

R14.2 Checking against off-by-one errors. When writing the selection sort algorithm of Section 14.1, a programmer must make the usual choices of < against <=, a.length against a.length - 1, and from against from + 1. This is a fertile ground for off-by-one errors. Conduct code walkthroughs of the algorithm with arrays of length 0, 1, 2, and 3 and check carefully that all index values are correct.

R14.3 For the following expressions, what is the order of the growth of each?

1. n² + 2n + 1

2. n¹⁰ + 9n⁹ + 20n⁸ + 145n⁷

3. (n + 1)⁴

4. (n² + n)²

5. n + 0.001n³

6. n³ − 1000n² + 10⁹

7. n + log(n)

8. n² + n log(n)

9. 2ⁿ + n²

10. 

R14.4 We determined that the actual number of visits in the selection sort algorithm is

We characterized this method as having O(n²) growth. Compute the actual ratios

T(2.000)/T(1.000)

T(4.000)/T(1.000)

T(10.000)/T(1.000)

and compare them with

f(2.000)/f(1.000)

f(2.000)/f(1.000)

f(2.000)/f(1.000)

where f(n) = n².

R14.5 Suppose algorithm A takes 5 seconds to handle a data set of 1,000 records. If the algorithm A is an O(n) algorithm, how long will it take to handle a data set of 2,000 records? Of 10,000 records?

R14.6 Suppose an algorithm takes 5 seconds to handle a data set of 1,000 records. Fill in the following table, which shows the approximate growth of the execution times depending on the complexity of the algorithm.

	O(n)	O(n2)	O(n3)	O(nlog(n))	O(2n)
1,000	5	5	5	5	5
2,000
3,000		45
10,000

For example, because 3,000²/1,000² = 9, the algorithm would take 9 times as long, or 45 seconds, to handle a data set of 3,000 records.

R14.7 Sort the following growth rates from slowest to fastest growth.

R14.8 What is the growth rate of the standard algorithm to find the minimum value of an array? Of finding both the minimum and the maximum?

R14.9 What is the growth rate of the following method?

public static int count(int[] a, int c)
{
   int count = 0;

   for (int i = 0; i < a.length; i++)
   {
      if (a[i] == c) count++;
   }
   return count;
}

R14.10 Your task is to remove all duplicates from an array. For example, if the array has the values

4 7 11 4 9 5 11 7 3 5

then the array should be changed to

4 7 11 9 5 3

Here is a simple algorithm. Look at a[i]. Count how many times it occurs in a. If the count is larger than 1, remove it. What is the growth rate of the time required for this algorithm?

R14.11 Consider the following algorithm to remove all duplicates from an array. Sort the array. For each element in the array, look at its next neighbor to decide whether it is present more than once. If so, remove it. Is this a faster algorithm than the one in Exercise R14.10?

R14.12 Develop an O(nlog(n)) algorithm for removing duplicates from an array if the resulting array must have the same ordering as the original array.

R14.13 Why does insertion sort perform significantly better than selection sort if an array is already sorted?

R14.14 Consider the following speedup of the insertion sort algorithm of Special Topic 14.1 on page 604. For each element, use the enhanced binary search algorithm that yields the insertion position for missing elements. Does this speedup have a significant impact on the efficiency of the algorithm?

Programming Projects

Project 14.1 Write a program that keeps an appointment book. Make a class Appointment that stores a description of the appointment, the appointment day, the starting time, and the ending time. Your program should keep the appointments in a sorted array list. Users can add appointments and print out all appointments for a given day. When a new appointment is added, use binary search to find where it should be inserted in the array list. Do not add it if it conflicts with another appointment.

Project 14.2 Implement a graphical animation of sorting and searching algorithms. Fill an array with a set of random numbers between 1 and 100. Draw each array element as a bar, as in Figure 3. Whenever the algorithm changes the array, wait for the user to click the Step button, then call the repaint method. The Run button should run the animation until the animation has finished or the user clicks the Step button again.

Animate selection sort, merge sort, and binary search. In the binary search animation, highlight the currently inspected element and the current values of from and to.

Figure 14.3. Graphical Animation