Verified Test Bank - Faster Sorting Methods Chapter 16 5e

Chapter 16 - Faster Sorting Methods

True/False (12)

1. Divide and conquer algorithms typically use two or more recursive calls.
2. Divide and conquer algorithms can only be written recursively.
3. Merging two arrays requires an additional array.
4. A disadvantage of merge sort is the need for a temporary array during the merge step.
5. You cannot use a recurrence relation to estimate the time efficiency of the recursive merge sort algorithm because there are two recursive calls in the method.
6. The iterative merge sort algorithm is much simpler than the recursive algorithm
7. The merge sorts in the Java Class Library are stable.
8. The quick sort algorithm always divides an array in half.
9. In quick sort, the partition places the pivot in the position that it will occupy in the final sorted array.
10. In quick sort, the choice of pivots affects its behavior.
11. The radix sort restricts the data that it sorts on.
12. Radix sort is a general-purpose sorting algorithm.

Short Answer (6)

1. Given the following array of 8 elements, trace the merge sort algorithm. Assume the array is to be sorted in ascending order.
   
   81 16 4 6 34 11 23 67

81 16 4 6 34 11 23 67
81 16 4 6 34 11 23 67
81 16 4 6 34 11 23 67
16 81 4 6 11 34 23 67
4 6 16 81 11 23 34 67
4 6 11 16 23 34 67 81

1. Given the following array of 9 elements, trace one iteration of the quick sort algorithm. Use the middle value in the array as the pivot. Assume the array is to be sorted in ascending order.
   
   81 16 4 6 34 11 23 67 52

81 16 4 6 34 11 23 67 52
swap the pivot with the last value in the array
81 16 4 6 52 11 23 67 34
swap 81 and 23
23 16 4 6 52 11 81 67 34
swap 52 and 11
23 16 4 6 11 52 81 67 34
swap pivot with the element at the index from the left (element is 52)
23 16 4 6 11 34 81 67 52
end of first iteration

1. In quick sort which element would be selected to be the pivot of the following array if the pivot strategy is to use the median of three elements, the first, middle and last.

81 16 4 6 34 11 23 67 52

1. Given the following array of 9 elements, trace one iteration of the quick sort algorithm. Use the pivot strategy by selecting the median of three elements, the first, middle and last. Assume the array is to be sorted in ascending order.
   
   81 16 4 6 34 11 23 67 52

81 16 4 6 34 11 23 67 52
swap the pivot with the last value in the array (already there)
81 16 4 6 34 11 23 67 52
swap 81 and 23
23 16 4 6 34 11 81 67 52
done swapping, as indexFromLeft (element is 81) passes indexFromRight(element is 11)
swap pivot with the element at the indexFromLeft (element is 81)
23 16 4 6 34 11 52 67 81
end of first iteration

1. Why don’t we select the median element of all the n-entries in the array to be our pivot point?
2. Given the following array of 8 elements, show the steps to sort the elements in ascending order using radix sort.
   81 546 677 9 97 12 53 22

081 546 677 009 097 012 053 022
buckets for ones digit
081 012 022 053 546 677 097 009
buckets for tens digit
009 012 022 546 053 677 081 097
buckets for hundreds digit
009 012 022 053 081 097 546 677

Multiple Choice (32) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. Which sorting method divides an array into halves, sorts them and merges them back into one sorted array?
   1. merge sort
   2. quick sort
   3. radix sort
   4. insertion sort
2. Dividing a problem into two or more smaller, distinct problems, then solving them and combining them into a final solution is called
   1. divide and conquer
   2. divide and combine
   3. recursion
   4. sorting
3. The most programming intensive part of merge sort is
   1. the merge step
   2. the division step
   3. the comparison of items
   4. none of the above
4. After merging two arrays is complete, you need to
   1. copy the merged array back to the original array
   2. copy the original array to the temporary array
   3. copy the rest of the first array elements to the temporary array
   4. copy the rest of the second array elements to the temporary array
5. In merge sort, allocating and initializing an array many times during the recursive calls to merge
   1. is a waste of time and space
   2. is the only way to ensure the algorithm will work correctly
   3. is the only way the merge process will work
   4. all of the above
6. In merge sort, the merge step takes at most ______ comparisons for n items.
   1. n – 1
   2. n
   3. 2n
   4. n2
