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?

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?

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

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?

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.

5 7 8 10 17