nother 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 using loop invariants $($i$.$e$.$ that it actually sorts the input

array$)$ and give an asymptotically tight bound on the algorithms runtime

$($using big$-\backslash$Theta notation$)$