Problem 11
Assume the following list of keys: 25,32,20,15,45,4,18,91,62,88,66 This list is to be sorted using the insertion sort algorithm as described in this chapter for array-based lists. Show the resulting list after seven passes of the sorting phase - that is, after seven iterations of the for loop.
Problem 12
Recall the insertion sort algorithm (contiguous version) as discussed in this chapter. Assume the following list of keys: 30,20,35,27,96,82,56,60,48,75,5,80 Exactly how many key comparisons are executed to sort this list using the insertion sort algorithm?
Problem 13
Both the merge sort and quick sort algorithms sort a list by partitioning it. Explain how the merge sort algorithm differs from the quick sort algorithm in partitioning the list.
Problem 14
Assume the following list of keys: 36,55,89,95,65,75,13,62,86,9,23,74,2,100,98 This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the middle element of the list. a. Give the resulting list after one call to the function partition. b. What is the size of the list that the function partition partitioned? c. What are the sizes of the two sublists created by the function partition?
Problem 17
Assume the following list of keys: 48,30,66,50,9,95,80,15,25,18,94,55,3,22,62 This list is to be sorted using the quick sort algorithm as discussed in this chapter. Use pivot as the median of the first, last, and middle elements of the list. a. What is the pivot? b. Give the resulting list after one call to the function partition. c. What is the size of the list that the function partition partitioned? d. What are the sizes of the two sublists created by the function partition?
Problem 20
Suppose that \(L\) is a list of 10,000 elements. Find the average number of comparisons made by bubble sort, selection sort, and insertion sort to sort \(L\)
Problem 21
Suppose that \(L\) is a list of 10,000 elements. Find the average number of comparisons made by quick sort and merge sort to sort \(L\)
