$6.$ The following algorithm is supposed to sort an array of integers. Provide a proof that this algorithm is correct.

$//$ Sorts an array of integers.

Sort $($array A$)\{$

for i $=1$ to A$.$length

$\{$

minIndex $=$ i

for j $=$ i $+1$ to A$.$length

if A$[$j$]<$ A$[$minIndex$]$

minIndex $=$ j

Swap$($A$,$ i$,$ minIndex$)$

$\}$

$\}$

$//$ Swaps two elements of the array. You may assume this function is correct.

Swap $($A$,$ int x$,$ int y$)\{$

tmp $=$ A$[$x$]$

A$[$x$]=$ A$[$y$]$

A$[$y$]=$ tmp

$\}$