Efficiency of iterative binary search

How much better is binary search than linear search? When we analyzed the linear search in Section 6.7, we counted the worst case number of comparisons between the target and a list item, so let’s perform the same analysis for binary search. Since the binary search contains a while loop, we will need to think more carefully this time about when the worst case happens.

In the worst case, the while loop will iterate all the way until left > right. Therefore, the worst case number of item comparisons will be necessary when the item we seek is not found in the list. Let’s start by thinking about the worst case number of item comparisons for some small lists. First, suppose we have a list with length n = 4. In the worst case, we first look at the item in the middle of this list, and then are faced with searching a sublist with length 2. Next, we look at the middle item of this sublist and, upon not finding the item, search a sublist of length 1. After one final comparison to this single item, the algorithm will return –1. So we needed a total of 3 comparisons for a list of length 4.

After we compare the middle item in a list with length n = 8 to our target, we are left with a sublist with length 4. We already know that a list with length 4 requires 3 comparisons in the worst case, so a list with length 8 must require 3+1 = 4 comparisons in the worst case. Similarly, a list with length 16 must require only one more comparison than a list with length 8, for a total of 5. And so on. This pattern is summarized in Table 11.1. Notice that a list with over a billion items requires at most 31 comparisons!

In each row of the table, the length of the list (n) is 2 raised to the power of 1 less than the number of comparisons (c), or

n = 2^c–1.

Therefore, for a list of size n, the binary search requires

c = log₂ n + 1

comparisons in the worst case. So binary search is a logarithmic-time algorithm. Since the time complexity of linear search is proportional to n, this means that linear search is exponentially slower than binary search.

This is a degree of speed-up that is only possible through algorithmic refinement; a faster computer simply cannot have this kind of impact. Figure 11.1 shows a comparison of actual running times of both search algorithms on some small lists. The time required by binary search is barely discernible as the red line parallel to the x-axis. But the real power of binary search becomes evident on very long lists. As suggested by Table 11.1, a binary search takes almost no time at all, even on huge lists, whereas a linear search, which must potentially examine every item, can take a very long time.

A spelling checker

Now let’s apply our binary search to the spelling checker problem with which we started this section. We can write a program that reads an alphabetized word list, and then allows someone to repeatedly enter a word to see if it is spelled correctly (i.e., is present in the list of words). A list of English words can be found on computers running Mac OS X or Linux in the file /usr/share/dict/words, or one can be downloaded from the book web site. This list is already sorted if you consider an upper case letter to be equivalent to its lower case counterpart. (For example, “academy” directly precedes “Acadia” in this file.) However, as we saw in Chapter 6, Python considers upper case letters to come before lower case letters, so we actually still need to sort the list to have it match Python’s definition of “sorted.” For now, we can use the sort method; in the coming sections, we will develop our own sorting algorithms. The following function implements our spelling checker.

def spellcheck():
    """Repeatedly ask for a word to spell-check and print the result.

    Parameters: none

    Return value: None
    """

    dictFile = open('/usr/share/dict/words', 'r', encoding = 'utf-8')
    wordList = [ ]

    for word in dictFile:
        wordList.append(word[:-1])
    dictFile.close()
    wordList.sort()

    word = input('Enter a word to spell-check (q to quit): ')
    while word != 'q':
        index = binarySearch(wordList, word)
        if index != -1:
            print(word, 'is spelled correctly.')
        else:
            print(word, 'is not spelled correctly.')
        print()
        word = input('Enter a word to spell-check (q to quit): ')

The function begins by opening the word list file and reading each word (one word per line) into a list. Since each line ends with a newline character, we slice it off before adding the word to the list. After all of the words have been read, we sort the list. The following while loop repeatedly prompts for a word until the letter q is entered. Notice that we ask for a word before the while loop to initialize the value of word, and then again at the bottom of the loop to set up for the next iteration. In each iteration, we call the binary search function to check if the word is contained in the list. If the word was found (index != -1), we state that it is spelled correctly. Otherwise, we state that it is not spelled correctly.

Recursive binary search

You may have noticed that the binary search algorithm displays a high degree of self-similarity. In each step, the problem is reduced to solving a subproblem involving half of the original list. In particular, the problem of searching for an item between indices left and right is reduced to the subproblem of searching between left and mid - 1, or the subproblem of searching between mid + 1 and right. Therefore, binary search is a natural candidate for a recursive algorithm.

Like the recursive linear search from Section 10.4, this function will need two base cases. In the first base case, when the list is empty (left > right), we return -1. In the second base case, keys[mid] == item, so we return mid. If neither of these cases holds, we solve one of the two subproblems recursively. If the item we are searching for is less than the middle item, we recursively call the binary search with the right argument set to mid - 1. Or, if the item we are searching for is greater than the middle item, we recursively call the binary search with the left argument set to mid + 1.

def binarySearch(keys, target, left, right):
    """Recursively find the index of target in a sorted list of keys.

    Parameters:
        keys: a list of key values
        target: a value for which to search

    Return value:
        the index of an occurrence of target in keys
    """

    if left > right:              # base case 1: not found
        return -1
    mid = (left + right) // 2
    if target == keys[mid]:       # base case 2: found
        return mid
    if target < keys[mid]:        # recursive cases
        return binarySearch(keys, target, left, mid - 1)  # 1st half
    return binarySearch(keys, target, mid + 1, right)     # 2nd half

Efficiency of recursive binary search

