Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A and exchange it with A[2]. Continue in this manner for the first n-1 elements of A. a) This algorithm is known as the selection sort. Write the pseudo code for this algorithm.
b) What loop invariant does this algorithm maintain? Note: You do not have to discuss the three individual properties. You need to only provide the loop invariant.
c) Why does it need to run for only the first n-1 elements, rather than for
all n elements?
d) Give the best-case and worst-case running times of selection sort in O-notation. Explain your answers. (You will receive no credit for this question without the explanations for your answers.)