# File: sortTimer.py
# Purpose: Measure the runtime of different sorting algorithms
# 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]

#########################################################
## Merge Sort                                          ##
#########################################################

def merge(list1, list2, list3):
    """
    Merge the two sorted lists list1 and list2 into list3.

    Returns: None (modifies list3)
    """
    # Keep track of current indices into each list
    i1, i2, i3 = 0, 0, 0
    n1, n2 = len(list1), len(list2)

    # Keep merging as long as both list1 and list2 have more items
    while i1 < n1 and i2 < n2:
        if list1[i1] < list2[i2]: # take from list1
            list3[i3] = list1[i1]
            i1 += 1
        else:                     # take from list2
            list3[i3] = list2[i2]
            i2 += 1

        i3 += 1

    # At least one of the lists is empty, so grab the remaining elements
    while i1 < n1:
        list3[i3] = list1[i1]
        i1 += 1
        i3 += 1
        
    while i2 < n2:
        list3[i3] = list2[i2]
        i2 += 1
        i3 += 1

def mergeSort(mylist):
    """
    Sorts the provided list using the Merge Sort algorithm.

    Returns: None (sorts in place)
    """
    n = len(mylist)

    # If the list contains 0 or 1 item, we have no work to do
    if n < 2:
        return

    # First, divide the list into two smaller lists
    mid = n // 2
    left, right = mylist[:mid], mylist[mid:]

    # Next, recursively sort each sublist
    mergeSort(left)
    mergeSort(right)

    # Finally, merge the two sorted sublists back together
    merge(left, right, mylist)

#########################################################
## 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
    time_merge_forward = 0
    time_merge_backward = 0
    time_merge_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)

        # Sort the in-order list using merge sort
        t = time.time()
        mergeSort(sortedData[:]) # sort a copy
        time_merge_forward += (time.time() - t)

        # Sort the reversed list using merge sort
        t = time.time()
        mergeSort(backwardsData[:]) # sort a copy
        time_merge_backward += (time.time() - t)

        # Sort the randomized list using merge sort
        t = time.time()
        mergeSort(randomData[:]) # sort a copy
        time_merge_random += (time.time() - t)

    return {"selection_forward": time_selection_forward,
            "selection_backward": time_selection_backward,
            "selection_random": time_selection_random,
            "merge_forward": time_merge_forward,
            "merge_backward": time_merge_backward,
            "merge_random": time_merge_random}

def timeSort():
    """
    Sorts lists of different sizes using selection sort and merge sort
    and plots the runtimes.
    """
    # Parameters
    nvals = [10, 20, 40, 60, 80, 100, 200, 500, 1000, 2000]
    num_trials = 1000

    # Prep lists to store results
    all_times_selection_forward = []
    all_times_selection_backward = []
    all_times_selection_random = []
    all_times_merge_forward = []
    all_times_merge_backward = []
    all_times_merge_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)
        all_times_merge_forward.append(trial_results["merge_forward"] / num_trials * 1000)
        all_times_merge_backward.append(trial_results["merge_backward"] / num_trials * 1000)
        all_times_merge_random.append(trial_results["merge_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')
    plt.plot(nvals, all_times_merge_backward, label="merge sort - reversed (ms)", marker='o')
    plt.plot(nvals, all_times_merge_random, label="merge sort - randomized (ms)", marker='2')
    plt.plot(nvals, all_times_merge_forward, label="merge sort - in order (ms)", marker='*')

    # 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__":
    timeSort()