In this part you will explore the number of comparisons needed for exchange sort from a theoretical perspective.

Let n be the number of items to sort and consider the case n $=10.$

The $1$st item will be compared with the $2$nd$,3$rd$,4$th etc. item, and so on up to the $10$th item, a total of $9$ comparisons.

The $2$nd item will be compared with the $3$rd$,4$th$,5$th etc. item, and so on up to the $10$th item, a total of $8$ comparisons.

The $3$rd item will be compared with the $4$th$,5$th$,6$th etc. item, and so on up to the $10$th item, a total of $7$ comparisons.

The sort continues in this way until the $9$th item is reached. This is compared with the $10$th item, taking just $1$ comparison, and the algorithm will now finish.

This requires a total of $9+8+7+6+5+4+3+2+1$ comparisons. We could just add these $9$ numbers together but there is a neater way. You can probably see that their average is $10/2=5$ and as there are $9$ of them the total must be $9\backslash$times $5=45,$ just as we found in part $($d$)($i$).$

In the general case with n items the average will be n $/2$ and there will be n $1$ numbers, giving a total of $($n $1)\backslash$times n $/2$ comparisons.

i$.$How does the number of comparisons needed by exchange sort compare with that required by bubble sort $1?$

ii$.$Section $6\mathrm{.}4\mathrm{.}3$ discusses an improved form of bubble sort, which it calls bubble sort $3.$ Although in the worst case bubble sort $3$ can require $($n $1)\backslash$times n $/2$ comparisons, the same as exchange sort, bubble sort $3$ has a particular feature that means it will generally take fewer comparisons. Explain what this feature is and describe what kind of data it makes bubble sort $3$ useful for sorting.