# Mergesort vs Bubblesort example in Python # # Jay Summet # CS 1301 # Donated to the public domain: Oct 2008 from random import * ################################################################ ################### Bubble Sort ################################ # # Bubble Sort works by passing through the list of numbers and # swapping any numbers that are not in sorted order. # To guarantee that a list is sorted, this swapping pass must be # repeated N-1 times. # # In this demo, I have separated the swapElements step from # the repetition step into a helper function, but they could just # as easily be combined. # # Because it takes N-1 comparisons to swap elements in the list, # and you do this N-1 times, the time complexity of bubble sort # is (n-1)*(n-1) or, simplifying, O(n^2) # def swapElements(aList): i = 0 while( i < len(aList) - 1 ): if (aList[i] > aList[i+1]): temp = aList[i] aList[i] = aList[i+1] aList[i+1] = temp i = i+1 def bubbleSort(aList): for num in range(len(aList) - 1 ): swapElements(aList) ############################################################### ################# Merge Sort ################################## # # Mergesort works by breaking the original list down into smaller # and smaller sublists (until the sublists are of length 1). # Then, it recursively merges sublists, keeping the resulting lists # in sorted order. # Merging two (already sorted) lists is an order N operation O(N). # # The number of merges performed is essentially Log N, because each # step joins 1/2 of the remaining lists. In reality, the number of # merges is large, but the majority of the merges do well less than N # comparisons, and the big-O time complexity is O(N * Log N). # def merge(left,right): result = [] i = 0 j = 0 while( i < len(left) and j < len(right) ): if(left[i] <= right[j]): result.append(left[i]) i = i+1 else: result.append(right[j]) j = j+1 result = result + left[i:] result = result + right[j:] return result def mergesort(aList): if len(aList) < 2: return(aList) middle = len(aList) / 2 left = mergesort( aList[:middle] ) right = mergesort( aList[middle:] ) return merge(left,right) #Generates a random list of numbers: def randList(N): rList = [] for x in range(N): rList = rList + [ randrange(0,N*2) ] return rList ourList = randList(5000) #Run bubble sort and merge sort on the same list of numbers: #print ourList print "List length is:", len(ourList) print "mergesort Started!" mResult = mergesort(ourList) print "mergesort Finished!" #print mResult print "bubblesort Started!" bubbleSort(ourList) print "bubblesort Finished!" #print ourList