[Tutor] bubble sort function

[Steven D'Aprano]

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