Exercises

Here are some exercises for you to try on your own. Solutions are available at http://pragprog.com/titles/gwpy3/practical-programming.

1. All three versions of linear search start at index 0. Rewrite all to search from the end of the list instead of from the beginning. Make sure you test them.

2. For the new versions of linear search: if there are duplicate values, which do they find?

3. Binary search is significantly faster than the built-in search but requires that the list is sorted. As you know, the running time for the best sorting algorithm is on the order of N log₂ N, where N is the length of the list. If we search a lot of times on the same list of data, it makes sense to sort it once before doing the searching. Roughly how many times do we need to search in order to make sorting and then searching faster than using the built-in search?

4. Given the unsorted list [6, 5, 4, 3, 7, 1, 2], show what the contents of the list would be after each iteration of the loop as it is sorted using the following:

   1. Selection sort
   2. Insertion sort

5. Another sorting algorithm is bubble sort. Bubble sort involves keeping a sorted section at the end of the list. The list is traversed, pairs of elements are compared, and larger elements are swapped into the higher position. This is repeated until all elements are sorted.

   1. Using the English description of bubble sort, write an outline of the bubble sort algorithm in English.

   2. Continue using top-down design until you have a Python algorithm.

   3. Turn it into a function called bubble_sort(L).

   4. Try it out on the test cases from selection_sort.

6. In the description of bubble sort in the previous exercise, the sorted section of the list was at the end of the list. In this exercise, bubble sort will maintain the sorted section at the beginning of the list. Make sure that you are still implementing bubble sort!

   1. Rewrite the English description of bubble sort from the previous exercise with the necessary changes so that the sorted elements are at the beginning of the list instead of at the end.

   2. Using your English description of bubble sort, write an outline of the bubble sort algorithm in English.

   3. Write function bubble_sort_2(L).

   4. Try it out on the test cases from selection_sort.

7. Modify the timing program to compare bubble sort with insertion and selection sort. Explain the results.

8. The analysis of bin_sort said, “Since N values have to be inserted, the overall running time is N log₂ N.” Point out a flaw in this reasoning, and explain whether it affects the overall conclusion.

9. There are at least two ways to come up with loop conditions. One of them is to answer the question, “When is the work done?” and then negate it. In function merge in ​Merging Two Sorted Lists​, the answer is, “When we run out of items in one of the two lists,” which is described by this expression: i1 == len(L1) or i2 == len(L2). Negating this leads to our condition i1 != len(L1) and i2 != len(L2).

   Another way to come up with a loop condition is to ask, “What are the valid values of the loop index?” In function merge, the answer to this is 0 <= i1 < len(L1) and 0 <= i2 < len(L2); since i1 and i2 start at zero, we can drop the comparisons with zero, giving us i1 < len(L1) and i2 < len(L2).

   Is there another way to do it? Have you tried both approaches? Which do you prefer?

10. In function mergesort in ​Merge Sort​, there are two calls to extend. They are there because when the preceding loop ends, one of the two lists still has items in it that haven’t been processed. Rewrite that loop so that these extend calls aren’t needed.