3.2 BUBBLE SORT 673.2.4
- Show the results of each pass of BubbleSort applied to the list [7, 3, 9, 4,
2, 5, 6, 1, 8]. - Show the results of each pass of BubbleSort applied to the list [3, 5, 2, 9,
8, 1, 6, 4, 7]. - A different version of bubble sort keeps track of where the last exchange
occurred, and on the next pass, it will not go past this point. If the last
change was made in the swap of locations i and i + 1, the next pass will not
look at any elements past location i.
a. Write this new version of bubble sort.
b. Write a short paragraph that explains exactly why this new version of
bubble sort will work.
c. Does this new version of bubble sort change the worst-case analysis? Give
an analysis or justification for your answer.
d. This new version of bubble sort does change the average-case analysis.
Give a detailed explanation of what is involved in calculating this new
average-case analysis. - Another version of bubble sort alternates passes so that the odd passes are
like the original, but the even passes move from the bottom of the array to
the top. On the odd passes the larger elements move toward the bottom,
and on the even passes the smaller elements move toward the top.
a. Write this new version of bubble sort.
b. Write a short paragraph that explains exactly why this new version of
bubble sort will work.
c. Does this new version of bubble sort change the worst-case analysis? Give
an analysis or justification for your answer.
d. This new version of bubble sort does change the average-case analysis.
Give a detailed explanation of what is involved in calculating this new
average-case analysis. - A third version of bubble sort combines the ideas of Questions 1 and 2. This
bubble sort moves back and forth through the array but adjusts its upper and
lower range of the sort based on where the last changes were made.
a. Write this third version of bubble sort.
■3.2.4 EXERCISES