Like the iterative binary search, this algorithm also has logarithmic time complexity. But, as with the recursive linear search, we have to derive this result differently using a recurrence relation. Again, let the function T(n) denote the maximum (worst case) number of comparisons between the target and a list item in a binary search when the length of the list is n. In the function above, there are two such comparisons before reaching a recursive function call. As we did in Section 10.4, we will simply represent the number of comparisons before each recursive call with the constant c. When n = 0, we reach a base case with no recursive calls, so T(0) = c.

Since each recursive call divides the size of the list under consideration by (about) half, the size of the list we are passing into each recursive call is (about) n/2. Therefore, the number of comparisons in each recursive call must be T(n/2). The total number of comparisons is then

T(n) = T (n/2) + c.

Now we can use the same substitution method that we used with recursive linear search to arrive at a closed form expression in terms of n. First, since T(n) = T(n/2) + c, we can substitute T(n) with T(n/2) + c:

Now we need to replace T(n/2) with something. Notice that T(n/2) is just T(n) with n/2 substituted for n. Therefore, using the definition of T(n) above,

T (n/2) = T (n/2/2) + c = T (n/4) + c.

Similarly,

T (n/4) = T (n/4/2) + c = T (n/8) + c

and

T (n/8) = T (n/8/2) + c = T (n/16) + c.

This sequence of substitutions is illustrated in Figure 11.2. Notice that the denominator under the n at each step is a power of 2 whose exponent is the multiplier in front of the accumulated c’s at that step. In other words, for each denominator 2ⁱ, the accumulated value on the right is i · c. When we finally reach T(1) = T(n/n), the denominator has become n = 2^{log₂ n}, so i = log₂ n and the total on the right must be (log₂ n)c. Finally, we know that T(0) = c, so the total number of comparisons is

T(n) = (log₂ n + 2) c.

Therefore, as expected, the recursive binary search is a logarithmic-time algorithm.

Exercises

11.1.1. How would you modify each of the binary search functions in this section so that, when a target is not found, the function also prints the values in keys that would be on either side of the target if it were in the list?

11.1.2. Write a function that takes a file name as a parameter and returns the number of misspelled words in the file. To check the spelling of each word, use binary search to locate it in a list of words, as we did above. (Hint: use the strip string method to remove extraneous punctuation.)

11.1.3. Write a function that takes three parameters—minLength, maxLength, and step—and produces a plot like Figure 11.1 comparing the worst case running times of binary search and linear search on lists with length minLength, minLength + step, minLength + 2 * step, ..., maxLength. Use a slice of the list derived from list(range(maxLength)) as the sorted list for each length. To produce the worst case behavior of each algorithm, search for an item that is not in the list (e.g., –1).

11.1.4. The function below plays a guessing game against the pseudorandom number generator. What is the worst case number of guesses necessary for the function to win the game for any value of n, where n is a power of 2? Explain your answer.

import random

def guessingGame(n):
    secret = random.randrange(1, n + 1)
    left = 1
    right = n
    guessCount = 1
    guess = (left + right) // 2
    while guess != secret:
        if guess > secret:
            right = guess - 1
        else:
            left = guess + 1
        guessCount = guessCount + 1
        guess = (left + right) // 2
    return guessCount

Implementing selection sort

Now let’s look at how we can implement this algorithm, using a more detailed representation of this list which, as usual, we will name data:

To begin, we want to search for the smallest value in the list, and swap it with the value at index 0. We have already seen how to accomplish key parts of this step. First, writing a function

swap(data, i, j)

to swap two values in a list was the objective of Exercise 8.2.5. In this swap function, i and j are the indices of the two values in the list data that we want to swap. And on Page 354, we developed a function to find the minimum value in a list. The min function used the following algorithm:

minimum = data[0]
for item in data[1:]:
    if item < minimum:
        minimum = item

The variable named minimum is initialized to the first value in the list, and updated with smaller values as they are encountered in the list.

Unfortunately, it is not quite that easy. To swap the positions of two values in data, we need to know their indices rather than their values. Therefore, in our selection sort algorithm, we will need to substitute minimum with a reference to the index of the minimum value. Let’s call this new variable minIndex. This substitution results in the following alternative algorithm.

n = len(data)
minIndex = 0
for index in range(1, n):
    if data[index] < data[minIndex]:
        minIndex = index

Notice that this algorithm is really the same as the previous algorithm; we are just now referring to the minimum value indirectly through its index (data[minIndex]) instead of directly through the variable minimum. Once we have the index of the minimum value in minIndex, we can swap the minimum value with the value at index 0 by calling

if minIndex != 0:
    swap(data, 0, minIndex)

In our example list, these steps will find the smallest value, 10, at index 4, and then call swap(data, 0, 4). We first check if minIndex != 0 so we do not needlessly swap the value in position 0 with itself. This swap results in the following modified list:

In the next step, we need to do almost exactly the same thing, but for the second smallest value.

Notice that, now that the smallest value is “out of the way” at the front of the list, the second smallest value in data must be the smallest value in data[1:]. Therefore, we can use exactly the same process as above, but on data[1:] instead. This requires only four small changes in the code, marked in red below.

minIndex = 1
for index in range(2, n):
    if data[index] < data[minIndex]:
        minIndex = index
if minIndex != 1:
    swap(data, 1, minIndex)

Instead of initializing minIndex to 0 and starting the for loop at 1, we initialize minIndex to 1 and start the for loop at 2. Then we swap the smallest value into position 1 instead of 0. In our example list, this will find the smallest value in data[1:], 20, at index 3. Then it will call swap(data, 1, 3), resulting in the following modified list:

