# File: sorting..py
# Description: Solution
# Student: Suliman Sharif
# Student's UT EID: ss59598
# Course Name: CS 313E
# Unique Number: 50595
#
# Date Created: 11/25/2015
# Date Last Modified:11/25/2015

import random
import time
import sys
sys.setrecursionlimit(10000)

def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

def selectionSort(alist):
    for fillslot in range(len(alist)-1,0,-1):
        positionOfMax = 0
        for location in range(1,fillslot+1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp


def insertionSort(alist):
    for index in range(1,len(alist)):
        currentvalue = alist[index]
        position = index

        while position>0 and alist[position-1]>currentvalue:
            alist[position] = alist[position-1]
            position = position-1

        alist[position] = currentvalue

def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:
        for startposition in range(sublistcount):
            gapInsertionSort(alist,startposition,sublistcount)
        sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):
        currentvalue = alist[i]
        position = i

        while position>=gap and alist[position-gap]>currentvalue:
            alist[position] = alist[position-gap]
            position = position - gap

        alist[position] = currentvalue

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i = 0
        j = 0
        k = 0

        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1

        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1

def quickSort(alist):
    quickSortHelper(alist,0,len(alist) - 1)

def quickSortHelper(alist,first,last):
    if first < last:
        splitpoint = partition(alist,first,last)
        quickSortHelper(alist,first,splitpoint-1)
        quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
    pivotvalue = alist[first]
    leftmark = first + 1
    rightmark = last
    done = False

    while not done:

        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1

        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark -= 1

        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp

    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp

def runFunction(function, number, listSize):

    average = 0
    for i in range(number):
        average += function(listSize)

    average = average / number

    return average

############################################

def listNumberSort(n):

    randomList = []
    for i in range(0, n):
        randomList.append(i)

    random.shuffle(randomList)
    bubbleTime = bubbleSortTime(randomList)

    return bubbleTime

def listSortedSort(n):

    sortedList = []
    for i in range(0, n):
        sortedList.append(i)

    bubbleTime = bubbleSortTime(sortedList)

    return bubbleTime

def listReversedSort(n):

    reversedList = []
    for i in range(0, n):
        reversedList.append(i)

    reversedList.reverse()
    bubbleTime = bubbleSortTime(reversedList)

    return bubbleTime

def bubbleSortTime(List):

    startTime = time.perf_counter()
    bubbleSort(List)
    endTime = time.perf_counter()
    elapsedTime = endTime - startTime

    return elapsedTime

###########################################

def listNumberSelection(n):

    randomList = []
    for i in range(0, n):
        randomList.append(i)

    random.shuffle(randomList)
    selectionTime = selectionSortTime(randomList)

    return selectionTime

def listSortedSelection(n):

    sortedList = []
    for i in range(0, n):
        sortedList.append(i)

    selectionTime = selectionSortTime(sortedList)

    return selectionTime

def listReversedSelection(n):

    reversedList = []
    for i in range(0, n):
        reversedList.append(i)

    reversedList.reverse()
    selectionTime = selectionSortTime(reversedList)

    return selectionTime

def selectionSortTime(List):

    startTime = time.perf_counter()
    selectionSort(List)
    endTime = time.perf_counter()
    elapsedTime = endTime - startTime

    return elapsedTime

##########################################

def listNumberInsertion(n):

    randomList = []
    for i in range(0, n):
        randomList.append(i)

    random.shuffle(randomList)
    insertionTime = insertionSortTime(randomList)

    return insertionTime


def listSortedInsertion(n):

    sortedList = []
    for i in range(0, n):
        sortedList.append(i)

    insertionTime = insertionSortTime(sortedList)

    return insertionTime

def listReversedInsertion(n):

    reversedList = []
    for i in range(0, n):
        reversedList.append(i)

    reversedList.reverse()
    insertionTime = insertionSortTime(reversedList)

    return insertionTime

def insertionSortTime(List):

    startTime = time.perf_counter()
    insertionSort(List)
    endTime = time.perf_counter()
    elapsedTime = endTime - startTime

    return elapsedTime

############################################

def listNumberShell(n):

    randomList = []
    for i in range(0, n):
        randomList.append(i)

    random.shuffle(randomList)
    shellTime = shellSortTime(randomList)

    return shellTime


def listSortedShell(n):

    sortedList = []
    for i in range(0, n):
        sortedList.append(i)

    shellTime = shellSortTime(sortedList)

    return shellTime

def listReversedShell(n):

    reversedList = []
    for i in range(0, n):
        reversedList.append(i)

    reversedList.reverse()
    shellTime = shellSortTime(reversedList)

    return shellTime

