• Support PF! Buy your school textbooks, materials and every day products Here!

Bubble sort doesn't stop as expected

  • Thread starter mr.me
  • Start date
  • #1
49
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
 

Answers and Replies

  • #2
gneill
Mentor
20,792
2,770
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.
 
  • #3
49
0
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?
 
  • #4
I like Serena
Homework Helper
6,577
176
Can you indent "size = size - 1"?
 
  • #5
49
0
I indented but it looped twice instead of 3 times, the list sorted was three items [9,8,10]
 
  • #6
49
0
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:
 
  • #7
I like Serena
Homework Helper
6,577
176
Can you adjust the while-condition then?
 
  • #8
I like Serena
Homework Helper
6,577
176
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? :confused:
 
  • #9
49
0
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
I like Serena
Homework Helper
6,577
176
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
49
0
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
I like Serena
Homework Helper
6,577
176
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
49
0
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
I like Serena
Homework Helper
6,577
176
Did you try it?
 
  • #15
49
0
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
I like Serena
Homework Helper
6,577
176
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
49
0
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
I like Serena
Homework Helper
6,577
176
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
49
0
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
I like Serena
Homework Helper
6,577
176
What do you have now then?
 
  • #21
49
0
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
I like Serena
Homework Helper
6,577
176
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
49
0
It does seem to work on several tests, however I changed it and noticed no difference
 
  • #24
I like Serena
Homework Helper
6,577
176
Well, either way, I'm off to bed now. :zzz:
 

Related Threads on Bubble sort doesn't stop as expected

  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
1
Views
8K
Replies
2
Views
531
Replies
3
Views
6K
Replies
12
Views
3K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
1K
Top