import random
def generateRandomList(n, min = 1, max = 100):
    r = []
    for i in range(n):
        r.append(random.randint(1,100))
    return r

def generateRandomGrid(n):
    r = []
    for i in range(n):
        r.append(generateRandomList(n))
    return r

def searchGrid(grid):
    smallest = grid[0][0]
    for l in grid:
        for e in l:
            if e < smallest:
                smallest = e
    return smallest

def smallestLinSearch(l):
    smallest = l[0]
    for e in l:
        if e < smallest:
            smallest = e
    return smallest

def linSearch(l, target):
    for i in range(len(l)):
        if l[i] == target:
            return i
    return -1

def binSearch(l, target):
    length = len(l)
    c = 1
    i = 1

    while True:
        factor = i/2**c
        index = int(len(l)*factor)
        item = l[index]
        if item == target:
            return index
        elif 2**c >= len(l):
            return -1
        elif item < target:
            c += 1
            i = (i*2) + 1
        elif item > target:
            c += 1
            i = (i*2) - 1

def bubbleSortNums(l):
    done = False
    while not done:
        done = True
        for i in range(len(l) - 1):
            if l[i] > l[i+1]:
                tmp = l[i+1]
                l[i+1] = l[i]
                l[i] = tmp
                done = False
    return l

import timeit

list1 = generateRandomList(1000)
list2 = generateRandomList(2000)
list10 = generateRandomList(10000)

#Time linear search size 1000
before = timeit.default_timer()
smallestLinSearch(list1)
after = timeit.default_timer()
print(f"Linear search on a list of size 1000: {after - before} seconds")

#Time linear search size 2000
before = timeit.default_timer()
smallestLinSearch(list2)
after = timeit.default_timer()
print(f"Linear search on a list of size 2000: {after - before} seconds")

#Time linear search size 10000
before = timeit.default_timer()
smallestLinSearch(list10)
after = timeit.default_timer()
print(f"Linear search on a list of size 10000: {after - before} seconds")

#Time bubble sort size 1000
before = timeit.default_timer()
bubbleSortNums(list1)
after = timeit.default_timer()
print(f"Bubble sort on a list of size 1000: {after - before} seconds")

#Time bubble sort size 2000
before = timeit.default_timer()
bubbleSortNums(list2)
after = timeit.default_timer()
print(f"Bubble sort on a list of size 2000: {after - before} seconds")

#Time bubble sort size 10000
before = timeit.default_timer()
bubbleSortNums(list10)
after = timeit.default_timer()
print(f"Bubble sort on a list of size 10000: {after - before} seconds")