7. The performance of the merge operation for n items in merge sort is
   1. O(n)
   2. O(n²)
   3. O(n log n)
   4. O(log n)
8. The performance of merge sort for n items is
   1. O(n log n)
   2. O(log n)
   3. O(n)
   4. O(n2)
9. In merge sort, the merge steps are O(n)
   1. regardless of the initial order of the array
   2. when the data is initially close to being sorted
   3. when the data is initially close to being reverse sorted
   4. none of the above
10. The class Arrays in the package java.util has several static methods to sort arrays of Objects into ascending order. Which sort is used?
    1. merge sort
    2. quick sort
    3. shell sort
    4. insertion sort
11. A sorting algorithm that does not change the relative order of objects that are equal is called
    1. stable
    2. relative
    3. ordered
    4. all of the above
12. The quick sort algorithm uses a ________ to divide the array into two pieces.
    1. pivot
    2. mid-point
    3. divider
    4. none of the above
13. Which sorting algorithm divides the array into two pieces based on the selection of a pivot element?
    1. quick sort
    2. merge sort
    3. radix sort
    4. selection sort
14. Which statements are true about the pivot element in quick sort?
    1. Entries in positions before the pivot are less than or equal to the pivot.
    2. Entries in positions after the pivot are greater than or equal to the pivot.
    3. The pivot is in the position that it will occupy in the final sorted array.
    4. All of the above.
15. In quick sort, dividing the array portions before and after the pivot are called
    1. partitions
    2. sections
    3. halves
    4. recursive arrays
16. In quick sort, the partition step takes at most ______ comparisons for n items.
    1. n
    2. 1
    3. 2n
    4. n2
17. The ideal situation in quick sort is when the pivot moves
    1. to the center of the array
    2. to the beginning of the array
    3. to the end of the array
    4. to a random place in the array
18. In quick sort, having every partition form sub arrays of roughly the same size
    1. is optimal
    2. creates more work because of repeated comparisons
    3. slows the processing down
    4. all of the above
19. The best-case performance of quick sort for n items is
    1. O(n log n)
    2. O(log n)
    3. O(n)
    4. O(n2)
20. The average-case performance of quick sort for n items is
    1. O(n log n)
    2. O(log n)
    3. O(n)
    4. O(n2)
21. The worst-case performance of quick sort for n items is
    1. O(n²)
    2. O(n log n)
    3. O(n)
    4. O(log n)
22. Which of the following statements are true about quick sort?
    1. In practice, it can be faster than merge sort.
    2. It does not require additional memory that merge sort does.
    3. It can degrade into an O(n²) sort if the pivot-selection scheme is bad.
    4. All of the above.
23. The worst case situation for quick sort is when
    1. each partition has one empty subarray
    2. each partition is of equal size
    3. the pivot element cannot be determined
    4. the array elements are initially completely random
24. In quick sort, the majority of the work occurs
    1. before the recursive calls
    2. in creating the partition
    3. both a & b
    4. none of the above
25. In the quick sort algorithm, using the median-of-three pivot selection scheme
    1. avoids worst-case performance for arrays that are already sorted
    2. avoids worst-case performance for arrays that are nearly sorted
    3. does not avoid worst-case for randomly distributed arrays
    4. all of the above
26. When quick sort partitions arrays as small as 10 entries, the best strategy is to
    1. use insertion sort on the small array
    2. use merge sort on the small array
    3. use shell sort on the small array
    4. use quick sort down to arrays as small as two entries
27. Which sort does not use comparisons?
    1. radix sort
    2. quick sort
    3. merge sort
    4. shell sort
28. The radix sort
    1. restricts the data that it sorts on
    2. is not suitable as a general-purpose sorting algorithm
    3. treats array entries as if they were strings that have the same length
    4. all of the above
29. Radix sort
    1. distributes digits into buckets
    2. partitions the array
    3. merges the array back into place
    4. all of the above
30. The best-case performance of radix sort on restricted data is
    1. O(n)
    2. O(log n)
    3. O(n log n)
    4. O(n2)
31. The worst-case performance of radix sort on restricted data is
    1. O(n)
    2. O(log n)
    3. O(n log n)
    4. O(n2)
32. The average-case performance of radix sort on restricted data is
    1. O(n)
    2. O(log n)
    3. O(n log n)
    4. O(n2)