Bubble Sort Homework

Question

In class we are doing sorting algorithms and, although I understand them fine when talking about them and writing pseudocode, I am having problems writing actual code for them.

This is my attempt in Python:

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 1
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
            else:
                unsorted = True

print bubble(mylist)

Now, this (as far as I can tell) sorts correctly, but once it finishes it just loops indefinitely.

How can this code be fixed so the function finishes properly and correctly sorts a list of any (reasonable) size?

P.S. I know I should not really have prints in a function and I should have a return, but I just have not done that yet as my code does not really work yet.

Answer 1

To explain why your script isn't working right now, I'll rename the variable unsorted to sorted.

At first, your list isn't yet sorted. Of course, we set sorted to False.

As soon as we start the while loop, we assume that the list is already sorted. The idea is this: as soon as we find two elements that are not in the right order, we set sorted back to False. sorted will remain True only if there were no elements in the wrong order.

sorted = False  # We haven't started sorting yet

while not sorted:
    sorted = True  # Assume the list is now sorted
    for element in range(0, length):
        if badList[element] > badList[element + 1]:
            sorted = False  # We found two elements in the wrong order
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
    # We went through the whole list. At this point, if there were no elements
    # in the wrong order, sorted is still True. Otherwise, it's false, and the
    # while loop executes again.

There are also minor little issues that would help the code be more efficient or readable.

• In the for loop, you use the variable element. Technically, element is not an element; it's a number representing a list index. Also, it's quite long. In these cases, just use a temporary variable name, like i for "index".

  for i in range(0, length):
  

• The range command can also take just one argument (named stop). In that case, you get a list of all the integers from 0 to that argument.

  for i in range(length):
  

• The Python Style Guide recommends that variables be named in lowercase with underscores. This is a very minor nitpick for a little script like this; it's more to get you accustomed to what Python code most often resembles.

  def bubble(bad_list):
  

• To swap the values of two variables, write them as a tuple assignment. The right hand side gets evaluated as a tuple (say, (badList[i+1], badList[i]) is (3, 5)) and then gets assigned to the two variables on the left hand side ((badList[i], badList[i+1])).

  bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]
  

Put it all together, and you get this:

my_list = [12, 5, 13, 8, 9, 65]

def bubble(bad_list):
    length = len(bad_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if bad_list[i] > bad_list[i+1]:
                sorted = False
                bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

bubble(my_list)
print my_list

(I removed your print statement too, by the way.)