Another Sorting Algorithm Below we present another algorithm for

sorting an array of integers:

ExchangeSort$($A$[1,...,$ n$])$

Repeat forever:

i $1$

For j from $1$ to n $1$:

If A$[$j$]>$ A$[$j $+1]$:

i $$ j

If i $=1$:

$//$A is now sorted

Return

Swap A$[$i$]$ with A$[$i $+1]$

Prove that this algorithm is correct $($i$.$e$.$ that it actually sorts the input

array$)$ and give an asymptotically t