Write a variation of bubble sort that:

- sorts in descending order (largest to smallest)

- builds the sorted part on the left-hand side of the list

''' Description: Sorts myList in ascending order using a bubble sort. The bubble sort stops early if no items are exchanged when scanning the unsorted part of the list. File: bubbleSortB.py '''

import random import time

def bubbleSort(myList): """Rearranges the items in myList so they are in ascending order""" for lastUnsortedIndex in range(len(myList)-1,0,-1): alreadySorted = True # scan the unsorted part at the beginning of myList for testIndex in range(lastUnsortedIndex): # if we find two adjacent items out of order, switch them if myList[testIndex] > myList[testIndex+1]: temp = myList[testIndex] myList[testIndex] = myList[testIndex+1] myList[testIndex+1] = temp alreadySorted = False if alreadySorted: return

def shuffle(myList): for fromIndex in range(len(myList)): toIndex = random.randint(0,len(myList)-1) temp = myList[fromIndex] myList[fromIndex] = myList[toIndex] myList[toIndex] = temp

def main(): print("bubbleSortB Timings") aList = list(range(10000,0,-1)) print( " Before sorting list: ",end="") print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-1]) start = time.clock() bubbleSort(aList) end = time.clock() print( "sorted list:", end="") print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-1]) print( "Time to sort",end - start,"seconds") print( " Before sorting list: ", end="") print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-1]) start = time.clock() bubbleSort(aList) end = time.clock() print( "sorted list:", end="") print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-1]) print( "Time to sort",end - start,"seconds") aList = list(range(10000,0,-1)) shuffle(aList) print( " Before sorting (random) list: ",end="") print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-1]) start = time.clock() bubbleSort(aList) end = time.clock() print( "sorted list:",end="") print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-1]) print( "Time to sort",end - start,"seconds") aList = list(range(10000,0,-1)) shuffle(aList) print( " Before sorting (random) list: ",end='') print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-1]) start = time.clock() bubbleSort(aList) end = time.clock() print( "sorted list:",end="") print( aList[0],aList[1],aList[2], '...',aList[-3], aList[-2],aList[-1]) print( "Time to sort",end - start,"seconds") input("Hit -key to end")

if __name__ == "__main__": main()