def shellSortTime(List):

    startTime = time.perf_counter()
    shellSort(List)
    endTime = time.perf_counter()
    elapsedTime = endTime - startTime

    return elapsedTime

############################################

def listNumberMerge(n):

    randomList = []
    for i in range(0, n):
        randomList.append(i)

    random.shuffle(randomList)
    mergeTime = mergeSortTime(randomList)

    return mergeTime


def listSortedMerge(n):

    sortedList = []
    for i in range(0, n):
        sortedList.append(i)

    mergeTime = mergeSortTime(sortedList)

    return mergeTime

def listReversedMerge(n):

    reversedList = []
    for i in range(0, n):
        reversedList.append(i)

    reversedList.reverse()
    mergeTime = mergeSortTime(reversedList)

    return mergeTime

def mergeSortTime(List):

    startTime = time.perf_counter()
    mergeSort(List)
    endTime = time.perf_counter()
    elapsedTime = endTime - startTime

    return elapsedTime

###############################################

def listNumberQuick(n):

    randomList = []
    for i in range(0, n):
        randomList.append(i)

    random.shuffle(randomList)
    quickTime = quickSortTime(randomList)

    return quickTime

def listSortedQuick(n):

    sortedList = []
    for i in range(0, n):
        sortedList.append(i)

    quickTime = quickSortTime(sortedList)

    return quickTime

def listReversedQuick(n):

    reversedList = []
    for i in range(0, n):
        reversedList.append(i)

    reversedList.reverse()
    quickTime = quickSortTime(reversedList)

    return quickTime

def quickSortTime(List):

    startTime = time.perf_counter()
    quickSort(List)
    endTime = time.perf_counter()
    elapsedTime = endTime - startTime

    return elapsedTime

################################################

def main():

    randomAverageBubble = runFunction(listNumberSort, 5, 10)
    randomAverageBubble100 = runFunction(listNumberSort, 5, 100)
    randomAverageBubble1000 = runFunction(listNumberSort, 5, 1000)
    randomAverageSelection = runFunction(listNumberSelection, 5, 10)
    randomAverageSelection100 = runFunction(listNumberSelection, 5, 100)
    randomAverageSelection1000 = runFunction(listNumberSelection, 5, 1000)
    randomAverageInsertion = runFunction(listNumberInsertion, 5, 10)
    randomAverageInsertion100 = runFunction(listNumberInsertion, 5, 100)
    randomAverageInsertion1000 = runFunction(listNumberInsertion, 5, 1000)
    randomAverageShell = runFunction(listNumberShell, 5, 10)
    randomAverageShell100 = runFunction(listNumberShell, 5, 100)
    randomAverageShell1000 = runFunction(listNumberShell, 5, 1000)
    randomAverageMerge = runFunction(listNumberMerge, 5, 10)
    randomAverageMerge100 = runFunction(listNumberMerge, 5, 100)
    randomAverageMerge1000 = runFunction(listNumberMerge, 5, 1000)
