import random
import timeit

def selection_sort(arr):
    #choose cell to change
    for k in range(0, len(arr)):
        cur=arr[k]
        j=k+1
        while j< len(arr): #bounds
            if arr[j]<cur:
                cur=arr[j]
                i=j
                 #Change the variables
                extra=arr[k]
                arr[k]=cur
                arr[i]=extra
            j=j+1

def insertion_sort(arr):
    for k in range(1, len(arr)):
        cur=arr[k]
        j=k
      while j>0 and arr[j-1]>cur:
          arr[j]=arr[j-1]
          j=j-1
          arr[j]=cur

if __name__ == '__main__':

    size=[1000, 2500, 5000, 7500, 10000]
    minimum=-1000
    maximum=1000
    for s in size:
        #increasing
        list=[]
        list.append(random.randrange(minimum,maximum+1,1))
        for i in range (1,s):
            range1=list[i-1]
            list.append(random.randrange(range1,maximum+1,1))
        list11=list.copy()

        #decreasing
        list2=[]
        list2.append(random.randrange(minimum,maximum+1,1))
        for j in range (1,s):
            range2=list2[j-1]
            list2.append(random.randrange(minimum,range2+1,1))
        list21=list2.copy()

        #random
        list3=[]
        for k in range(1, s+1):
            list3.append(random.randrange(minimum,maximum+1,1))
        list31=list3.copy()

        selection_sort(list)
        insertion_sort(list11)
        selection_sort(list2)
        insertion_sort(list21)
        selection_sort(list3)
        insertion_sort(list31)

        selection=[list, list2, list3]
        insertion=[list11, list21, list31]
        for a in selection:
            runtime=timeit.timeit('selection_sort(a)', setup='from __main__ import selection_sort, a', number=1)
            print( 'Selection: ' + '{:.6f}'.format(runtime))

        for b in insertion:
            runtime= timeit.timeit('insertion_sort(b)', setup='from __main__ import insertion_sort, b', number=1)
            print('Insertion: ' + '{:.6f}'.format(runtime))