Question
why is bubblesortC is more efficient than bubblesort? please give time complexity (Big O) bubblesort: import random import time def bubbleSort(myList): Rearranges the items in
why is bubblesortC is more efficient than bubblesort? please give time complexity (Big O)
bubblesort:
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): # scan the Before sorting 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
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("bubbleSort 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
if __name__ == "__main__": main()
bubbleSortC:
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started