#    randomAverageQuick = runFunction(listNumberQuick, 5, 10)
#    randomAverageQuick100 = runFunction(listNumberQuick, 5, 100)
#    randomAverageQuick1000 = runFunction(listNumberQuick, 5, 1000)

    print ("Input type = Random")
    print ("                      avg time    avg time    avg time")
    print ("    Sorting function   (n=10)      (n=100)    (n=1000)")
    print ("----------------------------------------------------------")
    print ("       bubbleSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(randomAverageBubble, randomAverageBubble100, randomAverageBubble1000))
    print ("      SelectionSort   {0:0.6f}    {1:0.6f}    {2:0.6f}".format(randomAverageSelection, randomAverageSelection100, randomAverageSelection1000))
    print ("      InsertionSort   {0:0.6f}    {1:0.6f}    {2:0.6f}".format(randomAverageInsertion, randomAverageInsertion100, randomAverageInsertion1000))
    print ("        ShellSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(randomAverageShell, randomAverageShell100, randomAverageShell1000))
    print ("        MergeSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(randomAverageMerge, randomAverageMerge100, randomAverageMerge1000))
#    print ("        QuickSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(randomAverageQuick, randomAverageQuick100, randomAverageQuick1000))

    print ("\n")
    sortedAverageBubble = runFunction(listSortedSort, 5, 10)
    sortedAverageBubble100 = runFunction(listSortedSort, 5, 100)
    sortedAverageBubble1000 = runFunction(listSortedSort, 5, 1000)
    sortedAverageSelection = runFunction(listSortedSelection, 5, 10)
    sortedAverageSelection100 = runFunction(listSortedSelection, 5, 100)
    sortedAverageSelection1000 = runFunction(listSortedSelection, 5, 1000)
    sortedAverageInsertion = runFunction(listSortedInsertion, 5, 10)
    sortedAverageInsertion100 = runFunction(listSortedInsertion, 5, 100)
    sortedAverageInsertion1000 = runFunction(listSortedInsertion, 5, 1000)
    sortedAverageShell = runFunction(listSortedShell, 5, 10)
    sortedAverageShell100 = runFunction(listSortedShell, 5, 100)
    sortedAverageShell1000 = runFunction(listSortedShell, 5, 1000)
    sortedAverageMerge = runFunction(listSortedMerge, 5, 10)
    sortedAverageMerge100 = runFunction(listSortedMerge, 5, 100)
    sortedAverageMerge1000 = runFunction(listSortedMerge, 5, 1000)
#    sortedAverageQuick = runFunction(listSortedQuick, 5, 10)
#    sortedAverageQuick100 = runFunction(listSortedQuick, 5, 100)
#    sortedAverageQuick1000 = runFunction(listSortedQuick, 5, 1000)

    print ("Input type = Sorted")
    print ("                      avg time    avg time    avg time")
    print ("    Sorting function   (n=10)      (n=100)    (n=1000)")
    print ("----------------------------------------------------------")
    print ("       bubbleSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(sortedAverageBubble, sortedAverageBubble100, sortedAverageBubble1000))
    print ("      SelectionSort   {0:0.6f}    {1:0.6f}    {2:0.6f}".format(sortedAverageSelection, sortedAverageSelection100, sortedAverageSelection1000))
    print ("      InsertionSort   {0:0.6f}    {1:0.6f}    {2:0.6f}".format(sortedAverageInsertion, sortedAverageInsertion100, sortedAverageInsertion1000))
    print ("        ShellSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(sortedAverageShell, sortedAverageShell100, sortedAverageShell1000))
    print ("        MergeSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(sortedAverageMerge, sortedAverageMerge100, sortedAverageMerge1000))
#    print ("        QuickSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(sortedAverageQuick, sortedAverageQuick100, sortedAverageQuick1000))

    print ("\n")
    reversedAverageBubble = runFunction(listReversedSort, 5, 10)
    reversedAverageBubble100 = runFunction(listReversedSort, 5, 100)
    reversedAverageBubble1000 = runFunction(listReversedSort, 5, 1000)
    reversedAverageSelection = runFunction(listReversedSelection, 5, 10)
    reversedAverageSelection100 = runFunction(listReversedSelection, 5, 100)
    reversedAverageSelection1000 = runFunction(listReversedSelection, 5, 1000)
    reversedAverageInsertion = runFunction(listReversedInsertion, 5, 10)
    reversedAverageInsertion100 = runFunction(listReversedInsertion, 5, 100)
    reversedAverageInsertion1000 = runFunction(listReversedInsertion, 5, 1000)
    reversedAverageShell = runFunction(listReversedShell, 5, 10)
    reversedAverageShell100 = runFunction(listReversedShell, 5, 100)
    reversedAverageShell1000 = runFunction(listReversedShell, 5, 1000)
    reversedAverageMerge = runFunction(listReversedMerge, 5, 10)
    reversedAverageMerge100 = runFunction(listReversedMerge, 5, 100)
    reversedAverageMerge1000 = runFunction(listReversedMerge, 5, 1000)
#    reversedAverageQuick = runFunction(listReversedQuick, 5, 10)
#    reversedAverageQuick100 = runFunction(listReversedQuick, 5, 100)
#    reversedAverageQuick1000 = runFunction(listReversedQuick, 5, 1000)

    print ("Input type = Reversed")
    print ("                      avg time    avg time    avg time")
    print ("    Sorting function   (n=10)      (n=100)    (n=1000)")
    print ("----------------------------------------------------------")
    print ("       bubbleSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(reversedAverageBubble, reversedAverageBubble100, reversedAverageBubble1000))
    print ("      SelectionSort   {0:0.6f}    {1:0.6f}    {2:0.6f}".format(reversedAverageSelection, reversedAverageSelection100, reversedAverageSelection1000))
    print ("      InsertionSort   {0:0.6f}    {1:0.6f}    {2:0.6f}".format(reversedAverageInsertion, reversedAverageInsertion100, reversedAverageInsertion1000))
    print ("        ShellSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(reversedAverageShell, reversedAverageShell100, reversedAverageShell1000))
    print ("        MergeSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(reversedAverageMerge, reversedAverageMerge100, reversedAverageMerge1000))
#    print ("        QuickSort     {0:0.6f}    {1:0.6f}    {2:0.6f}".format(reversedAverageQuick, reversedAverageQuick100, reversedAverageQuick1000))



main()