Use the timing routine that we discussed in class and do the following: create a

Question

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<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)

5.15:

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

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

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

Explanation / Answer

#!/usr/bin/env python
# coding=utf-8
import time
import random
from decimal import Decimal

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

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

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

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)

def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
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

if __name__ == '__main__':
_list = random.sample(xrange(1,1000), 100)
_dup_list = _list
print("Original list {}".format(_list))
start_time = time.time()
bubbleSort(_list)
end_time = time.time()
print("Total time taken by Bubble sort is %s " % Decimal(end_time - start_time))
########### Selection Sort ######################
_list = _dup_list
start_time = time.time()
selectionSort(_list)
end_time = time.time()
print("Total time taken by Selection sort is %s " % Decimal(end_time - start_time))
########### Insertion Sort #####################
_list = _dup_list
start_time = time.time()
insertionSort(_list)
end_time = time.time()
print("Total time taken by Insertion sort is %s " % Decimal(end_time - start_time))
########### Merge Sort ########################
_list = _dup_list
start_time = time.time()
mergeSort(_list)
end_time = time.time()
print("Total time taken by Merge sort is %s " % Decimal(end_time - start_time))
########### Quick Sort #######################
_list = _dup_list
start_time = time.time()
quickSort(_list)
end_time = time.time()
print("Total time taken by Quick sort is %s " % Decimal(end_time - start_time))

Here's the demo of it

http://ideone.com/Bqs0Xs

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.