Similarly, the next step is to find the index of the smallest value starting at index 2, and then swap it with the value in index 2:

minIndex = 2
for index in range(3, n):
    if data[index] < data[minIndex]:
        minIndex = index
if minIndex != 2:
    swap(data, 2, minIndex)

In our example list, this will find the smallest value in data[2:], 30, at index 3. Then it will call swap(data, 2, 3), resulting in:

We continue by repeating this sequence of steps, with increasing values of the numbers in red, until we reach the end of the list.

To implement this algorithm in a function that works for any list, we need to situate the repeated sequence of steps in a loop that iterates over the increasing values in red. We can do this by replacing the initial value of minIndex in red with a variable named start:

minIndex = start
for index in range(start + 1, n):
    if data[index] < data[minIndex]:
        minIndex = index
if minIndex != start:
    swap(data, start, minIndex)

Then we place these steps inside a for loop that has start take on all of the integers from 0 to n - 2:

 1 def selectionSort(data):
 2     """Sort a list of values in ascending order using the
 3        selection sort algorithm.
 4
 5     Parameter:
 6         data: a list of values
 7
 8     Return value: None
 9     """
10
11     n = len(data)
12     for start in range(n - 1):
13         minIndex = start
14         for index in range(start + 1, n):
15             if data[index] < data[minIndex]:
16                 minIndex = index
17         if minIndex != start:
18             swap(data, start, minIndex)

Because the comparison operators are defined for both numbers and strings, we can use our selectionSort function to sort either kind of data. For example, call selectionSort on each of the following lists, and then print the results. (Remember to incorporate the swap function from Exercise 8.2.5.)

numbers = [50, 30, 40, 20, 10, 70, 60]
animals = ['dog', 'cat', 'monkey', 'zebra', 'platypus', 'armadillo']
heights = [7.80, 6.42, 8.64, 7.83, 7.75, 8.99, 9.25, 8.95]

Efficiency of selection sort

Next, let’s look at the time complexity of the selection sort algorithm. We can derive the asymptotic time complexity by counting the number of times the most frequently executed elementary step executes. The most frequently executed step in the selectionSort function is the comparison in the if statement on line 15. Since line 15 is in the body of the inner for loop (on line 14) and this inner for loop iterates a different number of times for each value of start in the outer for loop (on line 12), we must ask how many times the inner for loop iterates for each value of start. When start is 0, the inner for loop on line 14 runs from 1 to n – 1, for a total of n – 1 iterations. So line 15 is also executed n – 1 times. Next, when start is 1, the inner for loop runs from 2 to n – 1, a total of n – 2 iterations, so line 15 is executed n – 2 times. With each new value of start, there is one less iteration of the inner for loop. Therefore, the total number of times that line 15 is executed is

(n – 1) + (n – 2) + (n – 3) + …

Where does this sum stop? To find out, we look at the last iteration of the outer for loop, when start is n - 2. In this case, the inner for loop runs from n - 1 to n - 1, for only one iteration. So the total number of steps is

(n – 1) + (n – 2) + (n – 3) + … + 3 + 2 + 1.

What is this sum equal to? You may recall that we have encountered this sum a few times before (see Box 4.2):

Ignoring the constant 1/2 in front of n² and the low order term (1/2)n, we find that this expression is asymptotically proportional to n²; hence selection sort has quadratic time complexity.

Figure 11.3 shows the results of an experiment comparing the running time of selection sort to the sort method of the list class. (Exercise 11.3.4 asks you to replicate this experiment.) The parabolic blue curve in Figure 11.3 represents the quadratic time complexity of the selection sort algorithm. The red curve at the bottom of Figure 11.3 represents the running time of the sort method. Although this plot compares the algorithms on very small lists on which both algorithms are very fast, we see a marked difference in the growth rates of the execution times. We will see why the sort method is so much faster in Section 11.4.

Querying data

Suppose we want to write a program that allows someone to query the USGS earthquake data that we worked with in Section 8.4. Although we did not use IDs then, each earthquake was identified by a unique ID such as ak10811825. The first two characters identify the monitoring network (ak represents the Alaska Regional Network) and the last eight digits represent a unique code assigned by the network. So our program needs to search for a given ID, and then return the attributes associated with that ID, say the earthquake’s latitude, longitude, magnitude, and depth. The earthquake IDs will act as keys, on which we will perform our searches. This associated data is sometimes called satellite data because it revolves around the key.

To use the efficient binary search algorithm in our program, we need to first sort the data by its key values. When we read this data into memory, we can either read it into parallel lists, as we did in Section 8.4, or we can read it into a table (i.e., a list of lists), as we did in Section 9.1. In this section, we will modify our selection sort algorithm to handle the first option. We will leave the second option as an exercise.

First, we will read the data into two lists: a list of keys (i.e., earthquake IDs) and a list of tuples containing the satellite data. For example, the satellite data for one earthquake that occurred at 19.5223 latitude and -155.5753 longitude with magnitude 1.1 and depth 13.6 km will be stored in the tuple (19.5223, -155.5753, 1.1, 13.6). Let’s call these two lists ids and data, respectively. (We will leave writing the function to read the IDs and data into their respective lists as an exercise.) By design, these two lists are parallel in the sense that the satellite data in data[index] belongs to the earthquake with ID in ids[index]. When we sort the earthquakes by ID, we will need to make sure that the associations with the satellite data are maintained. In other words, if, during the sort of the list ids, we swap the values in ids[9] and ids[4], we also need to swap data[9] and data[4].

