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
    while not found and trial < 10:
        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()