Question or problem about Python programming:
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.
How to solve the problem:
Solution 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 variableelement
. 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, likei
for “index”.for i in range(0, length):

The
range
command can also take just one argument (namedstop
). 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.)
Solution 2:
The goal of bubble sort is to move the heavier items at the bottom in each round, while moving the lighter items up. In the inner loop, where you compare the elements, you don’t have to iterate the whole list in each turn. The heaviest is already placed last. The swapped variable is an extra check so we can mark that the list is now sorted and avoid continuing with unnecessary calculations.
def bubble(badList): length = len(badList) for i in range(0,length): swapped = False for element in range(0, lengthi1): if badList[element] > badList[element + 1]: hold = badList[element + 1] badList[element + 1] = badList[element] badList[element] = hold swapped = True if not swapped: break return badList
Your version 1, corrected:
def bubble(badList): length = len(badList)  1 unsorted = True while unsorted: unsorted = False 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 unsorted = True #print badList #else: #unsorted = True return badList
Solution 3:
This is what happens when you use variable name of negative meaning, you need to invert their values. The following would be easier to understand:
sorted = False while not sorted: ...
On the other hand, the logic of the algorithm is a little bit off. You need to check whether two elements swapped during the for loop. Here’s how I would write it:
def bubble(values): length = len(values)  1 sorted = False while not sorted: sorted = True for element in range(0,length): if values[element] > values[element + 1]: hold = values[element + 1] values[element + 1] = values[element] values[element] = hold sorted = False return values
Solution 4:
Your use of the Unsorted variable is wrong; you want to have a variable that tells you if you have swapped two elements; if you have done that, you can exit your loop, otherwise, you need to loop again. To fix what you’ve got here, just put the “unsorted = false” in the body of your if case; remove your else case; and put “unsorted = true before your for
loop.
Solution 5:
def bubble_sort(l): for passes_left in range(len(l)1, 0, 1): for index in range(passes_left): if l[index] < l[index + 1]: l[index], l[index + 1] = l[index + 1], l[index] return l