131

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.

Improve this question
16
  • 8
    god, this pisses me off. Why do they even teach a worthless algorithm like this in the first place. No knock at the question, just the source of it. Commented May 21, 2009 at 21:55
  • 125
    The post is essentially: "I have trouble coding, this is what I did, it doesn't work." There's obviously an implicit "Can someone give me some pointers please?" Unlike many homework questions, this one (a) is well written, (b) is upfront about being homework, and (c) includes a good attempt at solving the problem. I don't think the lack of an actual question mark detracts too greatly.. Commented May 21, 2009 at 22:48
  • 37
    Bubble sort is used as a learning tool because it's the easiest sort algorithm for most people to understand. It's a good entry point for learning about sorting and algorithms in general. If we only taught stuff that people would actually use, the discussion of sorting would start and end with "use the library sort routine". Commented May 21, 2009 at 23:28
  • 38
    This question is a poster-child for how to ask a good "homework" questions. To John Fouhy's point, there is a code sample, it's well written, and the poster is trying hard to make it easy for us to help. Well done, joshhunt. Commented May 22, 2009 at 0:21
  • 20
    Bubble sort is not an easy sort algorithm for people to understand. From both my own experience and experience teaching, I can confidently say that insertion sort, selection sort, min-sort (minimum element sort), even (for some students) mergesort and quicksort are easier to understand — after all, they correspond to somewhat natural ways of sorting a list, but bubble sort is just artificial. Further, bubble sort is prone to many off-by-one errors and infinite loop errors, like this question here. As Knuth says, "the bubble sort seems to have nothing to recommend it, except a catchy name..." Commented Jun 11, 2009 at 2:59

28 Answers 28

Reset to default
127

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.)

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Just on that last bit of code, bubble doesn't return anything, so the end result is that 'None' is printed. You probably either want to return the list, or do bubble(my_list) and then print my_list.
+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.
I'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?
This 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 (the length-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.
Put it all together, and you get this: ...well,you missed this one: The range command can also take just one argument (named stop).
|
10

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
Improve this answer

Comments

8

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
Improve this answer

8 Comments

It'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.
@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.
You guys are right, I answered prematurely on this one. Sorry about that.
@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.
I 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.
|
7

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.

Improve this answer

Comments

6 
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
Improve this answer

5 Comments

I do beleive the question was more along the lines of 'How can this code be fixed', not 'what is your bubble sort?'
you are absolutely right, but doing it in right way is more important
True, perhaps, mtasic... but anything tagged as homework is most instructively tweaked rather than re-written (especially when it's tagged as homework by the OP).
This is a perfect re-write of the text book C bubble sort most people study. I wrote the same.
adding good information is helpful in my view. so good answer ..thought you might use flag to break earliest possible.
3

#A very simple function, can be optimized (obviously) by decreasing the problem space of the 2nd array. But same O(n^2) complexity.

def bubble(arr): l = len(arr) for a in range(l): for b in range(l-1): if (arr[a] < arr[b]): arr[a], arr[b] = arr[b], arr[a] return arr
Improve this answer

1 Comment

It's a little less belabored with the way that you can swap values in Python: arr[a], arr[b] = arr[b], arr[a]
1

You've got a couple of errors in there. The first is in length, and the second is in your use of unsorted (as stated by McWafflestix). You probably also want to return the list if you're going to print it:

mylist = [12, 5, 13, 8, 9, 65] def bubble(badList): length = len(badList) - 2 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 unsorted = True return badList print bubble(mylist)

eta: You're right, the above is buggy as hell. My bad for not testing through some more examples.

def bubble2(badList): swapped = True length = len(badList) - 2 while swapped: swapped = False for i in range(0, length): if badList[i] > badList[i + 1]: # swap hold = badList[i + 1] badList[i + 1] = badList[i] badList[i] = hold swapped = True return badList
Improve this answer

2 Comments

Shouldn't the "unsorted = False" be outside the for loop?
It had a few more problems than that ;)
1

I am a fresh fresh beginner, started to read about Python yesterday. Inspired by your example I created something maybe more in the 80-ties style, but nevertheless it kinda works

lista1 = [12, 5, 13, 8, 9, 65] i=0 while i < len(lista1)-1: if lista1[i] > lista1[i+1]: x = lista1[i] lista1[i] = lista1[i+1] lista1[i+1] = x i=0 continue else: i+=1 print(lista1)
Improve this answer

Comments

1

The problem with the original algorithm is that if you had a lower number further in the list, it would not bring it to the correct sorted position. The program needs to go back the the beginning each time to ensure that the numbers sort all the way through.

I simplified the code and it will now work for any list of numbers regardless of the list and even if there are repeating numbers. Here's the code

mylist = [9, 8, 5, 4, 12, 1, 7, 5, 2] print mylist def bubble(badList): length = len(badList) - 1 element = 0 while element < length: if badList[element] > badList[element + 1]: hold = badList[element + 1] badList[element + 1] = badList[element] badList[element] = hold element = 0 print badList else: element = element + 1 print bubble(mylist)
Improve this answer

Comments

1 
def bubble_sort(l): exchanged = True iteration = 0 n = len(l) while(exchanged): iteration += 1 exchanged = False # Move the largest element to the end of the list for i in range(n-1): if l[i] > l[i+1]: exchanged = True l[i], l[i+1] = l[i+1], l[i] n -= 1 # Largest element already towards the end print 'Iterations: %s' %(iteration) return l
Improve this answer

1 Comment

Bubble 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)
1 
def bubbleSort(alist): if len(alist) <= 1: return alist for i in range(0,len(alist)): print "i is :%d",i for j in range(0,i): print "j is:%d",j print "alist[i] is :%d, alist[j] is :%d"%(alist[i],alist[j]) if alist[i] > alist[j]: alist[i],alist[j] = alist[j],alist[i] return alist

