Part $2$: Analyze and Implement Bubble Sort

Bubble Sort is another well$-$known sorting algorithm, where you repeatedly swap adjacent items if they are in the wrong order $($eventually allowing larger items to "bubble" to the end of the list$).$ Although it is notoriously inefficient, it is relatively straightforward.

Examine the pseudocode for the Bubble Sort algorithm:

bubbleSort $($A$)$ :

print $A$

for each index i in length $(A)-1$ :

for each index $j$ in length $(A)-1-$i:

if $A[j]>A[j+1]$ :

swap $A[j]$ and $A[j+1]$

print $A$

By hand, write out the "output" of the pseudocode if you were to run the above algorithm $($i$.$e$.,$ what gets printed at each iteration of the loop$)$ for the input $A=[8,1,4,2]$

Upload a photo or type your output to Canvas.

a$)$ Hint: There should be $7$ print statements. You may fill out the following table if you would like, where the rightmost column is what is printed.

$\backslash$table$[[i,j,A[i],A[j],pr{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}(A)$