Bubble Sort Homework
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, length-i-1):
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
Aether McLoud
Updated on July 15, 2020Comments
-
Aether McLoud almost 4 years
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.
-
Aether McLoud almost 15 yearsI do beleive the question was more along the lines of 'How can this code be fixed', not 'what is your bubble sort?'
-
mtasic85 almost 15 yearsyou are absolutely right, but doing it in right way is more important
-
Blorgbeard almost 15 yearsYou can speed up a bubble-sort by skipping the portion of your list that you know is already sorted (because of previous iterations). See en.wikipedia.org/wiki/Bubble_sort#Alternative_implementations
-
plankalkul almost 15 yearsagain, all you really need to do is use a boolean (call it untouched). declare it outside your loop; loop until untouched = true. within your while loop, set untouched to be true; in the body of your if, set untouched to be false. Doing this, you can ditch your else case. in this way, if you ever switch two elements, your loop will continue; if you don't, the loop will not.
-
Svante almost 15 yearsShouldn't the "unsorted = False" be outside the for loop?
-
Trevor Oke almost 15 yearsIt had a few more problems than that ;)
-
Daniel Martin almost 15 yearsIt's a bit too bad there's not a "WRONG" button I can hit for this answer. I think this question and the responses - and especially the voting - need to be featured the next time Joel Spolsky talks about how well he's tuned the social interactions on stackoverflow.
-
Jonathan Leffler almost 15 years@Daniel: you can do what other people with enough reputation (100) can do - downvote the wrong answer. There's a germ of truth - negated conditions enshrined in flag variables is bad. It isn't the whole answer, though - @McWafflestix has it right, I think.
-
Daniel Martin almost 15 years@Jonathan - I did downvote it, but a mere downvote seems insufficient. (It's worse than merely "not helpful") I'll grant that the general proposition that inverted variable names confuse those reading the code, but that's not the main thrust of this answer. The main thrust is just wrong.
-
Martin Cote almost 15 yearsYou guys are right, I answered prematurely on this one. Sorry about that.
-
Daniel Martin almost 15 years@Martin - and I should point out that I'm more surprised/shocked by the voting than the answer. The reputation system encourages you to get that first answer in, right away. The broken part is how an incorrect answer is voted up.
-
Martin Cote almost 15 yearsI suspect that most people vote without really understanding the question in the first place (just like the way I answered the question). OTOH, the person who asks the question has the privilege of choosing the 'right' answer afterwards.
-
KingNestor almost 15 years@Martin Cote, Just edit your answer with the correct information. Don't leave a partially incorrect answer out there.
-
Wesley almost 15 yearsGreat catch, Tung.
bubble
sorts the list in place and doesn't return anything. Therefore, sorting the list and displaying it is now performed separately. -
Tom Leys almost 15 years+1 well structured, clear advice. Great to see you walk the reader through what you did and why rather than just write a quick fix.
-
Martin Brown almost 15 yearsI'm a C# programmer, so this might just be because I don't get Python, but don't you need something in the while loop to subtract 1 from length to get a normal bubble sort algorithm?
-
Wesley almost 15 yearsThis is a naive (but not incorrect) implementation of Bubble Sort. After each iteration of the
while
loop, the largest element "bubbles up" to the end of the list. As such, after one iteration, the last element is definitely in the right place (and will not be moved by successive iterations). By subtracting 1 from length, you are optimizing the algorithm by only sorting the sublist that is not yet sorted (thelength-n
frontmost elements of the list). I elected to skip this optimization, as it is more an optimization than a vital part of the algorithm. -
Peter Perháč almost 15 years
Put it all together, and you get this:
...well,you missed this one:The range command can also take just one argument (named stop).
-
Wesley almost 15 yearsSharp eyes, MasterPeter. That was a silly oversight easily corrected, so thanks for pointing it out.
-
Sam Meldrum almost 15 years@Martin Cote - agree with KingNestor. Either correct your answer or delete it. Why leave it there when it is acknowledged to be wrong?
-
Makoto about 11 yearsIt's a little less belabored with the way that you can swap values in Python:
arr[a], arr[b] = arr[b], arr[a]
-
Grijesh Chauhan over 10 yearsadding good information is helpful in my view. so good answer ..thought you might use flag to break earliest possible.
-
Zile Rehman almost 10 yearsBubble larger element all the way to the end. And decrement the end counter, "n" so that you will not have to compare it again. Continue with the while loop as long as there are exchanges. Worst Case: O(N^2) Best Case: O(N)
-
kdopen about 9 yearsPlease indent your code sample correctly: this is, of course, especially important in Python. You might also want to explain why your solution is worth considering considering there is also an answer with 100 votes
-
Alexander about 6 yearsWhile this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value.
-
raviraja almost 6 yearsas @Wesley mentioned your code is not considering the fact that 'i' elements are bubbled at end of array(sorted) at any given point of time,so you only have to iterate over 'n-i' elements instead of n elements
-
Masoud Rahimi over 4 yearsIt would be better to add some explanation to your code.