Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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))
share|improve this question

3 Answers 3

up vote 7 down vote accepted
  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.)

share|improve this answer
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.

share|improve this answer
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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