Solve problem $4\mathrm{.}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\mathrm{.}14($page $206)$ makes this informal description of the method precise.