Bubble sort algorithm - do i have an error?

Question

I was following an online website tutorial on bubble sort and decided to do it myself before looking at the answer.

I get this:

 def bubbleSort(theList): i=0 while i < len(theList)-1: if theList[i+1] < theList[i]: theList[i],theList[i+1] = theList[i+1],theList[i] i=i+1 return theList myList = [13,5,6,2,10,11] print(bubbleSort(myList))

but in the answer they have:

 def bubbleSort(alist): for passnum in range(len(alist)-1,0,-1): for i in range(passnum): if alist[i]>alist[i+1]: temp = alist[i] alist[i] = alist[i+1] alist[i+1] = temp alist = [54,26,93,17,77,31,44,55,20] bubbleSort(alist) print(alist)

the problem i have is that my answer works but i dont understand why there is an extra line in the example answer:

 for passnum in range(len(alist)-1,0,-1):

whats the point of this? also in other examples i also see 2 for loops being used. is there an error with my code? it seems to work

Your answer does not work! You only do one pass, so only 13 bubbles to the end. — President James K. Polk
– President James K. Polk, Commented Aug 5, 2019 at 17:58
Your code outputs [5, 6, 2, 10, 11, 13] I have some concerns about the 2. Yes, you need two loops to perform bubble sort. — Kenny Ostrom
– Kenny Ostrom, Commented Aug 5, 2019 at 17:59
An extremely small amount of testing shows that your code fails. It failed on the very first example I ran it on. It isn't clear why you say that it "seems to work". — John Coleman
– John Coleman, Commented Aug 5, 2019 at 18:01
Read about how a bubble sort works and you'll see why a single loop cannot work. You'll look at each element (first loop) and compare it against all other elements (so a second loop is needed). There are some good animated visual examples out there that can show how this is working. — Phaelax
– Phaelax, Commented Aug 5, 2019 at 18:43

blue note · Accepted Answer · 2019-08-06 08:27:25Z

2

You make just one pass of the bubble sort. You code is correct, but it only brings the one, largest element to the end of the list. You should repeat the code n times, with the range reducing by one each time.

You should note that your code has complexity O(n), which bubblesort has O(n^2).

edited Aug 6, 2019 at 8:27

answered Aug 5, 2019 at 18:02

blue note

29.5k10 gold badges83 silver badges110 bronze badges

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

3 Comments

Error - Syntactical Remorse Over a year ago

Out of curiosity why use $ to express big O?

blue note Over a year ago

@Error-SyntacticalRemorse: bad formatting. most related sites render equation in $$ in latex format, but for some reason stackoveflow doesn't

John Coleman Over a year ago

@blue_note The idea has been discussed on meta: meta.stackexchange.com/q/30559/357835

Collectives™ on Stack Overflow

Bubble sort algorithm - do i have an error?

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related