Let's say we want to find primes by certain algorithms (called primality tests)
A sound primality test will never say that a number is prime when it is composite (but it may fail to detect some primes as such; it may also sometimes fail to HALT)
A complete primality test will never say that a number is composite when it is prime (but it may fail to detect some composites, thus produceing "pseudo-primes" or it fails to HALT)
A paritally correct primality test may sometimes fail to give an result at all (i.e., fail to HALT). But if it returns a result it is correct: If it says prime, the input is prime, and if it says composite, the input is composite.
A (totally) correct primality test will always halt, and it will always return the correct answer.
The key here, quoting from the section Infinite descent in the wikipedia article on mathematical induction, is
$\quad$ ... there are no infinite decreasing sequences of natural numbers
Here we provide constructions/hints and leave the organization/exposition of the theory to the interested reader.
Recall that we have the first projection mapping $\pi_1$ on $\Bbb Z^{+} \times \Bbb Z^{+}$ defined by:
$\quad \forall \, (m,m) \in \Bbb Z^{+} \times \Bbb Z^{+} : \pi_1(m,n)=m$
Define $P = \{ (m,n) \in \Bbb Z^{+} \times \Bbb Z^{+} \mid m \ge n \} $. Recall that the set $P$ contains the diagonal set
$\quad \quad \quad \Delta_{\mathbb Z^{+}} = \{(d,d) \mid d \in \mathbb Z^{+}\}$.
We define the function $F: P \to P$ as follows
$$
F(m,n) = \left\{\begin{array}{lr}
(m,n) & \text{if } m = n\\
(m-n,n) & \text{if } m-n \ge n\\
(n,m-n) & \text{if } m-n \lt n\\
\end{array}\right\}
$$
If $(m,n) \in P$ we can apply the $\text{gcd}$ function. Note that for elements $(d,d)$ in the diagonal $\Delta_{\mathbb Z^{+}}$,
$\tag 1 \text{gcd}(d,d) = d$
Now it is well known that
$\tag 2 \text{gcd}(m,n) = \text{gcd}\big(F(m,n)\big)$
For fixed $(s,t)$ in the domain of $F$ we define a sequence
$\tag 3 a_k = \pi_1 \circ F^k(s,t)$
By using the absurdity of an infinite descent, the sequence $(a_k)$ eventually 'stops decreasing and remains constant. That happens precisely when the algorithm $F$ 'hits the diagonal.
So the algorithm $F$ 'gets us' to the diagonal in a finite number of steps, and from there we can just 'read off' greatest common divisor.
Example: Let $m = 28$ and $n = 10$ so that $(m,n)$ belongs to the domain of $F$.
$\quad F(28,10) = (18, 10)$
$\quad F(18,10) = (10, 8)$
$\quad F(10,8) = (8, 2)$
$\quad F(8,2) = (6, 2)$
$\quad F(6,2) = (4, 2)$
$\quad F(4,2) = (2, 2)$ STOP
Of course if you don't want to stop you can continue to apply $F$. But the points on the diagonal are exactly the fixed points of $F$, so you will quickly lose interest.
The point $(2,2) \in \Delta_{\mathbb Z^{+}}$ and so $\text{gcd}(28,10) = 2$.
Best Answer
Your algorithm has a typo. The inner loop should start $j := i + 1$ and go to $n$. Notice that after iteration $i$ of the outer loop, the largest $i$ elements are sorted correctly at the end of the list. Prove this fact, which I will call $(*)$.
We also have termination, by finiteness of both loops (and no modification of $i, j$ other than incrementation).
You can then use induction on $(*)$ to argue that if the largest elements are sorted correctly at indices $n-i, ..., n-1$, then the next iteration of the loop will correctly place the $n-1-i$ largest element at index $n - 1 - i$, preserving order.
Edit:
Claim: On the ith iteration of the outer loop, the largest $i$ elements will be sorted correctly (at the end of the array).
Proof: By induction on $n \in \mathbb{N}$. Consider the base case of $n = 1$. Let $x$ be the largest element in the array. By the algorithm, if $x$ is unique, $x$ is swapped on each iteration after being discovered initially. It is then placed at the end. If $x$ is not unique, then there exists a second copy of it and no swap will occur. However, the second copy will then be swapped. This process continues, so the last occurrence of $x$ will be moved to the end of the array. The theorem thus holds at $i = 1$.
I assume the theorem holds true up to an arbitrary integer $k$ such that $1 < k < n$ and prove true for the $k+1$ case. Let $y$ be the $k+1$ largest element in the array. We consider the reduced case of examining the first $n - k - 1$ elements. By the inductive hypothesis, $y$ will be correctly placed at the end of this sub-array. As $y$ is no bigger than the $k$th largest element, $y$ will not be moved further down into the array. The $k+1$ case thus holds.
And so the claim holds true by the principle of mathematical induction.