Need some help with my python assignment.(ignore tree sort) You are to create a

Question

Need some help with my python assignment.(ignore tree sort)

You are to 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 You are to report the execution times obtained for the algorithms in a table with the following format: Note that since the algorithms have different efficiencies, execution times of over 60 seconds will be reached for different list sizes. Stop running tests for a given algorithm once you For each algorithm, create a line plot showing the list size on the x-axis and the execution time on the y-axis and include a discussion about whether the execution times obtained correspond to the big-O time efficiency of the algorithm.

Explanation / Answer

Hi,

Please find below the code-

# insertion sort
x = [7, 2, 3, 5, 9, 1]

def insertion(list):
for index in range(1,len(list)):
value = list[index]
i = index - 1
while i>=0 and (value < list[i]):
list[i+1] = list[i] # shift number in slot i right to slot i+1
list[i] = value # shift value left into slot i  
i = i - 1

# bubble sort
y = [7, 2, 3, 5, 9, 1]

def bubble(unsorted_list):
length = len(unsorted_list) - 1
sorted = False

while not sorted:
sorted = True
for i in range(length):
if unsorted_list[i] > unsorted_list[i+1]:
sorted = False
unsorted_list[i], unsorted_list[i+1] = unsorted_list[i+1], unsorted_list[i]

z= [54,26,93,17,77,31,44,55,20]
#selection sort
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

#Merge Sort

def merge(arr, p, q, r):
n1 = q - p + 1
n2 = r - q
right, left = [], []
for i in range(n1):
left.append(arr[p + i])
for j in range(n2):
right.append(arr[q + j + 1])
left.append(float('inf'))
right.append(float('inf'))
i = j = 0
for k in range(p, r + 1):
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1

a = [5, 2, 4, 7, 1, 3, 2, 6]
def merge_sort(arr, p, r):
if p < r:
q = (p + r) // 2
merge_sort(arr, p, q)
merge_sort(arr, q + 1, r)
merge(arr, p, q, r)

def test():
start = time.clock()
bubble(y)
elapsed = (time.clock() - start)
print "Time taken for bubble = ", elapsed
start = time.clock()
insertion(x)
elapsed = (time.clock() - start)
print "Time taken for Insertion = ", elapsed
start = time.clock()
selectionSort(z)
elapsed = (time.clock() - start)
print "Time taken for Selection = ", elapsed
start = time.clock()
pp = len(a)
merge_sort(a, 0, pp - 1)
elapsed = (time.clock() - start)
print "Time taken for Merge = ", elapsed

if __name__ == '__main__':
import time
test()

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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