C++ Programming

1. Consider the following list:

5, 12, 25, 32, 38, 46, 58, 62, 85, 90, 97, 105, 110

Using the 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.

i. 32

ii. 20

iii. 105

iv. 60

2. 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

3. 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.

Give the resulting list after one call to the function partition.

What is the size of the list that the function partition partitioned?

What are the sizes of the two sublists created by the function partition?

4. Suppose that the list of keys is as given in Exercise 3. 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.

5. 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 rear- ranges the element of the array in ascending order.

Your function must not incorporate any sorting algorithms, that is, no item comparisons should take place.