1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bubble sort doesn't stop as expected

  1. Nov 15, 2011 #1
    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 (Text):

    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
     
     
  2. jcsd
  3. Nov 15, 2011 #2

    gneill

    User Avatar

    Staff: Mentor

    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.
     
  4. Nov 15, 2011 #3
    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?
     
  5. Nov 15, 2011 #4

    I like Serena

    User Avatar
    Homework Helper

    Can you indent "size = size - 1"?
     
  6. Nov 15, 2011 #5
    I indented but it looped twice instead of 3 times, the list sorted was three items [9,8,10]
     
  7. Nov 15, 2011 #6
    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:
     
  8. Nov 15, 2011 #7

    I like Serena

    User Avatar
    Homework Helper

    Can you adjust the while-condition then?
     
  9. Nov 15, 2011 #8

    I like Serena

    User Avatar
    Homework Helper

    Uhh... :uhh: Did that work? :confused:
     
  10. Nov 15, 2011 #9
    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:
     
  11. Nov 15, 2011 #10

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  12. Nov 15, 2011 #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
     
  13. Nov 15, 2011 #12

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  14. Nov 15, 2011 #13
    Is this correct ?

    Code (Text):

    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: Nov 15, 2011
  15. Nov 15, 2011 #14

    I like Serena

    User Avatar
    Homework Helper

    Did you try it?
     
  16. Nov 15, 2011 #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.
     
  17. Nov 15, 2011 #16

    I like Serena

    User Avatar
    Homework Helper

    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.)
     
  18. Nov 15, 2011 #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
     
  19. Nov 15, 2011 #18

    I like Serena

    User Avatar
    Homework Helper

    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:
    Note that this text is exactly the algorithm, and it matches 1-to-1 with your program.
     
  20. Nov 15, 2011 #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:
     
  21. Nov 15, 2011 #20

    I like Serena

    User Avatar
    Homework Helper

    What do you have now then?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Bubble sort doesn't stop as expected
  1. C Bubble sort help (Replies: 8)

  2. Merge sort (Replies: 1)

  3. Bubble-sort algorithm (Replies: 3)

Loading...