alist = [54,26,93,17,77,31,44,55,20,-23,-34,16,11,11,11]

print bubbleSort(alist)

Improve this answer

1 Comment

Please 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
1 
def bubble_sort(a): t = 0 sorted = False # sorted = False because we have not began to sort while not sorted: sorted = True # Assume sorted = True first, it will switch only there is any change for key in range(1,len(a)): if a[key-1] > a[key]: sorted = False t = a[key-1]; a[key-1] = a[key]; a[key] = t; print a
Improve this answer

Comments

1

A simpler example:

a = len(alist)-1 while a > 0: for b in range(0,a): #compare with the adjacent element if alist[b]>=alist[b+1]: #swap both elements alist[b], alist[b+1] = alist[b+1], alist[b] a-=1

This simply takes the elements from 0 to a(basically, all the unsorted elements in that round) and compares it with its adjacent element, and making a swap if it is greater than its adjacent element. At the end the round, the last element is sorted, and the process runs again without it, until all elements have been sorted.

There is no need for a condition whether sort is true or not.

Note that this algorithm takes into consideration the position of the numbers only when swapping, so repeated numbers will not affect it.

Improve this answer

Comments

0 
def bubble_sort(li): l = len(li) tmp = None sorted_l = sorted(li) while (li != sorted_l): for ele in range(0,l-1): if li[ele] > li[ele+1]: tmp = li[ele+1] li[ele+1] = li [ele] li[ele] = tmp return li
Improve this answer

Comments

0 
def bubbleSort ( arr ): swapped = True length = len ( arr ) j = 0 while swapped: swapped = False j += 1 for i in range ( length - j ): if arr [ i ] > arr [ i + 1 ]: # swap tmp = arr [ i ] arr [ i ] = arr [ i + 1] arr [ i + 1 ] = tmp swapped = True if __name__ == '__main__': # test list a = [ 67, 45, 39, -1, -5, -44 ]; print ( a ) bubbleSort ( a ) print ( a )
Improve this answer

Comments

0 
def bubblesort(array): for i in range(len(array)-1): for j in range(len(array)-1-i): if array[j] > array[j+1]: array[j], array[j+1] = array[j+1], array[j] return(array) print(bubblesort([3,1,6,2,5,4]))
Improve this answer

1 Comment

While 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.
0 
arr = [5,4,3,1,6,8,10,9] # array not sorted for i in range(len(arr)): for j in range(i, len(arr)): if(arr[i] > arr[j]): arr[i], arr[j] = arr[j], arr[i] print (arr)
Improve this answer

Comments

0

I consider adding my solution because ever solution here is having

  1. greater time
  2. greater space complexity
  3. or doing too much operations

then is should be

So, here is my solution:

def countInversions(arr): count = 0 n = len(arr) for i in range(n): _count = count for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: count += 1 arr[j], arr[j + 1] = arr[j + 1], arr[j] if _count == count: break return count
Improve this answer

Comments

0

If anyone is interested in a shorter implementation using a list comprehension:

