# File: selectionsort.py
# Purpose: Measure the runtime of selection sort.
# Author: Tanya Amert

import matplotlib.pyplot as plt
import random
import time

def getMinIndex(mylist, start):
    # Find the minimum element of those from startIdx
    # to the end of the list
    minIdx = start
    for i in range(start+1, len(mylist)):
        # Is this one smaller?
        if mylist[i] < mylist[minIdx]:
            # If so, update the index we're tracking
            minIdx = i
    return minIdx

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):
        minIdx = getMinIndex(mylist, startIdx)

        # 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()