# Demo entry 6641748

test

Submitted by anonymous on Sep 21, 2017 at 03:08
Language: Python 3. Code size: 10.3 kB.

```import matplotlib.pyplot as plt
from random import *
import time
import copy
import numpy as np
import sys

def InsertionSort(input_list):
for i in range(1,len(input_list)):
key = input_list[i]
j = i-1
while j>=0 and input_list[j]>key:
input_list[j+1] = input_list[j]
j = j-1
input_list[j+1] = key

return input_list

def quickSort(A,lo,hi):
if lo<hi:
p = partition(A,lo,hi)
quickSort(A, lo, p-1)
quickSort(A, p+1, hi)

def partition(A,lo,hi):
pivot = A[hi]
i = lo - 1
for j in range(lo,hi):
if A[j]<pivot:
i = i+1
A[i],A[j]= A[j],A[i]
if A[hi] < A[i + 1]:
A[i+1],A[hi] = A[hi],A[i+1]
return i+1

def MERGE(A,p,q,r):
left = A[p:q+1]
right = A[q+1:r+1]
i = 0
j = 0
left.append(99999)
right.append(99999)
for k in range(p,r+1):
if left[i]<=right[j]:
A[k] = left[i]
i = i+1
else:
A[k] = right[j]
j = j+1

def mergeSort(A,p,r):
if p+1<r:
q = int((p+r)/2)
mergeSort(A,p,q)
mergeSort(A,q+1,r)
MERGE(A,p,q,r)

def random_generator(n):
l =  list(np.random.choice(n, n, replace=True))
with open("/Users/Yuchen/Documents/random.txt", "w") as f:
for s in l:
f.write(str(s) +"\n")
return l

def non_decreasing_generator(n):
nums = list(np.random.choice(n, n, replace=True))
l =  sorted(nums)
with open("/Users/Yuchen/Documents/non_decreasing.txt", "w") as f:
for s in l:
f.write(str(s) +"\n")
return l

def non_increasing_generator(n):
nums = list(np.random.choice(n, n, replace=True))
l =  sorted(nums)[::-1]
with open("/Users/Yuchen/Documents/non_increasing.txt", "w") as f:
for s in l:
f.write(str(s) +"\n")
return l

def random_number_test():

IS_time = [0 for i in range(20)]
QS_time = [0 for i in range(20)]
MS_time = [0 for i in range(20)]
for j in range(10):
x_axis = []

for i in range(20):
n = (i+1)*500
nums1 = []
nums2 = []
nums3 = []
random_generator(n)
with open("/Users/Yuchen/Documents/random.txt", "r") as f:
for line in f:
nums1.append(int(line.strip()))
nums2.append(int(line.strip()))
nums3.append(int(line.strip()))

x_axis.append(n)

start_time = time.clock()
InsertionSort(nums1)
end_time = time.clock()
IS_time[i] = IS_time[i]  + (end_time-start_time)
print('Random: The IS time for size '+str(n)+' for try ' +str(j+1)+' is: '+str(end_time-start_time))

start_time = time.clock()
quickSort(nums2,0,len(nums2)-1)
end_time = time.clock()
QS_time[i] = QS_time[i]  + (end_time-start_time)

print('Random: The QS time for size '+str(n)+' for try ' +str(j+1)+' is: '+str(end_time-start_time))

start_time = time.clock()
mergeSort(nums3,0,len(nums3)-1)
end_time = time.clock()
MS_time[i] = MS_time[i]  + (end_time-start_time)

print('Random: The MS time for size '+str(n)+' for try ' +str(j+1)+' is: '+str(end_time-start_time))

IS_time = [x / 10 for x in IS_time]
QS_time = [x / 10 for x in QS_time]
MS_time = [x / 10 for x in MS_time]

plt.figure(1)

plt.plot(x_axis,IS_time,label = 'Insertion Sort')
plt.plot(x_axis,QS_time,label = 'Quick Sort')
plt.plot(x_axis,MS_time,label = 'Merge Sort')

plt.title('Average running time for random numbers for 10 runs')
plt.xlabel('data size')
plt.ylabel('running time')
plt.savefig('/Users/Yuchen/Documents/Random.png')

plt.figure(2)

plt.plot(x_axis,QS_time,label = 'Quick Sort')
plt.plot(x_axis,MS_time,label = 'Merge Sort')

plt.title('Average running time for random numbers for 10 runs')
plt.xlabel('data size')
plt.ylabel('running time')
plt.savefig('/Users/Yuchen/Documents/Random2.png')

return IS_time,QS_time,MS_time

def nonincreasing_number_test():
IS_time = []
QS_time = []
MS_time = []
x_axis = []
for i in range(1,21):
n = i*500
nums1 = []
nums2 = []
nums3 = []
x_axis.append(n)
(non_increasing_generator(n))
with open("/Users/Yuchen/Documents/non_increasing.txt", "r") as f:
for line in f:
nums1.append(int(line.strip()))
nums2.append(int(line.strip()))
nums3.append(int(line.strip()))

start_time = time.clock()
InsertionSort(nums1)
end_time = time.clock()
IS_time.append(end_time-start_time)
print('Nonincreasing: The IS time for size '+str(n)+' is: '+str(end_time-start_time))

start_time = time.clock()
quickSort(nums2,0,len(nums2)-1)
end_time = time.clock()
QS_time.append(end_time-start_time)
print('Nonincreasing: The QS time for size '+str(n)+' is: '+str(end_time-start_time))

start_time = time.clock()
mergeSort(nums3,0,len(nums3)-1)
end_time = time.clock()
MS_time.append(end_time-start_time)
print('Nonincreasing: The MS time for size '+str(n)+' is: '+str(end_time-start_time))

plt.figure(3)

plt.plot(x_axis,IS_time,label = 'Insertion Sort')
plt.plot(x_axis,QS_time,label = 'Quick Sort')
plt.plot(x_axis,MS_time,label = 'Merge Sort')
plt.title('Running time for nonincreasing numbers')
plt.xlabel('data size')
plt.ylabel('running time')
plt.savefig('/Users/Yuchen/Documents/nonincreasing.png')

plt.figure(4)
plt.plot(x_axis,QS_time,label = 'Quick Sort')
plt.plot(x_axis,MS_time,label = 'Merge Sort')
plt.title('Running time for nonincreasing numbers')
plt.xlabel('data size')
plt.ylabel('running time')
plt.savefig('/Users/Yuchen/Documents/nonincreasing2.png')

return IS_time,QS_time,MS_time

def nondecreasing_number_test():
IS_time = []
QS_time = []
MS_time = []
x_axis = []
for i in range(1,21):
n = i*500
nums1 = []
nums2 = []
nums3 = []
x_axis.append(n)
(non_decreasing_generator(n))
with open("/Users/Yuchen/Documents/non_decreasing.txt", "r") as f:
for line in f:
nums1.append(int(line.strip()))
nums2.append(int(line.strip()))
nums3.append(int(line.strip()))

start_time = time.clock()
InsertionSort(nums1)
end_time = time.clock()
IS_time.append(end_time-start_time)
print('Nonincreasing: The IS time for size '+str(n)+' is: '+str(end_time-start_time))

start_time = time.clock()
quickSort(nums2,0,len(nums2)-1)
end_time = time.clock()
QS_time.append(end_time-start_time)
print('Nonincreasing: The QS time for size '+str(n)+' is: '+str(end_time-start_time))

start_time = time.clock()
mergeSort(nums3,0,len(nums3)-1)
end_time = time.clock()
MS_time.append(end_time-start_time)
print('Nonincreasing: The MS time for size '+str(n)+' is: '+str(end_time-start_time))

plt.figure(5)

plt.plot(x_axis,IS_time,label = 'Insertion Sort')
plt.plot(x_axis,QS_time,label = 'Quick Sort')
plt.plot(x_axis,MS_time,label = 'Merge Sort')
plt.title('Running time for nondecreasing numbers')
plt.xlabel('data size')
plt.ylabel('running time')
plt.savefig('/Users/Yuchen/Documents/nondecreasing.png')

plt.figure(6)
plt.plot(x_axis,QS_time,label = 'Quick Sort')
plt.plot(x_axis,MS_time,label = 'Merge Sort')
plt.title('Running time for nondecreasing numbers')
plt.xlabel('data size')
plt.ylabel('running time')
plt.savefig('/Users/Yuchen/Documents/nondecreasing2.png')

return IS_time,QS_time,MS_time

sys.setrecursionlimit(20000)
rand_IS,rand_QS,rand_MS = random_number_test()
rand = [0 for i in range(len(rand_IS))]
for i in range(len(rand_IS)):
rand[i] = (rand_IS[i],rand_QS[i],rand_MS[i])

with open("/Users/Yuchen/Documents/random_result.txt", "w") as f:
for s in rand:
f.write(str(s) +"\n")

nonde_IS,nonde_QS,nonde_MS = nondecreasing_number_test()
nonde = [0 for i in range(len(nonde_IS))]
for i in range(len(nonde_IS)):
nonde[i] = (nonde_IS[i],nonde_QS[i],nonde_MS[i])

with open("/Users/Yuchen/Documents/nondecreasing_result.txt", "w") as f:
for s in nonde:
f.write(str(s) +"\n")

nonin_IS,nonin_QS,nonin_MS = nonincreasing_number_test()

nonin = [0 for i in range(len(nonin_IS))]
for i in range(len(nonin_IS)):
nonin[i] = (nonin_IS[i],nonin_QS[i],nonin_MS[i])

with open("/Users/Yuchen/Documents/nonincreasing_result.txt", "w") as f:
for s in nonin:
f.write(str(s) +"\n")

```

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.