#------ IMPORTS ----------------------
from random import randint
from timeit import timeit
import matplotlib.pyplot as plt
import numpy as np
#------------------------------------
#     Bubble Sort
#------------------------------------
def bubblesort(alist):
    swapped = True
    iterations = 0
    list_len = len(alist)
    while (swapped == True):
        swapped = False
        iterations += 1
        for ii in range(1,list_len):
            if alist[ii-1] > alist[ii]:
                temp = alist[ii-1]
                alist[ii-1] = alist[ii]
                alist[ii] = temp
                swapped = True
    return alist
#-----------------------------------
#  Merge Sort
#-----------------------------------
def merge(list_a, list_b):
    list_sorted = []
    while list_a != [] and list_b != []:
        if list_a[0] < list_b[0]:
            list_sorted.append(list_a.pop(0))
        else:
            list_sorted.append(list_b.pop(0))
    if len(list_a) < 1:
        list_sorted += list_b
    else:
        list_sorted += list_a
    return list_sorted

def mergesort(unsorted):
    if len(unsorted) <= 1:
        return unsorted
    else:
        middle = int(len(unsorted) / 2)
        front = mergesort(unsorted[:middle])
        back = mergesort(unsorted[middle:])
    return merge(front, back)

def dosorts(alist, blist, mlist,tlist):
    alist1 = alist[:]
    alist2 = alist[:]
    bs = lambda: bubblesort(alist)
    ms = lambda: mergesort(alist1)
    ts = lambda: sorted(alist2)
    #time the functions for num_iterations each
    tbs = timeit(bs, number = num_iterations)
    tms = timeit(ms, number = num_iterations)
    tim = timeit(ts, number = num_iterations)
    blist.append(tbs)
    mlist.append(tms)
    tlist.append(tim)
    return blist, mlist, tlist
#----------------------------------
#  Testing
#----------------------------------
np.random.seed(555)
#Generate a large (1000 items) random list
max_int = 10000
#num_in_list = 100

y=[]      #y Shared axes values Num Point in List
xmran=[]  #x Merge sort time values Random List
xbran=[]  #x Bubble sort time values Random list
xtran=[]  #x Timsort sort time values Random list
xmsrt=[]  #x Merge sort time values Sorted List
xbsrt=[]  #x Bubble sort time values Sorted list
xtsrt=[]  #x TimSort sort time values Sorted list
xmrev=[]  #x Merged sort time, reversed list
xbrev=[]  #x Bubble sort time, reversed list
xtrev=[]  #x Timsort sort time, reversed list
xmams=[]  #x Merge sort time values First and Last Items swapped
xbams=[]  #x Bubble sort time values First and Last Items swapped
xtams=[]  #x Timsort sort time values First and Last Items swapped
num_iterations = 10
#for ii in range(80):
for ii in range(1, 3000,100):
    print("Run : " + str(ii-1))
    #num_points = ii*10 +  1
    #y.append(num_points)
    y.append(ii)
    list_to_sort = [randint(0,max_int) for i in range(ii)]
    #list_to_sort = [randint(0,max_int) for i in range(num_points)]
    sortedlist = mergesort(list_to_sort)
    almostsorted = sortedlist[:]
    usl = len(almostsorted)
    tmp = almostsorted[0];
    almostsorted[0] = almostsorted[usl-1]
    almostsorted[usl-1] = tmp

    xbran, xmran, xtran = dosorts(list_to_sort, xbran, xmran, xtran)   #random list
    xbsrt, xmsrt, xtsrt = dosorts(sortedlist, xbsrt, xmsrt, xtsrt)     #sorted list
    sortedlist.reverse()
    xbrev, xmrev, xtrev = dosorts(sortedlist, xbrev, xmrev, xtrev)     #reversed list
    xbams, xmams, xtams = dosorts(almostsorted, xbams, xmams, xtams)   #almost sorted list
#Plot  List Data
plt.style.use('seaborn-whitegrid')
fig1, (ax1, ax2, ax3,ax4) = plt.subplots(1,4 , sharey=True)
ax1.plot(xbran, y, "gD-", label='bubble')
ax1.plot(xmran, y, 'ro-', label='merge')
ax1.plot(xtran, y, 'b+-', label='timsort')
ax1.legend(loc='lower right')
ax1.set(xlabel='time (sec?) ' + str(num_iterations) + ' Iterations', ylabel='Length of list (number of points)',
       title='Random List')
ax2.plot(xbams, y, "gD-", label='bubble')
ax2.plot(xmams, y, 'ro-', label='merge')
ax2.plot(xtams, y, 'b+-', label='timsort')
ax2.legend(loc='lower right')
ax2.set(xlabel='time (sec?) ' + str(num_iterations) + ' Iterations', ylabel='Length of list (number of points)',
       title='Almost Sorted List')
ax3.plot(xbrev, y, "gD-", label='bubble')
ax3.plot(xmrev, y, 'ro-', label='merge')
ax3.plot(xtrev, y, 'b+-', label='timsort')
ax3.legend(loc='lower right')
ax3.set(xlabel='time (sec?) ' + str(num_iterations) + ' Iterations', ylabel='Length of list (number of points)',
       title='Reversed Sorted List')
ax4.plot(xbsrt, y, "gD-", label='bubble')
ax4.plot(xmsrt, y, 'ro-', label='merge')
ax4.plot(xtsrt, y, 'b+-', label='timsort')
ax4.legend(loc='lower right')
ax4.set(xlabel='time (sec?) ' + str(num_iterations) + ' Iterations', ylabel='Length of list (number of points)',
       title='Sorted List')
fig1.set_size_inches(9.5, 8.5)
fig1.show()