Assignment1Question3

#Question 3

#Mergesort, Threeway Mergesort, Special Threeway Mergesort, and Graphs recording time all below

import random

integer = 5

def random_list(integer):
    lst = []
    for x in range (integer):
        lst.append(random.randint(0, 100))
    return lst

###Mergesort Code###

def merge(left, right):
    array = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            array.append(left[0])
            left.pop(0)
        else:
            array.append(right[0])
            right.pop(0)
    while len(left) > 0:
        array.append(left[0])
        left.pop(0)
    while len(right) > 0:
        array.append(right[0])
        right.pop(0)
    return array
    print array
    
def merge_sort(lst):
    if len(lst) == 1:
        return lst
    else:
        left = lst[0:len(lst)/2]
        right = lst[len(lst)/2:len(lst)]
        left = merge_sort(left)
        right = merge_sort(right)
    return merge(left, right)
    print merge(left, right)

lst = random_list(integer)
print lst
print merge_sort(lst)

###Threeway_Mergesort Code###

def merge_two(left, right):
    array = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            array.append(left[0])
            left.pop(0)
        else:
            array.append(right[0])
            right.pop(0)
    while len(left) > 0:
        array.append(left[0])
        left.pop(0)
    while len(right) > 0:
        array.append(right[0])
        right.pop(0)
    return (array)
    
def merge_three(left, middle, right):
    array = []
    while len(left) > 0 and len(middle) > 0 and len(right) > 0:
        if left[0] <= middle[0] and left[0] <= right[0]:
            array.append(left[0])
            left.pop(0) 
        elif middle[0] <= left[0] and middle[0] <= right[0]:
            array.append(middle[0])
            middle.pop(0)
        elif right[0] <= left[0] and right[0] <= middle[0]:
            array.append(right[0])
            right.pop(0)
    return (array, left, middle, right)
    
def threeway_merge(left, middle, right):
    array = []
    if len(left) > 0 and len(middle) > 0 and len(right) > 0:
        output = merge_three(left, middle, right)
        array = array + output[0]
        left = output[1]
        middle = output[2]
        right = output[3]
        if len(left) == 0:
            array = array + merge_two(middle, right)
        elif len(middle) == 0:
            array = array + merge_two(left, right)
        elif len(right) == 0:
            array = array + merge_two(left, middle)
    elif len(left) == 0:
        array = array + merge_two(middle, right)
    elif len(middle) == 0:
        array = array + merge_two(left, right)
    elif len(right) == 0:
        array = array + merge_two(left, middle)
    return array
        
def threeway_mergesort(lst):
    if len(lst) <= 1:
        return lst
    else:
        left = lst[0:len(lst)//3]
        middle = lst[len(lst)//3:2*len(lst)//3]
        right = lst[2*len(lst)//3:len(lst)]
        left = threeway_mergesort(left)
        middle = threeway_mergesort(middle)
        right = threeway_mergesort(right)
    return (threeway_merge(left, middle, right))

random.seed(5)
    
lst1 = random_list(integer)
print (lst1)
print (threeway_mergesort(lst1))

lst2 = random_list(integer)
print (lst2)
print (threeway_mergesort(lst2))

lst3 = random_list(integer)
print (lst3)
print (threeway_mergesort(lst3))

#[62, 74, 80, 95, 74, 93, 2, 47, 95, 65]
#[2, 47, 62, 65, 74, 74, 80, 93, 95, 95]

#[90, 11, 47, 24, 54, 57, 1, 21, 28, 92]
#[1, 11, 21, 24, 28, 47, 54, 57, 90, 92]

#[77, 16, 80, 14, 62, 12, 0, 88, 21, 21]
#[0, 12, 14, 16, 21, 21, 62, 77, 80, 88]

###Merge-Insertion Code###

def threeway_mergesort2(lst):
    if len(lst) <= 1:
        return lst
    else:
        left = lst[0:len(lst)//3]
        middle = lst[len(lst)//3:2*len(lst)//3]
        right = lst[2*len(lst)//3:len(lst)]
        if len(left) < 3:
            left = insertion_sort(left)
        else:
            left = threeway_mergesort2(left)
        if len(middle) < 3:
            middle = insertion_sort(middle)
        else:
            middle = threeway_mergesort2(middle)
        if len(right) < 3:
            right = insertion_sort(right)
        else:
            right = threeway_mergesort2(right)        
    return (threeway_merge(left, middle, right))

random.seed(6)
    
lst1 = random_list(integer)
print (lst1)
print (threeway_mergesort2(lst1))

lst2 = random_list(integer)
print (lst2)
print (threeway_mergesort2(lst2))

lst3 = random_list(integer)
print (lst3)
print (threeway_mergesort2(lst3))

#[80, 83, 48, 26, 0, 66, 47, 76, 37, 77]
#[0, 26, 37, 47, 48, 66, 76, 77, 80, 83]

#[27, 80, 73, 41, 54, 68, 19, 55, 81, 26]
#[19, 26, 27, 41, 54, 55, 68, 73, 80, 81]

#[81, 69, 85, 33, 9, 80, 81, 44, 9, 19]
#[9, 9, 19, 33, 44, 69, 80, 81, 81, 85]

###Graphs Code###

#Question 3

import matplotlib.pyplot as plt
import time

x = [i for i in range(1, 101)]
y_mergesort = []
y_threeway_mergesort = []
y_threeway_mergesort2 = []

for j in x:
    lst = random_list(j)
    a = time.time()
    threeway_mergesort(lst)
    b = time.time()
    y_mergesort.append(b-a)

for j in x:
    lst = random_list(j)
    a = time.time()
    threeway_mergesort(lst)
    b = time.time()
    y_threeway_mergesort.append(b-a)
    
for j in x:
    lst = random_list(j)
    a = time.time()
    threeway_mergesort2(lst)
    b = time.time()
    y_threeway_mergesort2.append(b-a)

plt.plot(x,y_mergesort, label = "Mergesort Running Time")
plt.xlabel('Length of Array')
plt.ylabel('Running Time')
plt.title("Running Time as a function of Length of Array")
plt.legend()
plt.show()

plt.plot(x,y_threeway_mergesort, label = "Threeway Mergesort Running Time")
plt.xlabel('Length of Array')
plt.ylabel('Running Time')
plt.title("Running Time as a function of Length of Array")
plt.legend()
plt.show()
    
plt.plot(x,y_threeway_mergesort2, label = "Special Threeway Mergesort Running Time")
plt.xlabel('Length of Array')
plt.ylabel('Running Time')
plt.title("Running Time as a function of Length of Array")
plt.legend()
plt.show()