Sorting Out What You Learned

In this chapter, you learned the following:

• An invariant describes the data being used in a loop. The initial values for the variables used in the loop will establish the invariant, and the work done inside the loop will make progress toward the solution. When the loop terminates, the invariant is still true, but the solution will have been reached.

• Linear search is the simplest way to find a value in a list, but on average, the time required is directly proportional to the length of the list.

• Binary search is much faster—the average time is proportional to the logarithm of the list’s length—but it works only if the list is in sorted order.

• Similarly, the average running time of simple sorting algorithms like selection sort is proportional to the square of the input size N, whereas the running time of more complex sorting algorithms grows as N log₂ N.

• Looking at how the running time of an algorithm grows as a function of the size of its inputs is the standard way to analyze and compare the algorithm’s efficiency.

• Selection sort and insertion sort have almost the same invariant; the only difference is that with selection sort, the sorted section contains values that are smaller than all the values in the unsorted section. The two algorithms differ by how they make progress: selection sort selects the next-smallest item to put at the end of the sorted section, whereas insertion sort inserts the next item into the sorted section.