Bubble sort algorithm in Python

Question

I'm starting to implement basic sorting algorithms. Criticisms on the implementation is welcome.

#import pudb; pu.db def bubble_sort(list_): """Implement bubblesort algorithm: iterate L to R in list, switching values if Left > Right. Break when no alterations made to to list. """ not_complete = True while not_complete: not_complete = False for val, item in enumerate(list_): if val == len(list_)-1: val = 0 else: if list_[val] > list_[val+1]: list_[val], list_[val+1] = list_[val+1], list_[val] not_complete = True return list_ if __name__ == '__main__': assert bubble_sort(list(range(9))[::-1]) == list(range(9)) 

Answer 1

1. This line seems to be left over from a debugging session:

   #import pudb; pu.db 

   But there is no need to edit your code to debug it — and you should strive to avoid doing so, because it's too easy to forget to remove the debugging code. (And in your other question you did forget to remove it!)

   Instead, learn how to use the tools. You can run the built-in debugger pdb from the command line like this:

   $ python -mpdb myprogram.py 

   and you can run pudb from the command line as described in the documentation.

2. The docstring is written from the wrong point of view:

   """Implement bubblesort algorithm: iterate L to R in list, switching values if Left > Right. Break when no alterations made to to list. """ 

   Docstrings should be written from the user's point of view: What does this function do? How should I call it? What values does it return? What side effects does it have? For example:

   >>> help(abs) Help on built-in function abs in module builtins: abs(...) abs(number) -> number Return the absolute value of the argument. 

   Your docstring is written from the point of view of the implementer. This kind of material should be in comments.

3. You spelled your variable list_ to avoid shadowing the built-in function list. I would prefer to find a better name for the variable rather than arbitrarily respelling it like this. Since your algorithm works on any mutable sequence (not just lists), then seq might be a good name.

4. Instead of:

   else: if condition: code 

   write:

   elif condition: code 

5. You have a special case:

   if val == len(list_)-1: val = 0 

   to ensure that val + 1 does not run off the end of the list. But it would be better to stop the iteration before that happens. So instead of:

   for val, item in enumerate(list_): 

   write:

   for val in range(len(list_) - 1): 

6. val is an index into the list: it's conventional to give such variables names like i and j.

7. Each time around the while not_complete loop, you make a pass over the whole of the sequence. But there is an easy optimization, noted by Wikipedia:

   The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time.

   So I would write it like this:

   def bubble_sort(seq): """Sort the mutable sequence seq in place and return it.""" for i in reversed(range(len(seq))): finished = True for j in range(i): if seq[j] > seq[j + 1]: seq[j], seq[j + 1] = seq[j + 1], seq[j] finished = False if finished: break return seq 

8. You have some test code at the end of the script. It is best to organize test code like this into unit tests using the unittest module. For example:

   from unittest import TestCase from random import random class BubbleSortTest(TestCase): def test_bubble_sort(self): seq = [random() for _ in range(4000)] sorted_seq = sorted(seq) self.assertEqual(bubble_sort(seq), sorted_seq) 

   Note how I've used randomization to get a wider range of test cases. (I've also made the length of the test array large enough to give a noticeable delay and so emphasize how poor an algorithm bubble sort is.)

Answer 2

for val, item in enumerate(list_): 

You don't use item, so don't get it. Instead, use xrange(len(list_))

if val == len(list_)-1: val = 0 

This rechecks position 0 again. There is no need to do that. Instead, change the loop so it goes one less round.

Answer 3

def swap(mylist,i): temp1 = mylist[i] temp2 = mylist[i+1] mylist[i] = temp2 mylist[i+1] = temp1 def one_scan(mylist): for i in range (len(mylist)-1): if(mylist[i] >= mylist[i+1]): swap(mylist,i) def sortMyL(L): i = 0 while(i<len(L)): one_scan(L) i+=1 print("Sorted list") print(L) 

Let's say x = [3,2,1,6,7]

sortMyL(x) will print out [1,2,3,6,7]

Feel free to ask any questions.