Is this Bubble sort logic correct

Question

I saw some videos on youtube about list sorting technique, bubble sort and the code they used was

list1 = [4, 8, 5, 3, 1]

for i in range(len(list1)-1, 0, -1):
    for j in range(i):
        if list1[j] > list1[j+1]:
            t = list1[j]
            list1[j] = list1[j+1]
            list1[j+1] = t
print(list1)

After taking different list and sorting them on my own without python i found out a pattern, and made slight arrangements to the code and i am getting the same output.

list1 = [4, 8, 5, 3, 1]

for i in range(1,len(list1)):
    for j in range(len(list1)-1):
        if list1[j] > list1[j+1]:
            t = list1[j]
            list1[j] = list1[j+1]
            list1[j+1] = t

print(list1)

But here, I just want to know if the logic is the same and the method also is bubble sorting cuz in future when asks me to do bubble sort, i dont want to do this and end up being embarrassed :p

Thanks in advance :D

Answer 1

The algorithm is bubble sort, but with unnecessary comparisons. You sort it by iteration over all n elements n times. But after the first time it is guaranteed, that the highest value is at the last position, so you only need to go over the first n-1 elements in the next step and so on. In your algorithm you just continue to the end. That does not make it wrong, but in is not that efficient. However it does not change the time complexity of O(n^2).

EDIT: In reply to some comments: yes, in general you don't use bubble sort for efficiency. But there is a case, where it performs quite well (with the optimization where you stop when ther was one iteration without changes) and that is if you have a nearly sorted list.