Activity $4\mathrm{.}5\mathrm{.}2$: Selection Sort

Consider the following algorithm on an array of numbers x$1,$ x$2,$ x$3,...,$ xn$.$

The element in the first position is compared to the n $1$ remaining elements; whenever one is found that is less, the first element is swapped with it$.$ Then the element in the second position is compared with the remaining n $2$ elements. Whenever one is found that is less, the elements are swapped. This continues until the $($n$1)$st element; if it is out of order with the nth element, the elements are swapped. The algorithm pseudocode is shown below:

The selection sort algorithm

Step through this algorithm when applied to the array x$1=9,$ x$2=4,$ x$3=7,$ x$4=1.$ Record the values of the array every time they change.

In terms of n$,$ how many comparisons does this algorithm make on an array of length n$?$