The bubble sort in the previous exercise always makes n passes. However, it is possible for the array to become sorted before all n passes are complete. For example, a bubble sort of the array...

The bubble sort in the previous exercise always makes n passes. However, it is possible for the array to become sorted before all n passes are complete. For example, a bubble sort of the array 9216478 is sorted after only two passes:

2 1 6 4 7 8 9 (end of pass 1)

1 2 4 6 7 8 9 (end of pass 2)

But since a swap occurred during the second pass, the sort needs to make one more pass to check that the array is in order. Additional passes, such as the ones that the algorithm in the previous exercise would make, are unnecessary.  You can skip these unnecessary passes and even do less work by remembering where the last swap occurred. During the first pass, the last swap is of the 9 and the 8. The second pass checks up to the 8. But during the second pass, the last swap is of the 6 and the 4. You now know that 6, 7, 8, and 9 are sorted. The third pass needs only to check up to the 4, instead of to the 7 as an ordinary bubble sort would do. No swaps occur during the third pass, so the index of the last swap during this pass is taken as zero, indicating that no further passes are necessary. Implement this revised bubble sort.