def bubbleSort( A ):
    n = len(A)
    for i in range(n):
        for j in range(1,n-i):
            if A[j-1] > A[j]:
                A[j-1],A[j] = A[j],A[j-1]


def selectionSort( A ):
    n = len(A)
    for i in range(n-1,0,-1):
        maxPos = 0
        for j in range(1,i+1):
            if A[j]>A[maxPos]:
                maxPos=j
        A[maxPos],A[i] = A[i],A[maxPos]


def insertionSort( A ):
    n=len(A)
    for i in range(1,n):
        current = A[i]
        j = i - 1
        while j>=0 and A[j]>current:
            A[j+1]=A[j]
            j = j-1
        A[j+1]=current


import random
from timeit import Timer
original = list(range(3000))
double = list(range(len(original)*2))
random.shuffle(original)
random.shuffle(double)



##Bubble Sort
print("Bubble Sort")
originalCopy = original[:]
doubleCopy = double[:]

t1 = Timer("bubbleSort(originalCopy)", "from __main__ import bubbleSort,originalCopy")
res1 = t1.timeit(number=1)
print(f"bubbleSort(original) : {res1:15.2f} seconds")

t1 = Timer("bubbleSort(doubleCopy)", "from __main__ import bubbleSort,doubleCopy")
res2 = t1.timeit(number=1)
print(f"bubbleSort(double) : {res2:15.2f} seconds")

print("Doubled the data")
print("Time changed by a factor of "+str(res2/res1))
print()


##Selection Sort
print("Selection Sort")
originalCopy = original[:]
doubleCopy = double[:]

t1 = Timer("selectionSort(originalCopy)", "from __main__ import selectionSort,originalCopy")
res1 = t1.timeit(number=1)
print(f"selectionSort(original) : {res1:15.2f} seconds")

t1 = Timer("selectionSort(doubleCopy)", "from __main__ import selectionSort,doubleCopy")
res2 = t1.timeit(number=1)
print(f"selectionSort(double) : {res2:15.2f} seconds")

print("Doubled the data")
print("Time changed by a factor of "+str(res2/res1))
print()


##Insertion Sort
print("Insertion Sort")
originalCopy = original[:]
doubleCopy = double[:]

t1 = Timer("insertionSort(originalCopy)", "from __main__ import insertionSort,originalCopy")
res1 = t1.timeit(number=1)
print(f"insertionSort(original) : {res1:15.2f} seconds")

t1 = Timer("insertionSort(doubleCopy)", "from __main__ import insertionSort,doubleCopy")
res2 = t1.timeit(number=1)
print(f"insertionSort(double) : {res2:15.2f} seconds")

print("Doubled the data")
print("Time changed by a factor of "+str(res2/res1))
print()