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

import matplotlib.pyplot as plt
import random
import time

#########################################################
## Selection Sort                                      ##
#########################################################

def getMinIndex(mylist, start):
    """
    Finds the position of the minimum element in mylist,
    starting at position start.

    Returns: position (>= start) of minimum element
    """
    # 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):
    """
    Sorts the provided list using the Selection Sort algorithm.

    Returns: None (sorts in place)
    """
    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]

#########################################################
## Run the experiments                                 ##
#########################################################

def runTrials(n, numTrials):
    """
    Times sorting a list of size n over numTrials trials.

    Returns: a dict mapping approach (str) to average runtime (float, in seconds)
    """
    # Create lists that are the regular order and backwards order
    sortedData = list(range(n))
    backwardsData = sortedData[::-1] # reversed

    time_selection_forward = 0
    time_selection_backward = 0
    time_selection_random = 0
    for i in range(numTrials):
        # Create a randomized list to sort
        randomData = sortedData[:] # make a copy before we randomize it
        random.shuffle(randomData)

        # Sort the in-order list using selection sort
        t = time.time()
        selectionSort(sortedData[:]) # sort a copy
        time_selection_forward += (time.time() - t)

        # Sort the reversed list using selection sort
        t = time.time()
        selectionSort(backwardsData[:]) # sort a copy
        time_selection_backward += (time.time() - t)

        # Sort the randomized list using selection sort
        t = time.time()
        selectionSort(randomData[:]) # sort a copy
        time_selection_random += (time.time() - t)

    return {"selection_forward": time_selection_forward,
            "selection_backward": time_selection_backward,
            "selection_random": time_selection_random}

def timeSelectionSort():
    """
    Sorts lists of different sizes using selection sort and plots the runtimes.
    """
    # Parameters
    nvals = [10, 20, 40, 60, 80, 100, 200, 500, 1000, 2000] # takes almost 30 minutes to run with 5000, too
    num_trials = 1000

    # Prep lists to store results
    all_times_selection_forward = []
    all_times_selection_backward = []
    all_times_selection_random = []
    
    # Try all different values of n
    for n in nvals:
        # Get data for this value of n
        print("Working on n:", n)  
        trial_results = runTrials(n, num_trials)

        # Append the average time to the appropriate lists
        all_times_selection_forward.append(trial_results["selection_forward"] / num_trials * 1000)
        all_times_selection_backward.append(trial_results["selection_backward"] / num_trials * 1000)
        all_times_selection_random.append(trial_results["selection_random"] / num_trials * 1000)

    # Make the plot
    plt.figure()
    plt.plot(nvals, all_times_selection_backward, label="selection sort - reversed (ms)", marker='^')
    plt.plot(nvals, all_times_selection_random, label="selection sort - randomized (ms)", marker='s')
    plt.plot(nvals, all_times_selection_forward, label="selection sort - in order (ms)", marker='x')

    # Spiff up our plot
    plt.title("Time to sort as n gets really big")
    plt.xlabel("Number of elements in the list")
    plt.ylabel("Sort time (ms)")
    plt.legend()
    plt.show()

if __name__ == "__main__":
    timeSelectionSort()