'''
Created on Nov 16, 2015

@author: ola
'''
import time,random


def selectsort(data):
    def minindex(first):
        dex = first
        for i in range(first,len(data)):
            if data[i] < data[dex]:
                dex = i           
        return dex

    for i in range(len(data)):
        mindex = minindex(i)
        # swap the elements in index positions i and mindex
        temp = data[mindex]
        data[mindex] = data[i]
        data[i] = temp
    
    return data

def bubblesort(data):
    for j in range(len(data)-1,0,-1):
        for k in range(0,j):
            if data[k] > data[k+1]:
                #   swap the elements in index positions k and k+1
                temp = data[k]
                data[k] = data[k+1]
                data[k+1] = temp
    return data

def timsort(data):
    data = sorted(data)
    return data

def randomword(size):
    alph = 'abcdefghijklmnopqrstuvwxyz'
    chars = [alph[random.randint(0,25)] for dummy in range(size)]
    return ''.join(chars)

def makeList(n):
    ret = [(randomword(12),i) for i in range(n)]
    random.shuffle(ret)
    return ret

def issorted(data):
    for i in range(len(data)-1):
        if data[i] > data[i+1]:
            print i, data[i], data[i+1]
            return False
    return True

def func_name(st):
    st = str(st)
    sp = st.find(' ')
    next = st.find(' ',sp+1)
    return st[sp+1:next]

def timesorts(start,last,inc):
    funcs = [bubblesort,selectsort,timsort]
    print "size\tcreate-time\t",
    for f in funcs:
        print func_name(f),"\t",
    print
    for size in range(start,last+1,inc):
        createstart = time.time()
        data = makeList(size) 
        createend = time.time()
        print "%d\t%3.3f\t" % (size,createend-createstart),
        for func in funcs:
            random.shuffle(data)
            start = time.time()
            data = func(data)
            end = time.time() 
            if (not issorted(data)):
                print "whoops"
            print "\t%3.3f\t" % (end-start),  
        print

if __name__ == '__main__':
    timesorts(1000,10000,1000)