Chapter 10

a. It was remarked in this chapter that 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

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 \(\mathbf{L}\) ?

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 or elements in the array. The function rearranges the element of the array in ascending order. Your function must not incorporate any sorting algorithms, that is, no item comparisons should take place.

To use a vector object in a program, which header file must be included in the program?

What do the following statements do? a. vector list(50); b. vector nameList;

What is the output of the following C++ code? vector intList(5); int i; for (i = 0; i < 5; i++) intList[i] = 2 * i + 1; for (i = 0; i < 5; i++) cout << intList.at(i) << " "; cout << endl;

What is the output of the following C++ code? vector classList; classList.push_back("Nisha"); classList.push_back("Tony"); classList.push_back("Bobby"); classList.push_back("Peter"); for (unsigned int i = 0; i < classList.size(); i++) cout << classList[i] << " "; cout << endl;

a. Write a C++ statement that declares secretList to be a vector object to store integers. (Do not specify the size of secretList.) b. Write C++ statements to store the following values, in the order given, into secretList: 56, 28, 32, 96, 75 c. Write a for loop that outputs the contents of secretList. (Use the expression secretList.size() to determine the size of secretList.)

. What is the output of the following C++ code? vector intList(10); for (int i = 0; i < 10; i++) intList[i] = 2 * i + 5; cout << intList.front() << " " << intList.back() << endl;

1\. Suppose that you have the following C++ code: vector myList(5); unsigned int length; myList[0] = 3; for (int i = 1; i < 4; i++) myList[i] = 2 * myList[i - 1] - 5; myList.push_back(46); myList.push_back(57); myList.push_back(35); a. Write a C++ statement that outputs the first and the last elements of myList. (Do not use the array subscripting operator or the index of the elements.) b. Write a C++ statement that stores the size of myList into length. c. Write a for loop that outputs the elements of myList.