To do this with our existing selection sort algorithm is actually quite simple. We pass both lists into the selection sort function, but make all of our sorting decisions based entirely on a list of keys. Then, when we swap two values in keys, we also swap the values in the same positions in data. The modified function looks like this (with changes in red):

def selectionSort(keys, data):
    """Sort parallel lists of keys and data values in ascending
       order using the selection sort algorithm.

    Parameters:
        keys: a list of keys
        data: a list of data values corresponding to the keys
                  
    Return value: None
    """
                  
    n = len(keys)
    for start in range(n - 1):
        minIndex = start
        for index in range(start + 1, n):
            if keys[index] < keys[minIndex]:
                minIndex = index
        swap(keys, start, minIndex)
        swap(data, start, minIndex)

Once we have the sorted parallel lists ids and data, we can use binary search to retrieve the index of a particular ID in the list ids, and then use that index to retrieve the corresponding satellite data from the list data. The following function does this repeatedly with inputted earthquake IDs.

def queryQuakes(ids, data):
    key = input('Earthquake ID (q to quit): ')
    while key != 'q':
        index = binarySearch(ids, key, 0, len(ids) - 1)
        if index >= 0:
            print('Location: ' + str(data[index][:2]) + '
' +
                  'Magnitude: ' + str(data[index][3]) + '
' +
                  'Depth: ' + str(data[index][2]) + '
')
        else:
            print('An earthquake with that ID was not found.')
        key = input('Earthquake ID (q to quit): ')

A main function that ties all three pieces together looks like this:

def main():
    ids, data = readQuakes()    # left as an exercise
    selectionSort(ids, data)
    queryQuakes(ids, data)

Exercises

11.2.1. Can you find a list of length 5 that requires more comparisons (on line 15) than another list of length 5? In general, with lists of length n, is there a worst case list and a best case list with respect to comparisons? How many comparisons do the best case and worst case lists require?

11.2.2. Now consider the number of swaps. Can you find a list of length 5 that requires more swaps (on line 18) than another list of length 5? In general, with lists of length n, is there a worst case list and a best case list with respect to swaps? How many swaps do the best case and worst case lists require?

11.2.3. The inner for loop of the selection sort function can be eliminated by using two built-in Python functions instead:

def selectionSort2(data):
    n = len(data)
    for start in range(n - 1):
        minimum = min(data[start:])
        minIndex = start + data[start:].index(minimum)
        if minIndex != start:
            swap(data, start, minIndex)

Is this function more or less efficient than the selectionSort function we developed above? Explain.

11.2.4. Suppose we already have a list that is sorted in ascending order, and want to insert new values into it. Write a function that inserts an item into a sorted list, maintaining the sorted order, without re-sorting the list.

11.2.5. Write a function that reads earthquake IDs and earthquake satellite data, consisting of latitude, longitude, depth and magnitude, from the data file on the web at

http://earthquake.usgs.gov/earthquakes/feed/v1.0/summary/2.5_month.csv

and returns two parallel lists, as described on Page 559. The satellite data for each earthquake should be stored as a tuple of floating point values. Then use this function to complete a working version of the program whose main function is shown on Page 560. (Remember to incorporate the recursive binary search and the swap function from Exercise 8.2.5.) Look at the above URL in a web browser to find some earthquake IDs to search for or do the next exercise to have your program print a list of all of them.

11.2.6. Add to the queryQuakes function on Page 560 the option to print an alphabetical list of all earthquakes, in response to typing list for the earthquake ID. For example, the output should look something like this:

Earthquake ID (q to quit): ci37281696
Location: (33.4436667, -116.6743333)
Magnitude: 0.54
Depth: 13.69

Earthquake ID (q to quit): list
    ID             Location         Magnitude  Depth
----------  ----------------------  ---------  -----
ak11406701   (63.2397, -151.4564)         5.5    1.3
ak11406705   (58.9801, -152.9252)        69.2    2.3
ak11406708   (59.7555, -152.6543)        80.0    1.9
   ...

uw60913561   (41.8655, -119.6957)         0.2    2.4
uw60913616   (44.2917, -122.6705)         0.0    1.3

Earthquake ID (q to quit):

11.2.7. An alternative to storing the earthquake data in two parallel lists is to store it in one table (a list of lists or a list of tuples). For example, the beginning of a table containing the earthquakes shown in the previous exercise would look like this:

[['ak11406701', 63.2397, -151.4564, 5.5, 1.3],
 ['ak11406705', 58.9801, -152.9252, 69.2, 2.3],
 ...
]

Rewrite the readQuakes, selectionSort, binarySearch, and queryQuakes functions so that they work with the earthquake data stored in this way instead. Your functions should assume that the key value for each earthquake is in column 0. Combine your functions into a working program that is driven by the following main function:

def main():
    quakes = readQuakes()
    selectionSort(quakes)
    queryQuakes(quakes)

11.2.8. The Sieve of Eratosthenes is a simple algorithm for generating prime numbers that has a structure that is similar to the nested loop structure of selection sort. In this algorithm, we begin by initializing a list of n Boolean values named prime as follows. (In this case, n = 12.)

At the end of the algorithm, we want prime[index] to be False if index is not prime and True if index is prime. The algorithm continues by initializing a loop index variable to 2 (indicated by the arrow below) and then setting the list value of every multiple of 2 to be False.

Next, the loop index variable is incremented to 3 and, since prime[3] is True, the list value of every multiple of 3 is set to be False.

Next, the loop index variable is incremented to 4. Since prime[4] is False, we do not need to set any of its multiples to False, so we do not do anything.

This process continues with the loop index variable set to 5:

And so on. How far must we continue to increment index before we know we are done? Once we are done filling in the list, we can iterate over it one more time to build the list of prime numbers, in this case, [2, 3, 5, 7, 11]. Write a function that implements this algorithm to return a list of all prime numbers less than or equal to a parameter n.

Implementing insertion sort

To implement this algorithm, we need to repeatedly find the correct location to insert an item among the items to the left, assuming that the items to the left are already sorted. Let’s name the index of the item that we wish to insert insertIndex and the item itself itemToInsert. In other words, we assign

itemToInsert = data[insertIndex]

To illustrate, suppose that insertIndex is 4 (and itemToInsert is 10), as shown below:

We need to compare itemToInsert to each of the items to the left, first at index insertIndex - 1, then at insertIndex - 2, insertIndex - 3, etc. When we come to an item that is less than or equal to itemToInsert or we reach the beginning of the list, we know that we have found the proper location for the item. This process can be expressed with a while loop:

itemToInsert = data[insertIndex]
index = insertIndex - 1
while index >= 0 and data[index] > itemToInsert:
    index = index - 1

The variable named index tracks which item we are currently comparing to itemToInsert. The value of index is decremented while it is still at least zero and the item at position index is still greater than itemToInsert. At the end of the loop, because the while condition has become false, either index has reached -1 or data[index] <= itemToInsert. In either case, we want to insert itemToInsert into position index + 1. In the example above, we would reach the beginning of the list, so we want to insert itemToInsert into position index + 1 = 0.

To actually insert itemToInsert in its correct position, we need to delete itemToInsert from its current position, and insert it into position index + 1.

data.pop(insertIndex)
data.insert(index + 1, itemToInsert)

In the insertion sort algorithm, we want to repeat this process for each value of insertIndex, starting at 1, so we enclose these steps in a for loop:

def insertionSort(data):
    """Sort a list of values in ascending order using the
       insertion sort algorithm.

     Parameter:
         data: a list of values

     Return value: None
     """

     n = len(data)
     for insertIndex in range(1, n):
         itemToInsert = data[insertIndex]
         index = insertIndex - 1
         while index >= 0 and data[index] > itemToInsert:
             index = index - 1
         data.pop(insertIndex)
         data.insert(index + 1, itemToInsert)

Although this function is correct, it performs more work than necessary. To see why, think about how the pop and insert methods must work, based on the picture of the list on Page 564. First, to delete (pop) itemToInsert, which is at position insertIndex, all of the items to the right, from position insertIndex + 1 to position n - 1, must be shifted one position to the left. Then, to insert itemToInsert into position index + 1, all of the items to the right, from position index + 2 to n - 1, must be shifted one position to the right. So the items from position insertIndex + 1 to position n - 1 are shifted twice, only to end up back where they started.

A more efficient technique would be to only shift those items that need to be shifted, and do so while we are already iterating over them. The following modified algorithm does just that.

 1 def insertionSort(data):
 2     """ (docstring omitted) """
 3
 4     n = len(data)
 5     for insertIndex in range(1, n):
 6         itemToInsert = data[insertIndex]
 7         index = insertIndex - 1
 8         while index >= 0 and data[index] > itemToInsert:
 9             data[index + 1] = data[index]
10             index = index - 1
11         data[index + 1] = itemToInsert

The red assignment statement in the for loop copies each item at position index one position to the right. Therefore, when we get to the end of the loop, position index + 1 is available to store itemToInsert.

Efficiency of insertion sort

Is the insertion sort algorithm any more efficient than selection sort? To discover its time complexity, we first need to identify the most frequently executed elementary step(s). In this case, these appear to be the two assignment statements on lines 9–10 in the body of the while loop. However, the most frequently executed step is actually the test of the while loop condition on line 8. To see why, notice that the condition of a while loop is always tested when the loop is first reached, and again after each iteration. Therefore, a while loop condition is always tested once more than the number of times the while loop body is executed. As we did with selection sort, we will count the number of times the while loop condition is tested for each value of the index in the outer for loop.

Unlike with selection sort, we need to think about the algorithm’s best case and worst case behavior since the number of iterations of the while loop depends on the values in the list being sorted.

In the best case, it is possible that the item immediately to the left of itemToInsert is less than itemToInsert, and therefore the condition is tested only once. Therefore, since there are n – 1 iterations of the outer for loop, there are only n – 1 steps total for the entire algorithm. So, in the best case, insertion sort is a linear-time algorithm.

On the other hand, in the worst case, itemToInsert may be the smallest item in the list and the while loop executes until index is less than 0. Since index is initialized to insertIndex - 1, the condition on line 8 is tested with index equal to insertIndex - 1, then insertIndex - 2, then insertIndex - 3, etc., until index is -1, at which time the while loop ends. In all, this is insertIndex + 1 iterations of the while loop. Therefore, when insertIndex is 1 in the outer for loop, there are two iterations of the while loop; when insertIndex is 2, there are three iterations of the while loop; when insertIndex is 3, there are four iterations of the while loop; etc. In total, there are 2 + 3 + 4 + … iterations of the while loop. As we did with selection sort, we need to figure out when this pattern ends. Since the last value of insertIndex is n - 1, the while loop condition is tested at most n times in the last iteration. So the total number of iterations of the while loop is

2 + 3 + 4 + … + (n – 1) + n.

Using the same trick we used with selection sort, we find that the total number of steps is

Ignoring the constants and lower order terms, this means that insertion sort is also a quadratic-time algorithm in the worst case.

So which case is more representative of the efficiency of insertion sort, the best case or the worst case? Computer scientists are virtually always interested in the worst case over the best case because the best case scenario for an algorithm is usually fairly specific and very unlikely to happen in practice. On the other hand, the worst case gives a robust upper limit on the performance of the algorithm. Although more challenging, it is also possible to find the average case complexity of some algorithms, assuming that all possible cases are equally likely to occur.

We can see from Figure 11.4 that the running time of insertion sort is almost identical to that of selection sort in practice. Since the best case and worst case of selection sort are the same, it appears that the worst case analysis of insertion sort is an accurate measure of performance on random lists. Both algorithms are still significantly slower than the built-in sort method, and this difference is even more apparent with longer lists. We will see why in the next section.

Exercises

11.3.1. Give a particular 10-element list that requires the worst case number of comparisons in an insertion sort. How many comparisons are necessary for this list?

11.3.2. Give a particular 10-element list that requires the best case number of comparisons in an insertion sort. How many comparisons are necessary for this list?

11.3.3. Write a function that compares the time required to sort a long list of English words using insertion sort to the time required by the sort method of the list class.

We can use the function time in the module of the same name to record the time required to execute each function. The time.time() function returns the number of seconds that have elapsed since January 1, 1970; so we can time a function by getting the current time before and after we call the function, and finding the difference.

As we saw in Section 11.1, a list of English words can be found on computers running Mac OS X or Linux in the file /usr/share/dict/words, or one can be downloaded from the book web site. This list is already sorted if you consider an upper case letter to be equivalent to its lower case counterpart. However, since Python considers upper case letters to come before lower case letters, the list is not sorted for our purposes.

Notes:

• When you read in the list of words, remember that each line will end with a newline character. Be sure to remove that newline character before adding the word to your list.

• Make a separate copy of the original list for each sorting algorithm. If you pass a list that has already been sorted by the sort method to your insertion sort, you will not get a realistic time measurement because a sorted list is a best case scenario for insertion sort.

How many seconds did each sort require? (Be patient; insertion sort will take several minutes!) If you can be really patient, try timing selection sort as well.

11.3.4. Write a function

sortPlot(minLength, maxLength, step)

that produces a plot like Figure 11.4 comparing the running times of insertion sort, selection sort, and the sort method of the list class on shuffled lists with length minLength, minLength + step, minLength + 2 * step, ..., maxLength. At the beginning of your function, produce a shuffled list with length maxLength with

data = list(range(maxLength))
random.shuffle(data)

Then time each function for each list length using a new, unsorted slice of this list.

11.3.5. A sorting algorithm is called stable if two items with the same value always appear in the sorted list in the same order as they appeared in the original list. Are selection sort and insertion sort stable sorts? Explain your answer in each case.

11.3.6. A third simple quadratic-time sort is called bubble sort because it repeatedly “bubbles” large items toward the end of the list by swapping each item repeatedly with its neighbor to the right if it is larger than this neighbor.

For example, consider the short list [3, 2, 4, 1]. In the first pass over the list, we compare pairs of items, starting from the left, and swap them if they are out of order. The illustration below depicts in red the items that are compared in the first pass, and the arrows depict which of those pairs are swapped because they are out of order.

At the end of the first pass, we know that the largest item (in blue) is in its correct location at the end of the list. We now repeat the process above, but stop before the last item.

After the second pass, we know that the two largest items (in blue) are in their correct locations. On this short list, we make just one more pass.

After n – 1 passes, we know that the last n – 1 items are in their correct locations. Therefore, the first item must be also, and we are done.

1 2 3 4

Write a function that implements this algorithm.

11.3.7. In the bubble sort algorithm, if no items are swapped during a pass over the list, the list must be in sorted order. So the bubble sort algorithm can be made somewhat more efficient by detecting when this happens, and returning early if it does. Write a function that implements this modified bubble sort algorithm. (Hint: replace the outer for loop with a while loop and introduce a Boolean variable that controls the while loop.)

11.3.8. Write a modified version of the insertion sort function that sorts two parallel lists named keys and data, based on the values in keys, like the parallel list version of selection sort on Page 559.

Internal vs. external sorting

We have been assuming that the data that we want to sort is small enough to fit in a list in a computer’s memory. The selection and insertion sort algorithms must have the entire list in memory at once because they potentially pass over the entire list in each iteration of their outer loops. For this reason, they are called internal sorting algorithms.

But what if the data is larger than the few gigabytes that can fit in memory all at once? This is routinely the situation with real databases. In these cases, we need an external sorting algorithm, one that can sort a data set in secondary storage by just bringing pieces of it into memory at a time. The merge sort algorithm is just such an algorithm. In the merge function, each of the sorted halves could reside in a file on disk and just the current front item in each half can be read into memory at once. When the algorithm runs out of items in one of the sorted halves, it can simply read in some more. The merged list can also reside in a file on disk; when a new item is added to end of the merged result, it just needs to be written to the merged file after the previous item. Exercise 11.4.7 asks you to write a version of the merge function that merges two sorted files in this way.

Efficiency of merge sort

To discover the time complexity of merge sort, we need to set up a recurrence relation like the one we developed for the recursive binary search. We can again let T(n) represent the number of steps required by the algorithm with a list of length n. The mergeSort function consists of two recursive calls to mergeSort, each one with a list that is about half as long as the original. Like binary search, each of these recursive calls must require T(n/2) comparisons. But unlike binary search, there are two recursive calls instead of one. Therefore,

T(n) = 2T(n/2) + ?

where the question mark represents the number of steps in addition to the recursive calls, in particular to split data into left and right and to call the merge function.

Since every item in data is copied through slicing to one of the two lists, this must require about n steps.

Because either leftIndex or rightIndex is incremented in every iteration, the merge function iterates at most once for each item in the sorted list. So the total number of steps must be proportional to n. Therefore, the additional steps in the recurrence relation must also be proportional to n. Let’s call this number cn, where c is some constant. Then the final recurrence relation describing the number of steps in merge sort is

T(n) = 2T(n/2) + cn.

Finding a closed form for this recurrence is just slightly more complicated than it was for recursive binary search. Figure 11.8 illustrates the sequence of substitutions. Since there are two substitutions in each instance of the recurrence, the number of terms doubles in each level. But notice that the sum of the leftover values at each level is always equal to cn. As with the binary search recurrence, the size of the list (i.e., the argument of T) is divided in half with each level, so the number of levels is the same as it was with binary search, except that the base case with merge sort happens with n = 1 instead of n = 0. Looking back at Figure 11.2, we see that we reached n = 1 after log₂ n + 1 levels. Therefore, the total number of steps must be

T(n) = (log₂ n + 1) cn = cn log₂ n + cn,

which is proportional to n log₂ n asymptotically.

How much faster is this than the quadratic-time selection and insertion sorts? Figure 11.9 illustrates the difference by comparing the merge sort and selection sort functions on small randomly shuffled lists. The merge sort algorithm is much faster. Recall that the algorithm behind the built-in sort method is based on merge sort, which explains why it was so much faster than our previous sorts. Exercise 11.4.1 asks you to compare the algorithms on much longer lists as well.

Exercises

11.4.1. To keep things simple, assume that the selection sort algorithm requires exactly n² steps and the merge sort algorithm requires exactly n log₂ n steps. About how many times slower is selection sort than merge sort when n = 100? n = 1000? n = 1 million?

11.4.2. Repeat Exercise 11.3.3 with the merge sort algorithm. How does the time required by the merge sort algorithm compare to that of the insertion sort algorithm and the built-in sort method?

11.4.3. Add merge sort to the running time plot in Exercise 11.3.4. How does its time compare to the other sorts?

11.4.4. Our mergeSort function is a stable sort, meaning that two items with the same value always appear in the sorted list in the same order as they appeared in the original list. However, if we changed the <= operator in line 18 of the merge function to a < operator, it would no longer be stable. Explain why.

11.4.5. We have seen that binary search is exponentially faster than linear search in the worst case. But is it always worthwhile to use binary search over linear search?

The answer, as is commonly the case in the “real world”, is “it depends.” In this exercise, you will investigate this question. Suppose we have an unordered list of n items that we wish to search.

1. If we use the linear search algorithm, what is the time complexity of this search?
2. If we use the binary search algorithm, what is the time complexity of this search?
3. If we perform n (where n is also the length of the list) individual searches of the list, what is the time complexity of the n searches together if we use the linear search algorithm?
4. If we perform n individual searches with the binary search algorithm, what is the time complexity of the n searches together?
5. What can you conclude about when it is best to use binary search vs. linear search?

11.4.6. Suppose we have a list of n keys that we anticipate needing to search k times. We have two options: either we sort the keys once and then perform all of the searches using a binary search algorithm or we forgo the sort and simply perform all of the searches using a linear search algorithm. Suppose the sorting algorithm requires exactly n²/2 steps, the binary search algorithm requires log₂ n steps, and the linear search requires n steps. Assume each step takes the same amount of time.

1. If the length of the list is n = 1024 and we perform k = 100 searches, which alternative is better?
2. If the length of the list is n = 1024 and we perform k = 500 searches, which alternative is better?
3. If the length of the list is n = 1024 and we perform k = 1000 searches, which alternative is better?

11.4.7. Write a function that merges two sorted files into one sorted file. Your function should take the names of the three files as parameters. Assume that all three files contain one string value per line. Your function should not use any lists, instead reading only one item at a time from each input file and writing one item at a time to the output file. In other words, at any particular time, there should be at most one item from each file assigned to any variable in your function. You will know when you have reached the end of one of the input files when a read function returns the empty string. There are two files on the book web site that you can use to test your function.

Hard problems

Unfortunately, there are many common, simply stated problems for which the only known algorithms have exponential time complexity. For example, suppose we have n tasks to complete, each with a time estimate, that we wish to delegate to two assistants as evenly as possible. In general, there is no known way to solve this problem that is any better than trying all possible ways to delegate the tasks and then choosing the best solution. This type of algorithm is known as a brute force or exhaustive search algorithm. For this problem, there are two possible ways to assign each task (to one of the two assistants), so there are

possible ways to assign the n tasks. Therefore, the brute force algorithm has exponential time complexity. Referring back to Table 11.2, we see that even if we only have n = 50 tasks, the brute force algorithm would be of no use to us.

It turns out that there are thousands of such problems, known as the NP-hard problems, that, on the surface, do not seem as if they should be intractable, but, as far as we know, they are. Even more interesting, no one has actually proven that they are intractable. See Box 11.3 if you would like to know more about this fascinating problem.

When we cannot solve a problem exactly, one common approach is to instead use a heuristic. A heuristic is a type of algorithm that does not necessarily give a correct answer, but tends to work well in practice. For example, a heuristic for the task delegation problem might assign the tasks in order, always assigning the next task to the assistant with the least to do so far. Although this will not necessarily give the best solution, it may be “good enough” in practice.

Box 11.3: Does P = NP?

Project 11.1 Creating a searchable database

Write a program that allows for the interactive search of a data set, besides the earthquake data from Section 11.2, downloaded from the web or the book web site. It may be data that we have worked with elsewhere in this book or it may be a new data set. Your program, at a minimum, should behave like the program that we developed in Section 11.2. In particular, it should:

1. Read the data into a table or parallel lists.

2. Sort the data by an appropriate key value.

3. Interactively allow someone to query the data (by a key value). When a key value is found, the program should print the satellite data associated with that key. Use binary search to search for the key and return the results.

Project 11.2 Binary search trees

In this project, you will write a program that allows for the interactive search of a data set using an alternative data structure called a binary search tree (BST). Each key in a binary search tree resides in a node. Each node also contains references to a left child node and a right child node. The nodes are arranged so that the key of the left child of a node is less than or equal to the key of the node and the key of the right child is greater than the key of the node. For example, Figure 11.10 shows a binary search tree containing the numbers that we sorted in previous sections. The node at the top of the tree is called the tree’s root.

To insert a new item into a binary search tree, we start at the root. If the new item is less than or equal to the root, we next look at the left child. On the other hand, if the new item is greater than the root, we next look at the right child. Then we repeat this step on the next node, and continue until we arrive at a position without a node. Figure 11.11 illustrates how the value 35 would be inserted into the binary search tree in Figure 11.10. Starting at the root, since 35 < 50, we move to the left. Next, since 35 > 30, we next move to the right. Then, since 35 < 40, we move to the left. Since there is no node in this position, we create a new node with 35 and insert it there, as the left child of the node containing 40.

Searching a binary search tree follows the same process, except that we check whether the target value is equal to the key in each node that we visit. If it is, we return success. Otherwise, we move to the left or right, as we did above. If we eventually end up in a position without a node, we know that the target value was not found. For example, if we want to search for 20 in the binary search tree in Figure 11.10, we would start at the root and first move left because 20 < 50. Then we move left again because 20 < 30. Finally, we return success because we found our target. If we were searching for 25 instead, would have moved right when we arrived at node 20, but finding no node there, we would have returned failure.

In Python, we can represent a node in a binary search tree with a three-item list. As illustrated below, the first item in the list is the key, the second item is a list representing the left child node, and the third item is a list representing the right child node.

The list above represents a single node with no left or right child. Or, equivalently, we can think of the two empty lists as representing “empty” left and right children. To insert a child, we simply insert into one of the empty lists the items representing the desired node. For example, to make 70 the right child of the node above, we would insert a new node containing 70 into the second list:

[50, [ ], [70, [ ], [ ]]]

To insert 60 as the left child of 70, we would insert a new node containing 60 into the first list in 70:

[50, [ ], [70, [60, [ ], [ ]], [ ]]]

The list above now represents the root and the two nodes to the right of the root in Figure 11.10. Notice that an entire binary search tree can be represented by its root node. The complete binary search tree in Figure 11.10 looks like this:

bst = [50, [30, [20, [10, [], []], []], [40, [], []]],
           [70, [60, [], []], []]]

This representation quickly becomes difficult to read. But, luckily, we will rely on our functions to read them instead of us.

Let’s now implement the insert and search algorithms we discussed earlier, using this list implementation. To make our code easier to read, we will define three constant values representing the indices of the key, left child, and right child in a node:

KEY = 0
LEFT = 1
RIGHT = 2

So if node is the name of a binary search tree node, then node[KEY] is the node’s key value, node[LEFT] is the node’s left child, and node[RIGHT] is the node’s right child.

The following function inserts a new node into a binary search tree:

def insert(root, key):
    """Insert a new key into the BST with the given root.

    Parameters:
        root: the list representing the BST
        key: the key value to insert

    Return value: None
    """

    current = root
    while current != [ ]:
        if key <= current[KEY]:
            current = current[LEFT]
        else:
            current = current[RIGHT]
    current.extend([key, [ ], [ ]])

The variable named current keeps track of where we are in the tree during the insertion process. The while loop proceeds to “move” current left or right until current reaches an empty node. At that point, the loop ends, and the algorithm inserts a new node containing key by inserting key and two empty lists into the empty list assigned to current. (Recall that the extend method effectively appends each item in its list argument to the end of the list.) To use this function to insert the value 35 into our binary search tree named bst above, as in Figure 11.11, we would call insert(bst, 35).

The function to search a binary search tree is very similar:

def search(root, key):
    """Search for a target key in the BST with the given root.

    Parameters:
        root: the list representing the BST
        key: the key value to search for

    Return value: a Boolean indicating whether key was found
    """

    current = root
    while current != [ ] and current[KEY] != key:
        if key < current[KEY]:
            current = current[LEFT]
        else:
            current = current[RIGHT]
    return current != [ ]

The only differences in the search function are (a) the loop now also ends if we find the desired key value in the node assigned to current, and (b) at the end of the loop, we return False (failure) if current ends at an empty node and True otherwise.

In this project, you will work with a data set of your choice, downloaded from the web or the book web site. It may be data that we have worked with elsewhere in this book or it may be a new data set. Your data must contain two or more attributes per entry, one of which will be an appropriate key value. The remaining attributes will constitute the satellite data associated with the entry.