Wrap-Up

Answers to Self Review Exercises

20.1	a) 16, because an O(n2) algorithm takes 16 times as long to sort four times as much information. b) O(n log n).
20.2	Both of these algorithms incorporate "halving"somehow reducing something by half. The binary search eliminates from consideration one-half of the vector after each comparison. The merge sort splits the vector in half each time it is called.
20.3	The insertion sort is easier to understand and to implement than the merge sort. The merge sort is far more efficient (O(n log n)) than the insertion sort (O(n2)).
20.4	In a sense, it does not really sort these two subvectors. It simply keeps splitting the original vector in half until it provides a one-element subvector, which is, of course, sorted. It then builds up the original two subvectors by merging these one-element vectors to form larger subvectors, which are then merged, and so on.

Exercises

[Note: Most of the exercises shown here are duplicates of exercises from Chapters 78. We include the exercises again here as a convenience for readers studying searching and sorting in this chapter.]

20.5	(Bubble Sort) Implement bubble sortanother simple yet inefficient sorting technique. It is called bubble sort or sinking sort because smaller values gradually "bubble" their way to the top of the vector (i.e., toward the first element) like air bubbles rising in water, while the larger values sink to the bottom (end) of the vector. The technique uses nested loops to make several passes through the vector. Each pass compares successive pairs of elements. If a pair is in increasing order (or the values are equal), the bubble sort leaves the values as they are. If a pair is in decreasing order, the bubble sort swaps their values in the vector. The first pass compares the first two elements of the vector and swaps them if necessary. It then compares the second and third elements in the vector. The end of this pass compares the last two elements in the vector and swaps them if necessary. After one pass, the largest element will be in the last index. After two passes, the largest two elements will be in the last two indices. Explain why bubble sort is an O(n2) algorithm.
20.6	(Enhanced Bubble Sort) Make the following simple modifications to improve the performance of the bubble sort you developed in Exercise 20.5: After the first pass, the largest number is guaranteed to be in the highest-numbered element of the vector; after the second pass, the two highest numbers are "in place"; and so on. Instead of making nine comparisons (for a 10-element vector) on every pass, modify the bubble sort to make only the eight necessary comparisons on the second pass, seven on the third pass, and so on. The data in the vector may already be in the proper order or near-proper order, so why make nine passes (of a 10-element vector) if fewer will suffice? Modify the sort to check at the end of each pass whether any swaps have been made. If none have been made, the data must already be in the proper order, so the program should terminate. If swaps have been made, at least one more pass is needed.
20.7	(Bucket Sort) A bucket sort begins with a one-dimensional vector of positive integers to be sorted and a two-dimensional vector of integers with rows indexed from 0 to 9 and columns indexed from 0 to n 1, where n is the number of values to be sorted. Each row of the two-dimensional vector is referred to as a bucket. Write a class named BucketSort containing a function called sort that operates as follows: Place each value of the one-dimensional vector into a row of the bucket vector, based on the value's "ones" (rightmost) digit. For example, 97 is placed in row 7, 3 is placed in row 3 and 100 is placed in row 0. This procedure is called a distribution pass. Loop through the bucket vector row by row, and copy the values back to the original vector. This procedure is called a gathering pass. The new order of the preceding values in the one-dimensional vector is 100, 3 and 97. Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.). On the second (tens digit) pass, 100 is placed in row 0, 3 is placed in row 0 (because 3 has no tens digit) and 97 is placed in row 9. After the gathering pass, the order of the values in the one-dimensional vector is 100, 3 and 97. On the third (hundreds digit) pass, 100 is placed in row 1, 3 is placed in row 0 and 97 is placed in row 0 (after the 3). After this last gathering pass, the original vector is in sorted order. Note that the two-dimensional vector of buckets is 10 times the length of the integer vector being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memorythe bubble sort requires space for only one additional element of data. This comparison is an example of the spacetime trade-off: The bucket sort uses more memory than the bubble sort, but performs better. This version of the bucket sort requires copying all the data back to the original vector on each pass. Another possibility is to create a second two-dimensional bucket vector and repeatedly swap the data between the two bucket vectors.
20.8	(Recursive Linear Search) Modify Exercise 7.33 to use recursive function recursiveLinearSearch to perform a linear search of the vector. The function should receive the search key and starting index as arguments. If the search key is found, return its index in the vector; otherwise, return 1. Each call to the recursive function should check one index in the vector.
20.9	(Recursive Binary Search) Modify Fig. 20.3 to use recursive function recursiveBinarySearch to perform a binary search of the vector. The function should receive the search key, starting index and ending index as arguments. If the search key is found, return its index in the vector. If the search key is not found, return -1.
20.10	(Quicksort) The recursive sorting technique called quicksort uses the following basic algorithm for a one-dimensional vector of values: Partitioning Step : Take the first element of the unsorted vector and determine its final location in the sorted vector (i.e., all values to the left of the element in the vector are less than the element, and all values to the right of the element in the vector are greater than the elementwe show how to do this below). We now have one element in its proper location and two unsorted subvectors. Recursion Step : Perform Step 1 on each unsorted subvector. Each time Step 1 is performed on a subvector, another element is placed in its final location of the sorted vector, and two unsorted subvectors are created. When a subvector consists of one element, that element is in its final location (because a one-element vector is already sorted). The basic algorithm seems simple enough, but how do we determine the final position of the first element of each subvector? As an example, consider the following set of values (the element in bold is the partitioning elementit will be placed in its final location in the sorted vector): 37 2 6 4 89 8 10 12 68 45 Starting from the rightmost element of the vector, compare each element with 37 until an element less than 37 is found; then swap 37 and that element. The first element less than 37 is 12, so 37 and 12 are swapped. The new vector is      12  2  6  4  89  8  10  37  68  45 Element 12 is in italics to indicate that it was just swapped with 37. Starting from the left of the vector, but beginning with the element after 12, compare each element with 37 until an element greater than 37 is foundthen swap 37 and that element. The first element greater than 37 is 89, so 37 and 89 are swapped. The new vector is      12  2  6  4  37  8  10  89  68  45 Starting from the right, but beginning with the element before 89, compare each element with 37 until an element less than 37 is foundthen swap 37 and that element. The first element less than 37 is 10, so 37 and 10 are swapped. The new vector is      12  2  6  4  10  8  37  89  68  45 Starting from the left, but beginning with the element after 10, compare each element with 37 until an element greater than 37 is foundthen swap 37 and that element. There are no more elements greater than 37, so when we compare 37 with itself, we know that 37 has been placed in its final location of the sorted vector. Every value to the left of 37 is smaller than it, and every value to the right of 37 is larger than it. Once the partition has been applied on the previous vector, there are two unsorted subvectors. The subvector with values less than 37 contains 12, 2, 6, 4, 10 and 8. The subvector with values greater than 37 contains 89, 68 and 45. The sort continues recursively, with both subvectors being partitioned in the same manner as the original vector. Based on the preceding discussion, write recursive function quickSortHelper to sort a one-dimensional integer vector. The function should receive as arguments a starting index and an ending index on the original vector being sorted.