Problem 1
Fill in the blanks in each of the following statements: a. A selection sort application would take approximately ________ times as long to run on a 128-element vector as on a 32-element vector. b. The efficiency of merge sort is ________.
Problem 2
What key aspect of both the binary search and the merge sort accounts for the logarithmic portion of their respective Big Os?
Problem 4
In the text, we say that after the merge sort splits the vector into two subvectors, it then sorts these two subvectors and merges them. Why might someone be puzzled by our statement that "it then sorts these two subvectors"?
Problem 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\left(n^{2}\right)\) algorithm.
Problem 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: a. 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. b. 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 c. 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.
Problem 10
(Quicksort) The recursive sorting technique called quicksort uses the following basic algorithm for a one-dimensional vector of values: a. 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. b. 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): $$\begin{array}{llllllllll} 37 & 2 & 6 & 4 & 89 & 8 & 10 & 12 & 68 & 45 \end{array}$$
