Bubble sort doesn't stop as expected

[mr.me]

This was written in python as an excersie, it's a terribly inefficient use of python. Still I don't understand why the sort doesn't stop as soon as possible
can anyone one point out the error?

def   bubbleSort (theList):
      size = len(theList) - 1
      while (size > 0):
         index = 0
         while (index < size):
             if (theList[index] > theList[index+1]):
                 temp = theList[index]
                 theList[index] = theList[index+1]
                 theList[index+1] = temp
             index = index + 1
       size = size - 1
       print theList

 

[gneill]

In order to stop as soon as possible you'd need some way to detect that no further sorting needs to be done. For example, if you make it through a complete pass without having to swap any entries then the list must be all in order and you can quit.

 

[mr.me]

Would it be better to have the second loop run under the parameters?

index=0
(while size != index)

Or do I need to create a separate statement of some kind to operate under?

 

[I like Serena]

Can you indent "size = size - 1"?

 

[mr.me]

I indented but it looped twice instead of 3 times, the list sorted was three items [9,8,10]

 

[mr.me]

I got it, I need to indent the index iteration as well so that it is in the if statement. Dumb me

I sometimes forget that the if is in the loop instead of a superimposed rule for the loop,

Thanks for the help everyone.

 

[I like Serena]

Can you adjust the while-condition then?

 

[I like Serena]

I got it, I need to indent the index iteration as well so that it is in the if statement. Dumb me

Uhh... :uhh: Did that work?

 

[mr.me]

I was trying to say that it did I believe it did, at least it only printed the the list once when I ran it with the print in the loop. Is there something else going on that I don't understand?

 

[I like Serena]

Perhaps you should try a couple of longer unsorted lists...

The algorithm of bubble sort "bubbles" through the list one index at a time.
If you only increment the index if you actually swap, you won't properly bubble through the list.

 

[mr.me]

Earlier I was asking how I could adjust the while condition to allow it to stop after the first sort
I don't know what I would adjust it to

 

[I like Serena]

It shouldn't stop after the first sort.

The outer while-loop needs to make one extra iteration.

Hint: now it decrements size to 0 and then stops, without executing for size=0.

 

[mr.me]

Is this correct ?

def bubbleSort (theList):
    size = len(theList) - 1
    while (size > 0):
        index = 0
        while ( index>size ):
            if (theList[index] > theList[index+1]):
                temp = theList[index]
                theList[index] = theList[index+1]
                theList[index+1] = temp
            index = index + 1
        size = size - 1

 

[I like Serena]

Did you try it?

 

[mr.me]

Yes, it works and exists. I fixed an indent on the post that might have made it look wrong

I guess what I was asking is in languages where it is necessary to write a sort like this, is the code stylistically correct.

Again, thanks for all the help.

 

[I like Serena]

Well, you're writing in Python now - the only language where indenting is significant.

Btw, you algorithm still won't work.
You should really try it on some longer unsorted lists...

(You needed to fix the outer-while-loop, not the inner-while-loop.)

 

[mr.me]

I tried it on a longer list, and it's obviously I don't understand what I'm doing, can you show me a correct way to do it, I don't mean to just ask for the answer but I don't understand what the problem is anymore and now I'm more confused

 

[I like Serena]

Well, I think you should try to understand how bubblesort works.
If you do, the program should make more sense.

Perhaps you should take a look at the wiki article:
http://en.wikipedia.org/wiki/Bubble_sort

There's a nifty animation, showing the steps there, right above the following text:

An example on bubble sort. Starting from the beginning of the list,compare every adjacent pair, swap their position if they are not in the right order(the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there is no more element left to be compared.

Note that this text is exactly the algorithm, and it matches 1-to-1 with your program.

 

[mr.me]

I think I got it, half the time the problem I was having was that in my text editor my print statement was set outside the function and always displayed unsorted, I don't know why it copied correctly here, so even when I made (several tries) the first loop while(0<size) it wasn't working

Now I feel like a dummy

 

[I like Serena]

What do you have now then?

 

[mr.me]

It sorted several lists of many elements, correctly

def bubbleSort (theList):
    size = len(theList) - 1
    
    while (0<size): #Corrected the condition for the first while                                      
                           #it is now set to perform from a range of 0 through size
        index=0
        while ( index<size ):
            if (theList[index] > theList[index+1]):
                temp = theList[index]
                theList[index] = theList[index+1]
                theList[index+1] = temp
            index = index + 1       
        size = size - 1

 

[I like Serena]

Hmm, I would assume that it would still sort your initial list the wrong way...
Your correction shouldn't make a difference.
The outer-while-condition is the same even though the arguments are switched around.

That is because you should have "while (size >=0):" instead of "while (size > 0):".

 

[mr.me]

It does seem to work on several tests, however I changed it and noticed no difference

 

[I like Serena]

Well, either way, I'm off to bed now. :zzz: