def bubbleSort (my_ list): for passnum in range( len( my list 1, , -1): if my_li

Question

def bubbleSort (my_ list): for passnum in range( len( my list 1, , -1): if my_listl i] y listl i 1 ]: for i in range( passnum): temp = my-list [ i ] my-list [ i ] = my-listl i + 1 ] mylist [ i + 1] = temp return my list Note that the range function here takes 3 inputs instead of 1. Basically the range function here is incrementing from ln(list) - 1 to O using a step size of -1. More information can be found online in the official python documentation. 3.4 Analysis 1 (2 points) Assume we define complexity as the number of element comparisons we make (as we do on line 1), what would be the total runtime of this algorithm? 3.5 Analysis 2 (2 points) Assume we define complexity as the number of element swaps we make (as we do on lines 5-7) What would be the total runtime of this algorithm?

Explanation / Answer

Let us say that we have 5 elements sorted in reverse order

For first pass, we did 4 comparisons and 12 swaps

For second pass, we did 3 comparisons and 9 swaps

For third pass, we did 2 comparisons and 6 swaps

And for final pass, we did 1 comparison and 3 swaps

3.4

For 5 elements:

We did 4+3+2+1 comparisons

Hence, for n elements, we will do

= n-1 + n-2 + …..2 +1

= n(n-1)/2

=O(n^2) comparisons

3.5

For 5 elements:

We did 12+9+6+3 swaps

=3(4+3+2+1) swaps

Hence, for n elements, we will do

= 3( n-1 + n-2 + …..2 +1 )

= 3( n(n-1)/2 )

=O(n^2) comparisons

If you face any issue, you can leave a comment.

if you find this helpful, then please dont forget to leave a thumbs up, thanks

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.