$2\mathrm{.}2-2$

Consider sorting n numbers stored in array AOE$1$ W nc by $$rst $$nding the smallest

element of AOE$1$ W nc and exchanging it with the element in AOE$1$c$.$ Then $$nd the

smallest element of AOE$2$ W nc$,$ and exchange it with AOE$2$c$.$ Then $$nd the smallest

element of AOE$3$ W nc$,$ and exchange it with AOE$3$c$.$ Continue in this manner for the

$$rst n $1$ elements of A$.$ Write pseudocode for this algorithm, which is known

as selection sort. What loop invariant does this algorithm maintain? Why does it

need to run for only the $$rst n $1$ elements, rather than for all n elements? Give the

worst$-$case running time of selection sort in $-$notation. Is the best$-$case running

time any better?