Wrap-Up

Answers to Self Review Exercises

24.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).
24.2	Both of these algorithms incorporate "halving"somehow reducing something by half. The binary search eliminates from consideration one half of the array after each comparison. The merge sort splits the array in half each time it is called.
24.3	The insertion sort is easier to understand and to program than the merge sort. The merge sort is far more efficient (O(n log n)) than the insertion sort (O(n2)).
24.4	In a sense, it does not really sort these two subarrays. It simply keeps splitting the original array in half until it provides a one-element subarray, which is, of course, sorted. It then builds up the original two subarrays by merging these one-element arrays to form larger subarrays, which are then merged until the whole array has been sorted.

Exercises

24.5	(Bubble Sort) Implement the 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 array (i.e., toward the first element) like air bubbles rising in water, while the larger values sink to the bottom (end) of the array. The technique uses nested loops to make several passes through the array. 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 array. The first pass compares the first two elements of the array and swaps them if necessary. It then compares the second and third elements in the array. The end of this pass compares the last two elements in the array 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.
24.6	(Enhanced Bubble Sort) Make the following simple modifications to improve the performance of the bubble sort you developed in Exercise 24.5: After the first pass, the largest number is guaranteed to be in the highest-numbered element of the array; after the second pass, the two highest numbers are "in place"; and so on. Instead of making nine comparisons on every pass, modify the bubble sort to make eight comparisons on the second pass, seven on the third pass and so on. The data in the array may already be in the proper order or near-proper order, so why make nine passes 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 application should terminate. If swaps have been made, at least one more pass is needed.
24.7	(Bucket Sort) A bucket sort begins with a one-dimensional array of positive integers to be sorted and a two-dimensional array 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 array is referred to as a bucket. Write a class named BucketSort containing a method called Sort that operates as follows: Place each value of the one-dimensional array into a row of the bucket array, based on the value's "ones" (right-most) 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 array row by row, and copy the values back to the original array. This procedure is called a gathering pass. The new order of the preceding values in the one-dimensional array 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 array 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 array is in sorted order. Note that the two-dimensional array of buckets is 10 times the length of the integer array 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 array on each pass. Another possibility is to create a second two-dimensional bucket array and repeatedly swap the data between the two bucket arrays.
24.8	(Recursive Linear Search) Modify Fig. 24.2 to use recursive method RecursiveLinearSearch to perform a linear search of the array. The method should receive the search key and starting index as arguments. If the search key is found, return its index in the array; otherwise, return 1. Each call to the recursive method should check one index in the array.
24.9	(Recursive Binary Search) Modify Fig. 24.4 to use recursive method RecursiveBinarySearch to perform a binary search of the array. The method should receive the search key, starting index and ending index as arguments. If the search key is found, return its index in the array. If the search key is not found, return 1.
24.10	(Quicksort) The recursive sorting technique called quicksort uses the following basic algorithm for a one-dimensional array of values: Partitioning Step: Take the first element of the unsorted array and determine its final location in the sorted array (i.e., all values to the left of the element in the array are less than the element, and all values to the right of the element in the array are greater than the elementwe show how to do this below). We now have one element in its proper location and two unsorted subarrays. Recursive Step: Perform Step 1 on each unsorted subarray. Each time Step 1 is performed on a subarray, another element is placed in its final location in the sorted array, and two unsorted subarrays are created. When a subarray consists of one element, that element is in its final location (because a one-element array is already sorted). The basic algorithm seems simple enough, but how do we determine the final position of the first element of each subarray? 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 array): 37 2 6 4 89 8 10 12 68 45   Starting from the right-most element of the array, 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 array 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 array, 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 array 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 array 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 array. 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 array, there are two unsorted subarrays. The subarray with values less than 37 contains 12, 2, 6, 4, 10 and 8. The subarray with values greater than 37 contains 89, 68 and 45. The sort continues recursively with both subarrays being partitioned in the same manner as the original array. Based on the preceding discussion, write recursive method QuickSortHelper to sort a onedimensional integer array. The method should receive as arguments a starting index and an ending index in the original array being sorted.

Data Structures