Section 3.3 Analysis of Algorithms
215
a. Walk through algorithm BubbleSort to sort the list 5, 6, 3, 4, 8, 2.
b. Write a recurrence relation for the number of comparisons of list elements done by this algorithm to sort
an n-element list.
c. Solve this recurrence relation.
14. In algorithm BubbleSort, suppose we include exchanges of list elements as a work unit, in addition to
comparisons between list elements.
a. Describe the worst case and find the number of comparisons and exchanges done in this case.
b. Describe the best case and find the number of comparisons and exchanges done in this case.
c. Assume that on the average exchanges between elements must be done about half the time. Find the
number of comparisons and exchanges done in this case.
Exercises 15–18 refer to the recursive algorithm SelectionSort of Section 3.1.
15. In one part of algorithm SelectionSort, the index of the maximum item in a list must be found. This requires
comparisons between list elements. In an n-element (unsorted) list, how many such comparisons are needed
in the worst case to find the maximum element? How many such comparisons are needed in the average case?
16. Defining the basic operation as the comparison of list elements and ignoring the amount of work required
to exchange list elements, write a recurrence relation for the amount of work done by selection sort on an
n-element list. (Hint: Use the result from Exercise 15.)
17. Solve the recurrence relation of Exercise 16.
18. Assume that the exchange of L[i] and L[ j] takes place even if i = j. Write an expression for the total
number of comparisons and exchanges done to sort an n-element list.
Exercises 19–24 relate to a recursive sorting algorithm called MergeSort, which is described as follows: A oneelement list is already sorted; no further work is required. Otherwise, split the list in half, sort each half using
MergeSort (this is the recursive part), and then merge the two halves back into one sorted list.
19. The merge part of algorithm MergeSort requires comparing elements from each of two sorted lists to see
which goes next into the combined, sorted list. When one list runs out of elements, the remaining elements
from the other list can be added without further comparisons. Given the following pairs of lists, perform
a merge and count the number of comparisons to merge the two lists into one.
a. 6, 8, 9 and 1, 4, 5
b. 1, 5, 8 and 2, 3, 4
c. 0, 2, 3, 4, 7, 10 and 1, 8, 9
20. Under what circumstances will the maximum number of comparisons take place while merging two sorted
lists? If the lengths of the lists are r and s, what is the maximum number of comparisons?
21. Write a recurrence relation for the number of comparisons between list elements done by algorithm
MergeSort in the worst case. Assume that n = 2
m
.
22. Solve the recurrence relation of Exercise 21.
23. Use the results of Exercises 18 and 22 to compare the worst-case behavior of SelectionSort (counting
comparisons and exchanges) and MergeSort (counting comparisons) for n = 4, 8, 16, and 32 (use a
calculator or spreadsheet).
24. Use the results of Exercises 14 and 22 to compare the worst-case behavior of BubbleSort (counting
comparisons and exchanges) and MergeSort (counting comparisons) for n = 4, 8, 16, and 32 (use a
calculator or spreadsheet).
Exercises 25–34 relate to a recursive sorting algorithm called QuickSort, which is described as follows: A
one-element list is already sorted; no further work is required. Otherwise, take the first element in the list, call it the
215
a. Walk through algorithm BubbleSort to sort the list 5, 6, 3, 4, 8, 2.
b. Write a recurrence relation for the number of comparisons of list elements done by this algorithm to sort
an n-element list.
c. Solve this recurrence relation.
14. In algorithm BubbleSort, suppose we include exchanges of list elements as a work unit, in addition to
comparisons between list elements.
a. Describe the worst case and find the number of comparisons and exchanges done in this case.
b. Describe the best case and find the number of comparisons and exchanges done in this case.
c. Assume that on the average exchanges between elements must be done about half the time. Find the
number of comparisons and exchanges done in this case.
Exercises 15–18 refer to the recursive algorithm SelectionSort of Section 3.1.
15. In one part of algorithm SelectionSort, the index of the maximum item in a list must be found. This requires
comparisons between list elements. In an n-element (unsorted) list, how many such comparisons are needed
in the worst case to find the maximum element? How many such comparisons are needed in the average case?
16. Defining the basic operation as the comparison of list elements and ignoring the amount of work required
to exchange list elements, write a recurrence relation for the amount of work done by selection sort on an
n-element list. (Hint: Use the result from Exercise 15.)
17. Solve the recurrence relation of Exercise 16.
18. Assume that the exchange of L[i] and L[ j] takes place even if i = j. Write an expression for the total
number of comparisons and exchanges done to sort an n-element list.
Exercises 19–24 relate to a recursive sorting algorithm called MergeSort, which is described as follows: A oneelement list is already sorted; no further work is required. Otherwise, split the list in half, sort each half using
MergeSort (this is the recursive part), and then merge the two halves back into one sorted list.
19. The merge part of algorithm MergeSort requires comparing elements from each of two sorted lists to see
which goes next into the combined, sorted list. When one list runs out of elements, the remaining elements
from the other list can be added without further comparisons. Given the following pairs of lists, perform
a merge and count the number of comparisons to merge the two lists into one.
a. 6, 8, 9 and 1, 4, 5
b. 1, 5, 8 and 2, 3, 4
c. 0, 2, 3, 4, 7, 10 and 1, 8, 9
20. Under what circumstances will the maximum number of comparisons take place while merging two sorted
lists? If the lengths of the lists are r and s, what is the maximum number of comparisons?
21. Write a recurrence relation for the number of comparisons between list elements done by algorithm
MergeSort in the worst case. Assume that n = 2
m
.
22. Solve the recurrence relation of Exercise 21.
23. Use the results of Exercises 18 and 22 to compare the worst-case behavior of SelectionSort (counting
comparisons and exchanges) and MergeSort (counting comparisons) for n = 4, 8, 16, and 32 (use a
calculator or spreadsheet).
24. Use the results of Exercises 14 and 22 to compare the worst-case behavior of BubbleSort (counting
comparisons and exchanges) and MergeSort (counting comparisons) for n = 4, 8, 16, and 32 (use a
calculator or spreadsheet).
Exercises 25–34 relate to a recursive sorting algorithm called QuickSort, which is described as follows: A
one-element list is already sorted; no further work is required. Otherwise, take the first element in the list, call it the