# 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