USING PYTHON, Create a program that takes the following codes from the sorting a
ID: 3833140 • Letter: U
Question
USING PYTHON,
Create a program that takes the following codes from the sorting algorithms of bubble sort, selection sort and merge sort and measures the time of each algorithim that it takes to sort 10,000 random integers. If the time, for each algorithim, does not exceed 60 seconds the program with sort again but the number of random integers goes up by 10,000. It will repeat this until it has reached 60 seconds. It should print the time it took to sort and the sorted integers.
Example of what code should be:
Bubble sort will sort 10,000 random integers, if it takes 15 seconds it will continue to sort 20,000 random integers if it took 62 seconds it will stop and selection sort will sort 10,000 random integers, if it takes 7 seconds, selection sort will sort 20,000 random integers, if it took 20 seconds, selection sort will sort 30,000 random integers, if it took 61 seconds selection sort will stop and merge sort will sort 10,000 random integers...etc.
Program output example:
Bubble sort took 15 seconds at 10,000 integers
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 , 19, 20, 21, 22, 23, 24, 25......10,000]
Bubble Sort code:
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)
Selection Sort code:
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)
Merge Sort code:
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)
Explanation / Answer
import time
from random import randint
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 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 getList(count):
list =[]
for i in range(0,count):
list.append(randint(1,count))
return list
def main():
print "========== BUBBLE SORT ============="
total_time=0
numberOfItem = 10000
incrCount = 10000
while(total_time<60):
list = []
list = getList(numberOfItem)
print "Soring "+str(numberOfItem)+" using Bubble Sort [Please wait..........]"
start_time = time.clock()
bubbleSort(list)
total_time = time.clock() - start_time
print "Bubble sort took "+str(total_time)+" seconds at "+str(numberOfItem)+" integers. "
#print list #//Uncomment this lint if you want to priint list it is very big
numberOfItem = numberOfItem +incrCount
print "========== SELECTION SORT ============="
total_time=0
numberOfItem = 10000
incrCount = 10000
while(total_time<60):
list = []
list = getList(numberOfItem)
print "Soring "+str(numberOfItem)+" using Selection Sort [Please wait..........]"
start_time = time.clock()
selectionSort(list)
total_time = time.clock() - start_time
print "Selection Sort took "+str(total_time)+" seconds at "+str(numberOfItem)+" integers. "
#print list #//Uncomment this lint if you want to priint list it is very big
numberOfItem = numberOfItem +incrCount
print "========== MERGE SORT ============="
total_time=0
numberOfItem = 10000
incrCount = 10000
while(total_time<60):
list = []
list = getList(numberOfItem)
print "Soring "+str(numberOfItem)+" using Merge Sort [Please wait..........]"
start_time = time.clock()
selectionSort(list)
total_time = time.clock() - start_time
print "Merge Sort took "+str(total_time)+" seconds at "+str(numberOfItem)+" integers. "
#print list #//Uncomment this lint if you want to priint list it is very big
numberOfItem = numberOfItem +incrCount
main()
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.