import matplotlib.pyplot as plt
import random
import time

def selectionSort(mylist):
    n = len(mylist)

    # Consider each starting index except the last, as that
    # will be the maximum element in the list by the time
    # we finish with the second-to-last position
    for startIdx in range(n-1):
        # Find the minimum element of those from startIdx
        # to the end of the list
        minIdx = startIdx
        for i in range(startIdx+1, n):
            if mylist[i] < mylist[minIdx]:
                minIdx = i
        
        # Swap to put the minimum element (of those startIdx->end)
        # in position startIdx
        mylist[startIdx], mylist[minIdx] = mylist[minIdx], mylist[startIdx]

def timeSelectionSort():
    nvals = [10, 20, 40, 60, 80, 100, 200, 500, 1000, 2000]
    selectionTimes = []

    for n in nvals:
        print("Working on n:", n)
        
        mylist = list(range(n))

        sstime = 0
        numTests = 1000
        for i in range(numTests):
            random.shuffle(mylist)
        
            t = time.time()

            selectionSort(mylist)

            sstime += (time.time() - t)

        selectionTimes.append(sstime / numTests * 1000)

    plt.figure()
    plt.plot(nvals, selectionTimes, label="Selection Sort Time (ms)")
    plt.xlabel("Number of elements in the list")
    plt.ylabel("Sort time (ms)")
    plt.legend()
    plt.show()

if __name__ == "__main__":
    timeSelectionSort()