## 10-3a) Take n numbers from x to y (all unique) n=1000 x=1 y=1000000
## as given and implement simple naïve Insertion sorting. Sort 
## and print the number of swapping, comparisons, memory used, Time taken.



from time import clock
import sys

## Start
def insertion_sort(Sorted_List):
    memory=0
    swap=0
    comp=0
    for i in range(1, len(Sorted_List)):
        save = int(Sorted_List[i])
        j = i
        while j > 0 and int(Sorted_List[j - 1]) > save:
            Sorted_List[j] = Sorted_List[j - 1]
            j -= 1
            swap+=1
            comp+=1
        Sorted_List[j] = save
    memory= sys.getsizeof(Sorted_List) + sys.getsizeof(save)+ sys.getsizeof(i)+ sys.getsizeof(j)
    return Sorted_List,memory,swap,comp



## End
temp=[]
data=[]

InFile=open("in10_3.txt",'r+')
for row in InFile:
    temp=row.split(',')
    for i in temp:
        data.append(int(i))
InFile.close()
Start=clock()
Insertion_Sort,memory_used,no_swap,no_comp=insertion_sort(data)
Time_Taken=clock()-Start

OutFile=open("out_r3_10_3a.txt","w")
OutFile.write("\n Sorted List Is as Follows :-  \n" )
OutFile.write(str(Insertion_Sort))
OutFile.write("\n\n Time Taken = " + str(Time_Taken) + " Seconds. ")
OutFile.write("\n Memory  Used = " + str(memory_used) + " Bytes. ")

OutFile.close()

print "Output File Generated"