2. (Adapted from Exercise 2.2-2 in the textbook) Below is pseudocode for selection sort, which works by finding the minimum element of A, and storing it in A[1], then finding the second smallest element of A, and storing it in A[2], and so on. SELECTION-SORT (A) 1 fori-1 to A.length-1 for j = i+1 to A. length 4 exchange A[i] with Aj] State precisely a loop invariant for the inner for loop in lines 2-4, and prove that this loop invariant holds. Your proof should resemble the structure of the loop invariant proofs in Sections 2.1 and 2.3 of the textbook, including arguments for Initialization, Maintenance, and Termination. a. b. Using your answer from part a, state precisely a loop invariant for the outer for loop in lines 1-4, and prove that this loop invariant holds. c. To prove that Selection-Sort is correct, we must prove that the fial ii a permutation (reordering) of the original list A such that A[1] S A121 s... S A'In]. Your answer from part b should prove that A[1] s AT2] S S A'[n], so explain why we know that the final list A' is a permutation (reordering) of the original list A. Give a best-case and worst-case running time for selection sort using O-notation and argue informally that your answer is correct. d