Question

C++ Sorting and Searching

1. Mark the following statements as true or false.

a. A sequential search of a list assumes that the list elements are sorted in ascending

order.

b. A binary search of a list assumes that the list is sorted.

2. Consider the following list:
63 45 32 98 46 57 28 100
Using a sequential search, how many comparisons are required to determine whether the following items are in the list or not? (Recall that comparisons mean item comparisons, not index comparisons.)
a. 90 b. 57 c. 63 d. 120

3. Consider the following list: 2 10 17 45 49 55 68 85 92 98 110
Using the binary search, how many comparisons are required to determine whether the following items are in the list or not? Show the values of first, last, and middle and the number of comparisons after each iteration of the loop.

a. 15 b. 49 c. 98 d. 99

4. Sort the following list using the bubble sort algorithm. Show the list after each iteration of the outer for loop.
26, 45, 17, 65, 33, 55, 12, 18

5. Sort the following list using the selection sort algorithm. Show the list after each iteration of the outer for loop.
36, 55, 17, 35, 63, 85, 12, 48, 3, 66

6. Consider the following list: 5, 18, 21, 10, 55, 20
The first three keys are in order. To move 10 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?

7. Consider the following list: 7, 28, 31, 40, 5, 20
The first four keys are in order. To move 5 to its proper position using the insertion sort as described in this chapter, exactly how many key comparisons are executed?

8. Consider the following list: 28, 18, 21, 10, 25, 30, 12, 71, 32, 58, 15
This list is to be sorted using the insertion sort algorithm. Show the resulting list after six

passes of the sorting phase – that is, after six iterations of the for loop.

9. Perform the insertion sort algorithm using the following list of keys: 18, 8, 11, 9, 15, 20, 32, 61, 22, 48, 75, 83, 35, 3
Show the list after each iteration. Exactly how many key comparisons are executed to sort this list using insertion sort?

10. a. The performance of bubble sort can be improved if we stop the sorting process as soon as we find that in an iteration, no swapping of elements takes place. Write a function that implements bubble sort algorithm using this fact.
b. Using the algorithm that you designed in part (a), find the number of iterations that are needed to sort the list: 65, 14, 52, 43, 75, 25, 80, 90, 95.

11. Suppose that L is a sorted list of 4096 elements. What is the maximum number of comparisons made by binary search to determine whether an item is in L?

12. 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 must not incorporate any sorting algorithms, that is, no item comparisons should take place.

Answer 1

A sequential search of a list assumes that the list elements are sorted in ascending
1. a) false
Sequential search means checking element by element only and not necessarily sorted array

b. A binary search of a list assumes that the list is sorted.
1. b) true
Concept of binary search is that it has sorted elemets and finding the element takes lesser time than that of linear search.

63 45 32 98 46 57 28 100

2. a) 90
8 comparisions
Since 90 is not there in given list, it will check all the items. So, 8.

2. b) 57
6 comparisions
57 can be found at 6th comparsion and there it will stop. So, 6