Homework answers / question archive / Write function bubble_sort(L) that consumes L a list of integers, returns None and sorts L via mutation using the bubble sort algorithm

Write function bubble_sort(L) that consumes L a list of integers, returns None and sorts L via mutation using the bubble sort algorithm

Computer Science

Share With

---

Write function

bubble_sort(L)

that consumes L a list of integers, returns None and sorts L via mutation using the bubble sort algorithm.

The bubble sort algorithm sorts a list by comparing the first two elements, swapping them if they are in the wrong order, comparing the second and the third elements, swapping them if needed, and so on until reaching the end of the list. Then, start again at the beginning until no further swapping is required.

Because each pass always moves the largest element at the correct location (the end), checking it again on the next pass is not needed.

 

Example

Initial conditions

L = [6, 1, 5, 3]

Pass 1, Step 1

Compare 6 and 1, and swap them since they are in the wrong order.

L = [1, 6, 5, 3]

Pass 1, Step 2

Compare 6 and 5, and swap them since they are in the wrong order.

L = [1, 5, 6, 3]

Pass 1, Step 3

Compare 6 and 3, and swap them since they are in the wrong order.

L = [1, 5, 3, 6]

We reached the end of the list. At this point, we know that at least 6 (the largest value) is at the correct location. So we won't need to check the last position on the next pass.

Pass 2, Step 1

Compare 1 and 5, and do not swap them since they are in the right order.

L = [1, 5, 3, 6]

Pass 2, Step 2

Compare 5 and 3, and swap them since they are in the wrong order.

L = [1, 3, 5, 6]

No need to compare with the last value, we already now it is correct.

Pass 3, Step 1

Compare 1 and 3, and do not swap them since they are in the right order.

L = [1, 3, 5, 6]

No need to compare with the next value, we already now it is correct. The list is sorted!

You must use bubble sort in your solution. No marks will be given for any other sorting algorithm used.

 

This is what I did but I am not sure this is right or not. if it is wrong, what's the good code for this question? (L[j], L[j+1] = L[j+1], L[j] is not allowed since it wasn't in the lecture notes)

 

 for i in range(0, len(L)):

   for n in range(0, len(L)-i-1):

     if L[n] > L[n+1]:

       temp = L[n]

       L[n] = L[n + 1]

       L[n + 1] = temp

 return None