Page 1297 - exercise #4 Consider the following list: 5, 12, 25, 32, 38, 46, 58,
ID: 3554344 • Letter: P
Question
Page 1297 - exercise #4
Consider the following list:
5, 12, 25, 32, 38, 46, 58, 62, 85, 90, 97, 105, 110
Using binary search as described in this chapter, how many comparisons are required to find whether the following items are in the list? Show the values of first, last, and middle and the number of comparisons after each iteration of the loop.
a. 32 b. 20 c. 105 d. 60
Page 1298 - exercise #8
Sort the following list using the bubble sort algorithm as discussed in this chapter. Show the list after each iteration of the outer for loop.
46, 58, 16, 25, 83, 98, 8, 70, 5, 62
Page 1299 - exercise #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 functions 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 partitioned?
Page 1299 - exercise #16
Suppose that the list of keys is as given in Exercise 14. Use the quick sort algorithm, as discussed in this chapter, to determine the number of times the function partition is called to completely sort the list.
Page 1300 - exercise #22
Suppose that the elements of a list are in descending order and they need to be put in ascending order. Write a C++ function that takes as input an array of items in descending order and the number of elements in the array. The function rearranges the elements of the array in ascending order. Your function must not incorporate any sorting algorithms, that is, no item comparisons should take place.
Explanation / Answer
Page 1298 - exercise #8:
In bubble sort algorithm, after each of the iteration the largest element present in the list occupies the last position of the list, the smallest elements are moved to their preceding positions.
Here, the list of integers is 46, 58,16,25,83,98,8,70,5 and 62.
The following output describes the items stored in the list before sorting, after each of the iteration of outer for loop, and after sorting.
The list before sorting: 46, 58, 16,25,83,98,8,70,5,62
The resulting list after iteration 1 of the outer for loop: 46, 58, 16,25,83,8,70,5,62, 98
The resulting list after iteration 2 of the outer for loop: 46, 58, 16,25,8,70,5,62,83,98
The resulting list after iteration 3 of the outer for loop: 46, 58, 16,25,8,5,62,70,83,98
The resulting list after iteration 4 of the outer for loop: 46, 16, 25,8,5,58,62,70,83,98
The resulting list after iteration 5 of the outer for loop: 16, 25, 8,5, 46,58,62,70,83,98
The resulting list after iteration 6 of the outer for loop: 16, 8, 5, 25, 46, 58, 62,70,83,98
The resulting list after iteration 7 of the outer for loop: 8, 5, 16, 25, 46, 58, 62,70,83,98
The resulting list after iteration 8 of the outer for loop: 5, 8, 16, 25, 46, 58, 62,70,83,98
The list after sorting: 5, 8, 16, 25, 46, 58, 62,70,83,98
Hence, the items in the list after sorting are:
5, 8, 16, 25, 46, 58, 62,70,83,98
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.