exercise 2.2-2 in introduction to algorithms

writing these is mainly to improve my writing, not mere to finish exercise for these are trivial and solved.
pseudocode(selection sort):
input:array A[n];
output:array A'[n] with all elements sorted;
procedure:
n = length(A);
for ( i = 0; i < n-1; i++ ) { //indices start with zero.
__max = i;
__for ( j = i+1; j < n; j++ ) {
____if ( A[j] > A[max] ) max = j;
__}
__if ( max != i ) { //replacing the ith greatest element in correct position.
____tmp = A[i];
____A[i] = A[max];
____A[max] = tmp;
__}
}
procedure end;
pseudocode end;

in this algorithm, the loop invariant is A[0..i];
in each iteration, the subset A[0..i] is always sorted;
here is the mathematical induction:
basis:it's sorted prior to all iterations for there is only one element in this subset.
maintenance:assume at current iteration step, the value of i is k, due to the mathematical induction, we have, the subset A[0..k] is in sorted and for each position of m denote the mth greatest element.after current iteration, we will get the (k+1)th greatest element and replace it at the position of k+1.to the next iteratin, subset of A[0..(k+1)] is in sorted(this is trivial).
termination:after procedure, A[0..(n-2)] contains the previous n-1 greatest elements, so, the last one must be the least one.it's explicit that we get a sorted array at last.

the best-case: we need to do nothing for it's sorted.O(c),c constant.
the worst-case: it may be O(n^2).

that's all of the solution.