Problem $5.$ Consider an array $A$ of $n$ numbers. Begin sorting the array by repeatedly comparing adjacent

elements and swapping them if they are in the wrong order. This process should start at the beginning of the

array and continue until you reach the end. After the first pass, the largest element will be in its correct position

at the end of the array. Continue this process for the first $n-1$ elements of the array.

$($a$)$ Write pseudocode for this sorting algorithm, which is commonly known as the bubble$-$sort algorithm.

pts$]$

$($b$)$ Identify and explain the loop invariant maintained by this algorithm. Use it to prove correctness of the

algorithms. $[5$ pts$]$

$($c$)$ Explain why the algorithm only needs to run for the first $n-1$ elements rather than for all $n$ elements.

pts$]$

Proof.