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 <st...@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@python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor
>
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
