Create a program that enables you to measure the execution times of various sort

ID: 3834206 • Letter: C

Question

Create a program that enables you to measure the execution times of various sorting algorithms to better understand their efficiency characteristics. For each sorting algorithm, you are to measure and record the execution times for various lists of randomly generated integers. The list sizes used for the test cases should start at 10,000, and go up by 10,000 for each test until the execution time for the test exceeds 60 seconds. The algorithms for which you are to run the tests are: • Selection sort • Bubble sort • Merge sort • Tree sort

Here are the codes for the sorting algorithms.

Selection:

def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location

temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

Bubble:

def bubble_sort(a_list):

def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

Merge sort:

def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]

mergeSort(lefthalf)
mergeSort(righthalf)

i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1

while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1

while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

Tree Sort:

class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def storeInorder(root, inorder):
if root is None:
return
storeInorder(root.left, inorder)
inorder.append(root.data)
storeInorder(root.right, inorder)
def countNodes(root):
if root is None:
return 0
return countNodes(root.left) + countNodes(root.right) + 1
def arrayToBST(arr, root):
if root is None:
return
arrayToBST(arr, root.left)
root.data = arr[0]
arr.pop(0)
arrayToBST(arr, root.right)
def binaryTreeToBST(root):
if root is None:
return
n = countNodes(root)
arr = []
storeInorder(root, arr)
arr.sort()
arrayToBST(arr, root)
def printInorder(root):
if root is None:
return
printInorder(root.left)
print (root.data)
printInorder(root.right)
root = Node(100)
root.left = Node(30)
root.right = Node(105)
root.left.left = Node(220)
root.right.right= Node(25)
binaryTreeToBST(root)
print ("inorder of sorted binary tree : ")
printInorder(root)

Explanation / Answer