'''
Created on Dec 1, 2011

@author: rodger
'''
import random, time, sys

def get_number():
    return random.randint(0,sys.maxint)

def create_list(n):
    return [get_number() for i in xrange(0,n)]

def create_list_reverse(n):
    return [n - num for num in xrange(0,n)]

def create_list_almost_sorted(n):
    L = [num for num in xrange(0,n)]
    L[0], L[len(L)-1] = L[len(L)-1],L[0]
    return L

# Selection Sort from class 12/2/2011
def selectionSort(list):
    
    if len(list)<11:
        print "In Selection Sort .........."
        print list
    index = 0
    for element in list:
        min_index = find_min_index(list, index)
        list[index] = list[min_index]
        list[min_index] = element
        index += 1
        if len(list)<11:
            print list
    return list
    
def find_min_index(list, index):
    min_index= index
    for i, entry in enumerate(list[index:]):
        if entry < list[min_index]:
            min_index = i+index
    return min_index

# Another way to do selection sort 
def selectionSort2(L):
    i = 0
    while i != len(L):
        smallestIndex = find_min_index2(L,i)
        #swap numbers at i and smallestIndex
        temp = L[i]
        L[i] = L[smallestIndex]
        L[smallestIndex] = temp
        i = i+1
        
def find_min_index2(L,startIndex):
    smallestIndex = startIndex
    i = startIndex + 1
    while i != len(L):
        if L[i] < L[smallestIndex]:
            smallestIndex = i
        i = i+1
    return smallestIndex
     

# InsertionSort    
def insertion_sort(L):        
    if len(L)<=10:
        print "In InsertionSort"  
        print L 
    i = 1
    while i != len(L):
        insert(L,i)
        i = i + 1
        if len(L)<=10:
            print L 

def insert(L, b):
    # insert L[b] where it belongs in L[0:b+1]
    # L[0:b-1] must already be in sorted order
    i = b
    while i != 0 and L[i-1] >= L[b]:
        i = i - 1   
    value = L.pop(b)     # remove b from current position
    L.insert(i,value)    # insert value at ith position
    
# bubblesort
def bubblesort(L):
    if len(L) <= 10:
        print "Bubblesort"
        print L  
    for k in range(0,len(L)):
        swapPass(L,k)
        if len(L) <= 10:
            print L
       
def swapPass(L,startIndex):
    for num in range(startIndex+1,len(L)):
        if L[num] < L[num-1]:   # out of order
            temp = L[num]
            L[num] = L[num-1]
            L[num-1] = temp
    
def mergesort(L):
    # make list of 1-item lists
    if len(L)<= 10:
        print "In mergesort"
        print L
    workspace = []
    for i in range(len(L)):
        workspace.append([L[i]])
    i=0
    while i < len(workspace)-1:
        L1 = workspace[i]
        L2 = workspace[i+1]
        newL = merge(L1,L2)
        workspace.append(newL)
        i += 2
        if len(L)<= 10:
            print workspace
        
    # copy results back to L
    if len(workspace) != 0:
        L[:] = workspace[-1][:]
        
def merge(L1, L2):
    newL = []
    i1 = 0
    i2 = 0
    
    while i1 != len(L1) and i2 != len(L2):
        if L1[i1] <= L2[i2]:
            newL.append(L1[i1])
            i1 += 1
        else:
            newL.append(L2[i2]) 
            i2+= 1
    # one list is empty
    if i1 == len(L1):  # list L1 is empty
        newL.extend(L2[i2:])   # put in rest of elements from L2
    else:  # list L2 is empty
        newL.extend(L1[i1:])
    return newL

def mergesort2(list):
    size = len(list)
    if size > 1:
        L1 = mergesort2(list[:size/2])
        L2 = mergesort2(list[size/2:])
        return merge(L1, L2)
    else:
        return list
    

        
                
        
def timingsRandom(name, func):
    print name
    size = 50
    for index in range(0,4):
        size *= 2
        nums = create_list(size)
        start = time.time()
        func(nums)
        end = time.time()
        print "random:size = %d\ttime = %4.3f" % (len(nums), (end-start))
   
def timingsReverse(name, func):
    print name
    size = 50
    for index in range(0,4):
        size *= 2
        nums = create_list_reverse(size)
        start = time.time()
        func(nums)
        end = time.time()
        print "reverse:size = %d\ttime = %4.3f" % (len(nums), (end-start))
 
def timingsAlmostSorted(name, func):
    print name
    size = 50
    for index in range(0,5):
        size *= 2
        nums = create_list_almost_sorted(size)
        start = time.time()
        func(nums)
        end = time.time()
        print "almost sorted:size = %d\ttime = %4.3f" % (len(nums), (end-start))       
             

   
   
L = [8, 6, 5, 9, 3, 2, 1, 4]
selectionSort(L)
L = [8, 6, 5, 9, 3, 2, 1, 4]
selectionSort2(L)
L = [8, 6, 5, 9, 3, 2, 1, 4]
insertion_sort(L) 
L = [8, 6, 5, 9, 3, 2, 1, 4]
bubblesort(L)
L = [8, 6, 5, 9, 3, 2, 1, 4]
mergesort(L)   
print "In mergesort2 recursive"
L = [8, 6, 5, 9, 3, 2, 1, 4]
L = mergesort2(L)
print L
  

print "random ", create_list(12)
print "reverse", create_list_reverse(12)   
print "almost_sorted",  create_list_almost_sorted(12)  

print " "
print "Random Data:"
timingsRandom("Selectionsort",selectionSort)
print " "
timingsRandom("insertion_sort", insertion_sort)
print " "
timingsRandom("bubblesort", bubblesort)
print " "
timingsRandom("mergesort", mergesort)
print " "
timingsRandom("mergesort recursive", mergesort2)

print " "
print "Reverse:"
timingsReverse("Selectionsort",selectionSort)
print " "
timingsReverse("insertion_sort", insertion_sort)
print " "
timingsReverse("bubblesort", bubblesort)
print " "
timingsReverse("mergesort", mergesort)
print " "
timingsReverse("mergesort recursive", mergesort2)

print " "
print "Almost sorted:"
timingsAlmostSorted("Selectionsort",selectionSort)
print " "
timingsAlmostSorted("insertion_sort", insertion_sort)
print " "
timingsAlmostSorted("bubblesort", bubblesort)
print " "
timingsAlmostSorted("mergesort", mergesort)
print " "
timingsReverse("mergesort recursive", mergesort2)