1. Consider the following Bubble sort algorithm. Answer the following based on this algorithm

for i <-- 0 to n-2 do

for j <-- 0 to n-2-i do

if (A[j+1] < A[j])

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

1. Trace this algorithm with the following array. Show the array after each iteration of the ith loop. Show your work in detail.

5 4 7 3 1

2. How many comparisons in total you made i.e. how many times the comparison statement if (A[j+1] < A[j]) is executed? [5 Point]

3. How many swaps in total you made i.e. how many times the swap statement swap A[j] and A[j+1] is executed? [5 Point]

4. Is Bubble sort stable? You can answer this with the array 2 2 1 3 5. Justify your answer. [10 Points]

5. Compare the number of comparisons and swaps in 2.(b, c) and 1.(b, c)? What does this tell you about the efficiency of these algorithms? [5 Point]

6. Trace the bubble sort algorithm for the following already sorted array. The algorithm still makes a lot of comparisons even though the list is already sorted. Make an improvement to the algorithm so that if a pass through the list makes no swaps, the program stops and declares that the list is already sorted. Write the improved algorithm. [15 Point]

5 7 8 10 17