# Merge Sort vs Insertion Sort vs Bubble Sort example in Python
#
# Jay Summet
# CS 1301
# Donated to the public domain: March 2009
from random import *
import time
############################################
## Insertion Sort in Python.
############################################
#
# The insertion sort will start with the 2nd element of the list
# and compare it to the first element. If it is smaller, it will
# slide the first element to the right and insert the smaller element
# at the beginning of the list. Once it's finished with the 2nd element,
# the first two elements in the list are in sorted order, and the rest
# of the list is still unsorted. So it moves on to the 3rd element
# of the list and starts sliding any elements in the sorted part of the
# list to the right until it finds the right spot to place the current
# element. It repeats this until the list is entirely sorted.
#
# Insertion sort is a O(N^2) algorithm, although in reality
# the average case running time is N^2 / 4.
#
def insertionSort(list2):
for i in range(1, len(list2)):
save = list2[i]
j = i
while j > 0 and list2[j - 1] > save:
list2[j] = list2[j - 1]
j = j - 1
list2[j] = save
################################################################
################### 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)
timeStarted = time.time()
print "mergesort Started!"
mResult = mergeSort(ourList)
timeFinished = time.time()
print "mergesort Finished in", timeFinished - timeStarted ,"seconds.\n"
print "insertion sort Started!"
timeStarted = time.time()
insertionSort(ourList)
timeFinished = time.time()
print "insertion sort Finished in, ", timeFinished-timeStarted, "seconds.\n"
print "bubblesort Started!"
timeStarted = time.time()
bubbleSort(ourList)
timeFinished = time.time()
print "bubblesort Finished in, ", timeFinished-timeStarted, "seconds.\n"