SharedCS110 Session 5.1.ipynbOpen in CoCalc
from random import shuffle

def worst_sort(L):
while not is_sorted(L):
shuffle(L)
return L

def is_sorted(L):
for i in range(len(L)-1):
if L[i] > L[i + 1]:
return False
return True

A = [5,3,1,2,4,6]
print (worst_sort(A))

[1, 2, 3, 4, 5, 6]
import math
import random
import numpy as np
from matplotlib import pyplot as plt

def find_median(L, delta):
lower_bound = 50-(delta/0.02)
upper_bound = 50+(delta/0.02)
found = False
trial = 0
num = random.choice(L)
smaller = 0
for i in L:
if i < num:
smaller += 1
if lower_bound - smaller <=0 and upper_bound - smaller >= 0:
found = True
trial += 1
if found == False:
return "Fail"
else:
return num

# L = [x for x in range(100)]
# print (find_median(L,0.02))

#########################################
interval = [0.1,0.2,0.3,0.4,0.5]
input_size = np.linspace(10,100,10)
num_trial = 100

#generate a nested list with lists of different input_size
def generate_test():
test = []
for i in input_size:
test.append(sorted(random.sample(range(1, 200), int(i))))
return test

#Run the simulation on all input_sizes with parameter interval_size
#Repeat each simulation num_trials number times

def simulation(input_size,num_trial,interval_size):
graph = []
for i in generate_test():
trial = 0
failure = 0
while trial < num_trial:
if find_median(i,interval_size) == "Fail":
failure += 1
trial += 1
graph.append(float(failure)/num_trial)
return graph

#loop through all interval sizes
for i in interval:
results = simulation(input_size, num_trial, i)
plt.plot(input_size, results, label="Interval = {}".format(i))

plt.title("The Effect of Input Size and Interval on Failure")
plt.xlabel("Input size (n)")
plt.ylabel("Probability of failure (%)")
plt.legend()
plt.show()