# Programmer: Sriram Pemmaraju
# Date: May 2nd, 2014

import time
import random

# 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

def partition(L, first, last):
    # We pick the element L[first] as the "pivot" around which we partition the list
    p = first

    # We process the rest of the elements, one-by-one, in left-to-right order
    for current in range(p+1, last+1):
        # If L[current] is smaller than the pivot, it needs to move into the first block,
        # to the left of the pivot. 
        if L[current] < L[p]:
            swap(L, current, p+1)
            swap(L, p, p+1)
            p = p + 1

    return p

def generalQuickSort(L, first, last):
    # Base case: if first == last, then there is only one element in the
    # slice that needs sorting. So there is nothing to do.

    # Recursive case: if there are 2 or more elements in the slice L[first:last+1]
    if first < last:
        # Divide step: partition returns an index p such that 
        # first <= p <= last and everthing in L[first:p] is <= L[p]
        # and everything in L[p+1:last+1] is >= L[p]
        p = partition(L, first, last)

        # Conquer step
        generalQuickSort(L, first, p-1)
        generalQuickSort(L, p+1, last)

        # Combine step: there is nothing left to do!

def quickSort(L):
    generalQuickSort(L, 0, len(L)-1)

# main program
# L1 and L2 are copies of the same random list of size 10,000
L1 = [random.random() for i in range(50000)]
L2 = L1[:]

start = time.time()
selectionSort(L1)
print "Selection sort", time.time() - start

start = time.time()
quickSort(L2)
print "quickSort", time.time() - start