# Programmer: Sriram Pemmaraju
# Date: March 2nd, 2013
import random
import time

# Exchanges the elements indexed i and j in list L
def swap(L, i, j):
    temp = L[i]
    L[i] = L[j]
    L[j] = temp

# Finds and returns the index of a smallest element in the range L[lowerBound..len(L)-1]
def minIndex(L, lowerBound):
    minElement = L[lowerBound]
    indexOfMin = lowerBound
    index = lowerBound + 1

    while index < len(L):
        if L[index] < minElement:
            minElement = L[index]
            indexOfMin = index
            
        index = index + 1

    return indexOfMin

# Sorts a list of elements in ascending order by repeatedly selecting
# the minimum element from the rest of the list and bringing it to the front.
# After i iterations of the loop, the first i elements in the list are the smallest
# elements and appear in ascending order. Therefore in iteration i+1 we find a
# smallest element in L[i..len(L)-1] and exchange it with the element in slot i.
def selectionSort(L):
    n = len(L)
    index = 0

    while index < n-1:
        # Finds the index of a smallest element in the range L[index..n-1]
        m = minIndex(L, index)

        # Bring this smallest element to the "front" by swapping L[m] and
        # L[index]
        swap(L, index, m)

        index = index + 1

# This function constructs a random length-n list and computes the amount of
# time it takes to sort the list via selection sort
def timeSelectionSort(n):
    # Construct a random length-n list L
    L = []
    i = 0
    while i < n:
        L.append(random.randint(1, 1000000))
        i = i + 1

    # Time a call to selection sort
    start = time.time()
    selectionSort(L)
    stop = time.time()

    return stop - start


# This function computes the average time to perform selection sort on
# random length-n lists. The average is taken over numRepititions number
# of iterations
def timeManySorts(n, numRepititions):
    
    # Compute the total time it takes for a bunch of calls
    # to do selectionSort on random length-n lists
    totalTime = 0
    repNo = 0
    while repNo < numRepititions:
        totalTime = totalTime + timeSelectionSort(n)
        repNo = repNo + 1

    return totalTime/float(numRepititions)

# main program
n = 1000
while n <= 10000:
    print timeManySorts(n, 100)
    n = n + 1000