BUBBLE$-$SORT$($A$,$n$)$

for i$=1$ to n

for j$=$n downto i$+1$

if A$[$j$]<$ A$[$j$-1]$ then exchange A$[$j$]$ A$[$j$-1]$

BUBBLE$-$SORT works by first scanning the array A from A $[$n$]$ all the way down to

A$[1]$ and exchanging any adjacent elements that are out of order. This first scan

guarantees that the smallest element in A$[1...$n$]($i$.$e$.$ the smallest element of A$)$ will end

up in A$[1].$ BUBBLE$-$SORT then scans the array A for a second time from A$[$n$]$ all the

way down to A$[2]$ and exchanges again any adjacent elements that are out of order. This

second scan guarantees that the smallest element in A$[2$::n$]($i$.$e$.$ the next smallest element

of A$)$ will end up in A$[2].$ BUBBLE$-$SORT continues to perform scans in this way $($up to

n scans$),$ and in every scan it guarantees that the element with rank i ends up in A$[$i$].$

After the last scan, the array A is sorted.

$($a$)$ Compute running time of Bubble sort. Use cost and times columns to compute the

running time. $($Cost of a line is the amount of time that is required to execute the line, e$.$g$.$

constant c$1.$ Times is the number of times the line is executed.$)$ After you get the exact

expression for the running time, represent it in big$-$Oh notation $($O$-$notation$).$

$($b$)$ Which one do you think is faster in practice, INSERTION$-$SORT or

BUBBLE$\_$SORT, and why?

$($c$)$ Implement both sorts in a programming language of your choice. Make sure your

code matches the provided pseudocodes for the algorithms. Try them on randomly