Bubble sort doesn't stop as expected

  • Thread starter Thread starter mr.me
  • Start date Start date
  • Tags Tags
    Bubble Sort
AI Thread Summary
The discussion revolves around issues with a Python implementation of the bubble sort algorithm, specifically why it doesn't stop as expected. Participants highlight the need for a mechanism to detect when no swaps are made, indicating the list is sorted. The outer while-loop's condition is debated, with suggestions to adjust it for proper functionality. Indentation errors are also discussed, emphasizing their significance in Python. Ultimately, the corrected code appears to work for various test cases, though some confusion remains regarding the algorithm's mechanics.
mr.me
Messages
49
Reaction score
0
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?

Code:
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
 
Physics news on Phys.org
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.
 
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?
 
Can you indent "size = size - 1"?
 
I indented but it looped twice instead of 3 times, the list sorted was three items [9,8,10]
 
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. :biggrin:
 
Can you adjust the while-condition then?
 
mr.me said:
I got it, I need to indent the index iteration as well so that it is in the if statement. Dumb me

Uhh... :rolleyes: Did that work? :confused:
 
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?
:confused:
 
  • #10
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.
 
  • #11
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
 
  • #12
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.
 
  • #13
Is this correct ?

Code:
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
 
Last edited:
  • #14
Did you try it?
 
  • #15
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.
 
  • #16
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.)
 
  • #17
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
 
  • #18
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:
wikipedia said:
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.
 
  • #19
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

:blushing:
 
  • #20
What do you have now then?
 
  • #21
It sorted several lists of many elements, correctly


Code:
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
 
  • #22
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):".
 
  • #23
It does seem to work on several tests, however I changed it and noticed no difference
 
  • #24
Well, either way, I'm off to bed now. :zzz:
 

Similar threads

Replies
10
Views
2K
Replies
7
Views
2K
Replies
9
Views
3K
Replies
75
Views
6K
Replies
1
Views
1K
Replies
1
Views
2K
Replies
36
Views
4K
Back
Top