Selection Sort(A[1,2..n]:array of integers) 1.for i=1 to n-1 2.for j=i+1 to n 3.if A[j]<A[i] 4 swap(A[i],A[j])
I am trying to prove the correctness of this algorithm,I read from my book and here is what is written:We must have 2 invariants for the inner and outer loop
The inner states:Every time we reach line 2,the current A[i] hold the value of a minimum element from A[i ,...,j-1]
The outer states : Everytime we are at line 1,the current subarray A[1,..,i-1] consists of i-1 in number smallest elements from the original array A'[1,....,n] in sorted order
Now to prove that it is really sorting we use the outer loop with the claim that the part from A[1,..,i-1] is sorted and from the inner loop invariant A[i] is the minimum from A[1,...n] and it is solved ,however what seems unclear to me is how we design the inner invariant ,why do we say A[i] is the minimum from A[i,..,j-1] I tried with some values and it always turns only 1 element and I guess in our final proof we say not A[i] is the minimum in A[i,...j-1] but A[i,..n].Shouldn't we say A[i] is the minimum in A[i,..,j-1] since we have proved that ?