# 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): for i in range( 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(2500) #Run bubble, insertion, and merge sort on the same list of numbers: #print ourList print("List length is:", len(ourList) ) msList = ourList[:] timeStarted = time.time() print( "mergesort Started!") mResult = mergeSort(msList) timeFinished = time.time() print("mergesort Finished in", timeFinished - timeStarted ,"seconds.\n" ) print("insertion sort Started!") isList = ourList[:] timeStarted = time.time() insertionSort(isList) timeFinished = time.time() print("insertion sort Finished in, ", timeFinished-timeStarted, "seconds.\n") print("bubblesort Started!") bsList = ourList[:] timeStarted = time.time() bubbleSort(bsList) timeFinished = time.time() print("bubblesort Finished in, ", timeFinished-timeStarted, "seconds.\n")