(10 points) Consider the following sorting algorithm (the UNH sort) to sort an array A[1..n].

for i = n-1 downto 1 do

for j = 1 to i do

if A[j] > A[j+1] then

swap(A[j],A[j+1])

(a) Trace this sorting algorithm on the list 5, 8, 2, 4, 9, 3 i.e. show what the list looks like after each iteration of the outer loop. Also, calculate the exact number of total data comparisons made.

(b) As we did with insertion sort in class, do a worst case analysis (use big O notation) of the running time of this algorithm. You dont have to give any explanations here - just state your answer.

(c) As we did with insertion sort in class, do a best case analysis (use big O notation) of the running time of this algorithm. You dont have to give any explanations here - just state your answer.

The UNH Sort Array is only a generic name that has no relevance. Just focus on the code snip and the for loops in how to trace through the array