Why is my own implementation of Bubble Sort so much slower than another one I found online?

Question

I wrote my implementation of Bubble Sort according to my understanding of the general principle of how the algorithm works, and then compared it against another implementation I found online.

def my_bubble_sort(n):
    switched = True
    while switched:
        switched = False
        for i in range(1, len(n)):
            if n[i] < n[i - 1]:
                switched = True
                n[i - 1], n[i] = n[i], n[i - 1]
    return n


def some_other_bubble_sort(n):
    for i in range(len(n) - 1):
        for j in range(len(n) - 1 - i):
            if n[j] > n[j + 1]:
                n[j], n[j + 1] = n[j + 1], n[j]
    return n

While my_bubble_sort() is much faster on processing lists that are already sorted, some_other_bubble_sort() is almost three times faster (= takes 35% of the time) compared to my_bubble_sort() on actually random, unsorted lists.

I'm not sure why that is. Can anyone help me understand?

It can't be the additional checks against switched that make my implementation that much slower, can it?

Pastebin link

I also found that my version seems to be fairly close to the one taught at this MIT lecture.

Which one is generally preferable? Are they both valid implementations of bubble sort? Or is either of the two technically another sorting algorithm?

And which one would be preferable, generally speaking?

Answer 1

From your pastebin, here is the first place you go wrong:

unsorted1 = unsorted2 = [randint(1, 99) for _ in range(count)][:]

Here you assign unsorted1 and unsorted2 to point to the same list. So when you call some_other_bubble_sort on unsorted2, it is in fact no longer shuffled! It is sorted.

The solution is to first assign unsorted1 and then unsorted2 to a copy:

unsorted1 = [randint(1, 99) for _ in range(count)]
unsorted2 = unsorted1[:]

That makes your algorithm only slightly less than twice as slow. That can be explained simply by the fact your implementation does a lot more stuff. In Python the little things add up, like setting switched to True every iteration.