[Tutor] bubble sort function

[Spyros Charonis]

Many thanks for the link as well as for the pseudocode & code. I see what I
did wrong now. Here's the final version that works:


def bubbleSort_ascending(unsorted):

    """ Sorts a list of numbers in ascending order """

    n = len(unsorted)

    count = swaps = 0

    swapped = True

    ## Prompt user to choose if they want to see each sorting step

    option = raw_input("Show sorting steps? (Y/N):\n")

    while swapped:

        count += 1

        swapped = False

        ## Use a tuple assignment in order to swap the value of two
variables

        for i in range(1, n):

            if unsorted[i-1] > unsorted[i]:

                unsorted[i-1], unsorted[i] = unsorted[i], unsorted[i-1]

                swapped = True

        ## Catch user input and either show or hide sorting steps
accordingly

        if option in ("Y", "y"):

            print "\nIteration %d, %d swaps; list: %r\n" %(count, swaps,
unsorted)

        elif option in ("N", "n"):

            pass

        else:

            print "\nYour input was invalid, type either Y/y or N/n"

    return unsorted

On Sun, Nov 16, 2014 at 4:50 AM, Steven D'Aprano <steve at pearwood.info>
wrote:

> On Sat, Nov 15, 2014 at 04:46:26PM +0000, Spyros Charonis wrote:
> > Dear group,
> >
> >
> > I'm having a bit of trouble with understanding why my bubble sort
> > implementation doesn't work. I've got the following function to perform a
> > bubble sort operation on a list of numbers:
>
> It doesn't work because it is completely wrong. Sorry to be harsh, but
> sometimes it is easier to throw broken code away and start again than it
> is to try to diagnose the problems with it.
>
> Let's start with the unoptimized version of bubblesort given by
> Wikipedia:
>
> https://en.wikipedia.org/wiki/Bubble_sort#Implementation
>
> procedure bubbleSort( A : list of sortable items )
>    n = length(A)
>    repeat
>      swapped = false
>      for i = 1 to n-1 inclusive do
>        /* if this pair is out of order */
>        if A[i-1] > A[i] then
>          /* swap them and remember something changed */
>          swap( A[i-1], A[i] )
>          swapped = true
>        end if
>      end for
>    until not swapped
> end procedure
>
>
> Let's translate that to Python:
>
> def bubbleSort(alist):
>     n = len(alist)
>     swapped = True
>     while swapped:
>         swapped = False
>         for i in range (1, n-1):
>             # if this pair is out of order
>             if alist[i-1] > alist[i]:
>                 # swap them and remember something changed
>                 alist[i-1], alist[i] = alist[i], alist[i-1]
>                 swapped = True
>
>
> Let's add something to print the partially sorted list each time we go
> through the loop:
>
>
> def bubbleSort(alist):
>     print("Unsorted: %r" % alist)
>     n = len(alist)
>     swapped = True
>     count = swaps = 0
>     while swapped:
>         count += 1
>         swapped = False
>         for i in range (1, n):
>             # if this pair is out of order
>             if alist[i-1] > alist[i]:
>                 # swap them and remember something changed
>                 swaps += 1
>                 alist[i-1], alist[i] = alist[i], alist[i-1]
>                 swapped = True
>         print("Iteration %d, %d swaps; list: %r" % (count, swaps, alist))
>
>
>
> And now let's try it:
>
> py> mylist = [2, 4, 6, 8, 1, 3, 5, 7, 9, 0]
> py> bubbleSort(mylist)
> Unsorted: [2, 4, 6, 8, 1, 3, 5, 7, 9, 0]
> Iteration 1, 5 swaps; list: [2, 4, 6, 1, 3, 5, 7, 8, 0, 9]
> Iteration 2, 9 swaps; list: [2, 4, 1, 3, 5, 6, 7, 0, 8, 9]
> Iteration 3, 12 swaps; list: [2, 1, 3, 4, 5, 6, 0, 7, 8, 9]
> Iteration 4, 14 swaps; list: [1, 2, 3, 4, 5, 0, 6, 7, 8, 9]
> Iteration 5, 15 swaps; list: [1, 2, 3, 4, 0, 5, 6, 7, 8, 9]
> Iteration 6, 16 swaps; list: [1, 2, 3, 0, 4, 5, 6, 7, 8, 9]
> Iteration 7, 17 swaps; list: [1, 2, 0, 3, 4, 5, 6, 7, 8, 9]
> Iteration 8, 18 swaps; list: [1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
> Iteration 9, 19 swaps; list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
> Iteration 10, 19 swaps; list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>
>
>
> Now you can inspect the working code and compare it to the non-working
> code below and see what is different:
>
>
> > def bubble_sort_ascending(unsorted):
> >       """ Sorts a list of numbers into ascending order """
> >        iterations = 0
> >         size = len(unsorted) - int(1)
> >        for i in range(0, size):
> >             unsorted[i] = float(unsorted[i])
> >             while unsorted[i] > unsorted[i+1]:
> >                   # Use a tuple assignment in order to swap the value of
> > two variables
> >                   unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i]
> >                   iterations += 1
> >                   sorted_vec = unsorted[:] # copy unsorted which is now
> > sorted
> >                   print "\nIterations completed: %s\n" %(iterations)
> >        return sorted_vec
>
>
>
> --
> Steven
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20141116/f025f671/attachment-0001.html>