1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Algorithms other than Bubblesort are "preferable" by most metrics people care about. People don't spend a lot of time wondering which of two slightly different but suboptimal in both theory and practice algorithms to use. $\endgroup$ – Derek Elkins Jun 24 '18 at 4:54
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.