Solution Found!
In algorithm BubbleSort, suppose we include exchanges of list elements as a work unit
Chapter 3, Problem 14(choose chapter or problem)
In algorithm BubbleSort, suppose we include exchanges of list elements as a work unit, in addition to comparisons between list elements. a. Describe the worst case and find the number of comparisons and exchanges done in this case. b. Describe the best case and find the number of comparisons and exchanges done in this case. c. Assume that on the average exchanges between elements must be done about half the time. Find the number of comparisons and exchanges done in this case.
Questions & Answers
QUESTION:
In algorithm BubbleSort, suppose we include exchanges of list elements as a work unit, in addition to comparisons between list elements. a. Describe the worst case and find the number of comparisons and exchanges done in this case. b. Describe the best case and find the number of comparisons and exchanges done in this case. c. Assume that on the average exchanges between elements must be done about half the time. Find the number of comparisons and exchanges done in this case.
ANSWER:Step 1 of 4
Analysis of the algorithm involves solving the recurrence relation in the algorithm. Bubble sort repeatedly compares and swaps adjacent elements in every pass of the algorithm. The worst, best and average case analysis depends on the number of operations performed in the algorithm.