void selectionSort$($int A$[],$ int N$)\{$

for $($int k $=0$ ; k $<$ N$-1$; k$++)\{$

$//$ lines $5--8$: find the smallest value in A$[$k$..$N$-1]$

$//$ mi will hold the index for the smallest value.

int mi $=$ k ;

for $($int j $=$ k$+1$ ; j $<$ N ; j$++)\{$

if $($A$[$j$]<=$ A$[$mi$])$ mi $=$ j ;

$\}$

$//$ move $($swap$)$ the smallest value to A$[$k$]$

int t $=$ A$[$k$]$ ;

A$[$k$]=$ A$[$mi$]$ ;

A$[$mi$]=$ t ;

$\}$

$\}$

$1.$ Trace the above function on the array $[14,12,15,13,11].$ For each iteration of

the outer for loop, you need to produce a record of the values in array A$,$ similar

to Figure$-2\mathrm{.}2$ in the textbook $($and slides.$)$

$2.$ Why does the inner$-$loop maintain the index of the minimum value $($in variable

mi$)$ rather than the minimum value itself?

$3.$ Is there a best$-$case or worst$-$case for this algorithm? Explain $($elaborate on$)$ your

answer?

$($pssst$,$ the answer is no there isn$$t$.)$

$4.$ Derive the formula that counts the number of steps it takes for this function to

sort a list of size N$.$

$5.$ So what$$s the order$-$of$-$growth of this algorithm?

$6.$ What would be a suitable loop$-$invariant for the outer loop?

$7.$ Prove the correctness of the loop$-$invariant by proving the initialization and

main$-$tenance steps. Assume that the inner loop $($lines $58)$ is correct and that at line

$9$ the value in A$[$mi$]$ is indeed the smallest value in A$[$k$..$N$-1]$

$8.$ Use the loop$-$invariant, and the termination condition of the outer loop to prove

the correctness of the Selection$-$Sort algorithm