(Q11) [25 pts.] Solve problem 4.2 (a) and (b), pages 206-208: The Bubble Sort method sorts by making several passes through the array, comparing pairs of keys in adjacent locations, and interchanging their elements if they are out of order. That is, the first and second keys are compared and interchanged if the first is larger than the second; then the (new) second and the third keys are compared and interchanged if necessary, and so on. It is easy to see that the largest key will bubble up to the end of the array; on subsequent passes it will be ignored. If on any pass no entries are interchanged, the array is completely sorted and the algorithm can halt. The following Algorithm 4.14 (page 206) makes this informal description of the method precise. Algorithm 4.14 Bubble Sort Input: E, an array of elements, and a 20. the number of elements. Output: E with elements in nondecreasing order of their keys. void bubbleSort(Element() E, int n) int numPairs: // the number of pairs to be compared boolean didSwitch; // true if an interchange is done intji numpairs = n - 1: didSwitch - true; while (didSwitch) didSwitch - false; for(j = 0; j El + 1] Interchange Eli) and ELi + 1). didSwitch - true; // Continue for loop. numpairs -- return The example in Figure 4,29 illustrates how Bubble Sort works Input 8 3 4 9 7 7 didSwitche 3 4 81 7 9 didSwitch tre 3 4 7 9 didSwitch=false Figure 4.29 Bubble Sort