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
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?
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?