from __future__ import print_function, division
from typing import List, Union
import numpy as np
import timeit
import random
import matplotlib.pyplot as plt
import seaborn as sns
Number = Union[int, float]
# set matplotlib theme
sns.set()
# generate a random list of n ints ranging from 0 to 1000
random_list = lambda n: [random.randrange(0, 1000, 1) for _ in range(n)]
def mergesort(ll: List[Number]):
"""Sorts list ll according to the mergesort algorithm.
Comparisons are made according to the default "<" and "=" on floats.
>>> a = [7, 3, 2]
>>> mergesort(a)
[2, 3, 7]
>>> a = [10, 1, 7, 4, 0, 8]
>>> mergesort(a)
[0, 1, 4, 7, 8, 10]
>>> a = [3.2, 4.4, 4.3, 1.1]
>>> mergesort(a)
[1.1, 3.2, 4.3, 4.4]
"""
do_sort(ll)
return ll
def do_sort(array: List[Number]):
size = len(array)
if size < 2:
return
mid = size // 2
left = array[:mid]
right = array[mid:size]
do_sort(left)
do_sort(right)
merge(left, right, array)
def merge(left: List[Number], right: List[Number], array: List[Number]):
array_size = len(array)
right_size = len(right)
left_size = len(left)
left_index = right_index = 0
for k in range(array_size):
if right_index == right_size:
array[k:array_size] = left[left_index:left_size]
break
elif left_index == left_size:
array[k:array_size] = right[right_index:right_size]
break
if left[left_index] <= right[right_index]:
array[k] = left[left_index]
left_index += 1
else:
array[k] = right[right_index]
right_index += 1
import doctest
doctest.testmod()
# generate random lists of ints of sizes 10, 100, 1000 and 10,000
list_sizes = [10, 100, 1000, 10000]
lists = [random_list(i) for i in list_sizes]
algo_functions = ['mergesort', 'sorted']
results = {}
for l in lists:
for algo in algo_functions:
lcopy = l[:]
timetaken = timeit.timeit(stmt=f'{algo}(lcopy)', number=100, globals=globals())
results[algo] = results.setdefault(algo, []) + [timetaken] # store value in seconds
data = results.values()
col_headers = [str(s) for s in list_sizes]
row_headers = algo_functions
cells = []
for row in data:
cells.append([f"{x:.6f}" for x in row])
plt.figure(linewidth=2, figsize=(5,1))
table = plt.table(cellText=cells, rowLabels=row_headers, rowLoc='right', colLabels=col_headers, loc='center')
ax = plt.gca()
ax.get_xaxis().set_visible(False)
ax.get_yaxis().set_visible(False)
# Hide axes border
plt.box(on=None)
plt.draw()
plt.rcParams["figure.figsize"] = (10,8)
# correctly label bar chart
def autolabel(rects):
for rect in rects:
height = rect.get_height()
ax.annotate(
"{:.5f}".format(height),
xy=(rect.get_x() + rect.get_width() / 2, height),
xytext=(0, 3), # 3 points vertical offset
textcoords="offset points",
ha="center",
va="bottom",
)
labels = [str(s) for s in list_sizes]
x = np.arange(len(labels))
width = .35
fig, ax = plt.subplots()
rects1 = ax.bar(x - width/2, results.get('mergesort', []), width, label='Mergesort')
rects2 = ax.bar(x + width/2, results.get('sorted', []), width, label='Python Timsort')
ax.set_ylabel('Time taken (seconds)')
ax.set_xlabel('Input size (n)')
ax.set_title('Time taken by both algorithms')
ax.set_xticks(x)
ax.set_xticklabels(labels)
ax.legend()
ax.set_yscale('log')
autolabel(rects1)
autolabel(rects2)
plt.tight_layout()
plt.show()