Use the timing routine that we discussed in class and do the following: create a driver program that will generate a random list of 100 numbers from, say, 1000 possible values. Save the original list so that you can compare the results of the different sort routines. Print out the original list. Now, using the code from your text for Listings 5.9 (or use 5.10), 5.11, 5.12, 5.14, and 5.15 pass the list to each of these routines and record the amount of time it takes to sort the list. Print out these results (i.e., the time for each). For example, in your driver code you would store the value of the clock, send the list to the bubble sort routine, return and again store the value of the clock, subtract the two values to get the time spent using this sort. You would then repeat this process for each of the sort routines making sure you started with that same unsorted list each time. At the end, you would print out the results, indicating that for a list of 100 randomly generated numbers, bubble sort took .seconds, selection sort took etc.

Timing Routine here:

import time

def sumOfN2(n): start = time.time()

theSum = 0 for i in range(1,n+1): theSum = theSum + i

end = time.time()

return theSum,end-start

listing 5.9:

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

Listing 5.11:

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

listing 5.12:

def insertionSort(alist): for index in range(1,len(alist)):

currentvalue = alist[index] position = index

while position>0 and alist[position-1]>currentvalue: alist[position]=alist[position-1] position = position-1

alist[position]=currentvalue

5.14:

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

while i

while j

5.15:

def quickSort(alist): quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last): if first

splitpoint = partition(alist,first,last)

quickSortHelper(alist,first,splitpoint-1) quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last): pivotvalue = alist[first]

leftmark = first+1 rightmark = last

done = False while not done:

while leftmark <= rightmark and \ alist[leftmark] <= pivotvalue: leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and \ rightmark >= leftmark: rightmark = rightmark -1

if rightmark < leftmark: done = True else: temp = alist[leftmark] alist[leftmark] = alist[rightmark] alist[rightmark] = temp

temp = alist[first] alist[first] = alist[rightmark] alist[rightmark] = temp

return rightmark