def bubble_sort(lst: list) -> None: [swap_items(lst, i, i+1) for left in range(len(lst)-1, 0, -1) for i in range(left) if lst[i] > lst[i+1]] def swap_items(lst: list, pos1: int, pos2: int) -> None: lst[pos1], lst[pos2] = lst[pos2], lst[pos1]
Improve this answer

Comments

0

Here is a different variation of bubble sort without for loop. Basically you are considering the lastIndex of the array and slowly decrementing it until it first index of the array.

The algorithm will continue to move through the array like this until an entire pass is made without any swaps occurring.

The bubble is sort is basically Quadratic Time: O(n²) when it comes to performance.

class BubbleSort: def __init__(self, arr): self.arr = arr; def bubbleSort(self): count = 0; lastIndex = len(self.arr) - 1; while(count < lastIndex): if(self.arr[count] > self.arr[count + 1]): self.swap(count) count = count + 1; if(count == lastIndex): count = 0; lastIndex = lastIndex - 1; def swap(self, count): temp = self.arr[count]; self.arr[count] = self.arr[count + 1]; self.arr[count + 1] = temp; arr = [9, 1, 5, 3, 8, 2] p1 = BubbleSort(arr) print(p1.bubbleSort())
Improve this answer

Comments

0 
def bubblesort(L,s): if s >-1 : bubblesort(L,s-1) for i in range(len(L)-1-s): if L[i]>L[i+1]: temp = L[i+1] L[i+1] = L[i] L[i] = temp return L Nlist = [3,50,7,1,8,11,9,0,-1,5] print(bubblesort(Nlist,len(Nlist)))
Improve this answer

1 Comment

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
-1

Answers provided by the-fury and Martin Cote fixed the problem of the infinite loop, but my code would still not work correctly (for a larger list, it would not sort correctly.). I ended up ditching the unsorted variable and used a counter instead.

def bubble(badList): length = len(badList) - 1 n = 0 while n < len(badList): for element in range(0,length): if badList[element] > badList[element + 1]: hold = badList[element + 1] badList[element + 1] = badList[element] badList[element] = hold n = 0 else: n += 1 return badList if __name__ == '__main__': mylist = [90, 10, 2, 76, 17, 66, 57, 23, 57, 99] print bubble(mylist)

If anyone could provide any pointers on how to improve my code in the comments, it would be much appreciated.

Improve this answer

2 Comments

You 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
again, 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.
-1

Try this

a = int(input("Enter Limit")) val = [] for z in range(0,a): b = int(input("Enter Number in List")) val.append(b) for y in range(0,len(val)): for x in range(0,len(val)-1): if val[x]>val[x+1]: t = val[x] val[x] = val[x+1] val[x+1] = t print(val)
Improve this answer

Comments

-1

idk if this might help you after 9 years... its a simple bubble sort program

 l=[1,6,3,7,5,9,8,2,4,10] for i in range(1,len(l)): for j in range (i+1,len(l)): if l[i]>l[j]: l[i],l[j]=l[j],l[i]
Improve this answer

Comments

-1 
def merge_bubble(arr): k = len(arr) while k>2: for i in range(0,k-1): for j in range(0,k-1): if arr[j] > arr[j+1]: arr[j],arr[j+1] = arr[j+1],arr[j] return arr break else: if arr[0] > arr[1]: arr[0],arr[1] = arr[1],arr[0] return arr
Improve this answer

Comments

-1 
def bubble_sort(l): for i in range(len(l) -1): for j in range(len(l)-i-1): if l[j] > l[j+1]: l[j],l[j+1] = l[j+1], l[j] return l
Improve this answer

1 Comment

It would be better to add some explanation to your code.
-1 
def bubble_sorted(arr:list): while True: for i in range(0,len(arr)-1): count = 0 if arr[i] > arr[i+1]: count += 1 arr[i], arr[i+1] = arr[i+1], arr[i] if count == 0: break return arr arr = [30,20,80,40,50,10,60,70,90] print(bubble_sorted(arr)) #[20, 30, 40, 50, 10, 60, 70, 80, 90]
Improve this answer

Comments

-3

def bubbleSort(a): def swap(x, y): temp = a[x] a[x] = a[y] a[y] = temp #outer loop for j in range(len(a)): #slicing to the center, inner loop, python style for i in range(j, len(a) - j):
#find the min index and swap if a[i] < a[j]: swap(j, i) #find the max index and swap if a[i] > a[len(a) - j - 1]: swap(len(a) - j - 1, i) return a

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.