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
