> [!NOTE] Assumption > WLOG suppose the elements of the array are distinct. > [!Proposition] Proposition 1 > After one pass through the array, the largest entry will be at the end. > This gives that at the end of $t$ iterations of the outer for-loop, the $n-t$ highest elements of the array are in the sorted order and they occupy the indexes from $n-t+1$ to $n$. >*Proof* >1. After 1st comparison, $X=\max\{A[1],A[2]\}$ & $A[2] \gets X$. >2. Assume $A[k]$ is the largest among $(A[i])_{i=1}^{k}$, then in the next comparison between $A[k]$ and $A[k+1]$, $A[k+1]$ is the largest among $(A[i])_{i=1}^{k+1}$. > [!Proposition] Proposition 2 > If there is no pair of consecutive entries out of order, then the entire array is sorted. > *Proof* > 1. After the $i$th iteration, we know that $(A[i])_{i=n-i+1}^{n}$ are sorted. > 2. According to the condition, after the $i$th iteration, no swap for $A[j]$ with $j=1,2,\dots, n-2$ i.e. $(A[i])_{i=1}^{n-i}$ are sorted.