# Programmer: Sriram Pemmaraju
# Date: March 2nd, 2013

# 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