C Sorting and Searching 1 Mark the following statements as t

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

Solution

HI, I have answerd first 3 questions.

Please let me know in case of any issue.

Please post other questions in separate post.

1)

a. A sequential search of a list assumes that the list elements are sorted in ascending order.
   FALSE
b. A binary search of a list assumes that the list is sorted.
   TRUE

2)
Sequential Search: Since sequential search searches by comparing one by one element of list from first
                   to last. So if there are n elements in list, it takes max n comparisons.
   List: 63 45 32 98 46 57 28 100
   a. 90 : 8 comparisons
   b. 57 : 6 comparisons
   c. 63 : 1 comparisons
   d. 120 : 8 comparisons

3)
   List: 2 10 17 45 49 55 68 85 92 98 110

   a. 15
       first = 0
       last = 10
       mid = 5, first comparison with 55

       first = 0
       last = 4
       mid = 2, second comparison with 17

       first = 0;
       last = 1
       mid = 0. 3rd comparison with 2

       first = 1;
       last = 1;
       mid = 1, 4th comparison with 10

       END;

       Total comparison = 4

   List: 2 10 17 45 49 55 68 85 92 98 110
   b. 49
       first = 0
       last = 10
       mid = 5, first comparison with 55

       first = 0
       last = 4
       mid = 2, second comparison with 17

       first = 3;
       last = 4
       mid = 3. 3rd comparison with 45

       first = 4;
       last = 4;
       mid = 4, 4th comparison with 49

       END;

       Total comparison = 4

   c. 98
       List: 2 10 17 45 49 55 68 85 92 98 110

       first = 0
       last = 10
       mid = 5, first comparison with 55

       first = 6
       last = 10
       mid = 8, second comparison with 85

       first = 9;
       last = 10
       mid = 9. 3rd comparison with 98

       END;

       Total comparison = 3

   d. 99
       List: 2 10 17 45 49 55 68 85 92 98 110

       first = 0
       last = 10
       mid = 5, first comparison with 55

       first = 6
       last = 10
       mid = 8, second comparison with 85

       first = 9;
       last = 10
       mid = 9. 3rd comparison with 98

       first = 10;
       last = 10
       mid = 10. 4th comparison with 110

       END;

       Total comparison = 4