Week1_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 1 - measuring complexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This week:\n",
    "\n",
    "1. Try to launch this notebook with the Binder link at https://github.com/claresloggett/comp90014_workshops\n",
    "2. Explore JupyterLab (your tutor will demo). \n",
    "3. Check that you are able to log into your account at https://comp90014.eng.unimelb.edu.au/\n",
    "4. Try the empirical complexity exercises below\n",
    "\n",
    "If you are very new to programming (or just want a Python primer), you may want to just read through the below and instead try the exercises at http://claresloggett.github.io/python_workshops/hammingdist.html and http://claresloggett.github.io/python_workshops/kmer_counting.html ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exploring JupyterLab "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can find a User Guide with a description of features at http://jupyterlab.readthedocs.io\n",
    "\n",
    "The main interface we'll be using is the Jupyter Notebook interface. If you prefer to run just Jupyter Notebook itself instead of Jupyter Lab, that is fine. \n",
    "\n",
    "Some useful hotkeys are:\n",
    "\n",
    "* Shift-Enter : execute the code in the current cell\n",
    "* Enter : edit the current cell\n",
    "* ESC : stop editing a cell and return to \"command mode\" to use other hotkeys\n",
    "* m : Turn the current cell into a Markdown cell\n",
    "* y : Turn the current cell into a code cell\n",
    "* a : add a new cell above\n",
    "* b : add a new cell below\n",
    "* dd : delete the current cell\n",
    "* c : copy the current cell\n",
    "* v : paste the copied cell(s)\n",
    "\n",
    "You can also execute the command `?` or `help()` to get help on any function. For instance, `sorted?` or `help(sorted)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imports "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Get matplotlib plots to appear inline in the notebook\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sort_utilities import time_sort, completely_sorted_list, nearly_sorted_list, random_list, reversed_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Measuring complexity "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Insertion sort "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an implementation of insertion sort, discussed in lectures.\n",
    "\n",
    "This implementation sorts the list in-place, so the original list will also be modified."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isort(items):\n",
    "    \"\"\"\n",
    "    Sort a list in-place using insertion sort\n",
    "    \"\"\"\n",
    "    for index in range(1, len(items)):\n",
    "        next_item = items[index]\n",
    "        while index >= 1 and (next_item < items[index - 1]):\n",
    "            items[index] = items[index - 1]\n",
    "            index -= 1\n",
    "        items[index] = next_item\n",
    "    return items"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've imported some functions that create lists with different properties (you can see these in `sort_utilities.py`). Execute the following code cells:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5, 9, 4, 6, 2, 0, 8, 7, 1]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_list(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 4, 5, 3, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nearly_sorted_list(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reversed_list(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "completely_sorted_list(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test the performance of insertion sort using Jupyter's `%timeit` magic. We'll make the list outside the timed cell, as we don't want to time the creation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "items = random_list(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.78 µs ± 2.88 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit isort(items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a bigger list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "items = random_list(1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "159 µs ± 1.06 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit isort(items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've also imported a `time_sort()` function that you can use to time a sort function once you've written it, and get the result. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f66a78d9b00>]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZAAAAD8CAYAAABZ/vJZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xl8VPW9//HXhwBhNeyCgUCAsAQXxLAILrgCai9eV7QqVSzWqq0/e7XQxWvt7a120Wq19qJQl6qAqFdqtaiAdUGWIIisJiQhBBASwh4IWT6/P+bQm6YBhhAymZn38/HIg3O+8z3f+X6HybxzzvfMOebuiIiIHKtGke6AiIhEJwWIiIjUigJERERqRQEiIiK1ogAREZFaUYCIiEitKEBERKRWwgoQMxttZuvMLNvMJtXweKKZzQgeX2RmPao8NjkoX2dmo4KyZma22My+MLNVZvazKvVTgzaygjabHv8wRUSkrh01QMwsAXgaGAOkAzeYWXq1ahOAHe7eG3gceDTYNh0YBwwARgN/CNorBS509zOAgcBoMxsWtPUo8Li7pwE7grZFRKSBaRxGnSFAtrvnAJjZdGAssLpKnbHAQ8HyLOApM7OgfLq7lwK5ZpYNDHH3z4C9Qf0mwY8H21wI3Bg89kLQ7jNH6mCHDh28R48eYQxFREQOWbp0aZG7d6zt9uEESDKwscp6ATD0cHXcvdzMdgHtg/KF1bZNhn/s2SwFegNPu/siM+sA7HT38ur1qzOzicBEgJSUFDIzM8MYioiIHGJmG45n+3DmQKyGsuoX0DpcncNu6+4V7j4Q6AoMMbNTw3wugu2nuHuGu2d07FjrABURkVoKJ0AKgG5V1rsCmw9Xx8waA0lAcTjbuvtO4ENCcyRFQJugjcM9l4iINADhBMgSIC04O6opoUnx2dXqzAbGB8vXAPM8dJnf2cC44CytVCANWGxmHc2sDYCZNQcuBtYG28wP2iBo863aD09ERE6Uo86BBHMadwNzgARgmruvMrOHgUx3nw1MBV4KJsmLCYUMQb2ZhCbcy4G73L3CzLoALwTzII2Ame7+dvCUPwSmm9l/AcuCtkVEpIGxWLgfSEZGhmsSXUTk2JjZUnfPqO32+ia6iIjUigJERERqRQEiIhKFNhaX8PO3V7OrpCxifQjni4QiItJALN+4k2c/yuHdlVtIaGSc3bM9F6efHJG+KEBERBq4ykpn7tptPPtRDovzimndrDETz+vFt4b3oHNSs4j1SwEiItJAHSir4I3PN/HcxznkFO0juU1zfnpFOtcP7karxMh/fEe+ByIi8k+K9x3kpc828OJneWzfd5DTkpN48oYzuezUzjROaDhT1woQEZEGIrdoH1M/yWHW0gIOlFVyUb9OfPu8ngxNbUfoYuUNiwJERCTC3J0fvbmS6UvyadKoEVcNSub2c1Pp3al1pLt2RAoQEZEIe3/1Vl5dnM+NQ1O49+I0OrWO3MT4sVCAiIhEUGl5Bb94Zw1pnVrx8L8NaFBzHEcTPT0VEYlBLyzIY8P2En56RXpUhQcoQEREIqZobym/n5vNhf06cV6f6LsxngJERCRCfvveV+wvq+DHl/ePdFdqRQEiIhIBqzfvZsaSfG45uwe9OraKdHdqRQEiIlLP3J2fv72apOZN+P5FaZHuTq0pQERE6tl7q7fyWc527rukD0ktmkS6O7WmABERqUel5RX89ztr6HNyK24YkhLp7hwXBYiISD16/tPoPW23uujuvYhIFCncU8rv52VzUb9OnJsWfaftVqcAERGpJ4+9v44DUXzabnUKEBGRerBq8y6mL9nI+OE96Bmlp+1WpwARETnB3J2H/7KaNs2b8L0Lo/e03eoUICIiJ9icVV+zKLeY+y7tG9Wn7VanABEROYEOXW2378mtuWFwt0h3p06FFSBmNtrM1plZtplNquHxRDObETy+yMx6VHlsclC+zsxGBWXdzGy+ma0xs1Vm9v0q9R8ys01mtjz4uez4hykiEhnTPsljY/F+fnJF/6g/bbe6o94PxMwSgKeBS4ACYImZzXb31VWqTQB2uHtvMxsHPApcb2bpwDhgAHAK8IGZ9QHKgR+4++dm1hpYambvV2nzcXf/TV0NUkQkErbtOcDT87O5uH9snLZbXThxOATIdvccdz8ITAfGVqszFnghWJ4FXGShG/iOBaa7e6m75wLZwBB33+LunwO4+x5gDZB8/MMREWk4HnvvK0rLK/jx5emR7soJEU6AJAMbq6wX8K8f9v+o4+7lwC6gfTjbBoe7zgQWVSm+28xWmNk0M2sbRh9FRBqUlZt2MSNzI+PP7kFqh5aR7s4JEU6AWA1lHmadI25rZq2A14F73X13UPwM0AsYCGwBfltjp8wmmlmmmWUWFhYeeQQiIvXo0NV227Zoyj1RfLXdowknQAqAqqcOdAU2H66OmTUGkoDiI21rZk0IhcfL7v7GoQruvtXdK9y9EniW0CG0f+HuU9w9w90zOnaMvWOLIhKd3J2XFm4InbZ7SR+SmsfOabvVhRMgS4A0M0s1s6aEJsVnV6szGxgfLF8DzHN3D8rHBWdppQJpwOJgfmQqsMbdH6vakJl1qbL678DKYx2UiEgkfJ6/g6ufWcCDb61icI+2jIux03arO+pZWO5ebmZ3A3OABGCau68ys4eBTHefTSgMXjKzbEJ7HuOCbVeZ2UxgNaEzr+5y9wozOwe4GfjSzJYHT/Ujd38H+JWZDSR0qCsPuKMOxysiUuc2Fpfw6N/W8vaKLXRsncijV5/GNWd1I6FRTUfxY4eFdhSiW0ZGhmdmZka6GyISZ3YfKOPp+dn86dM8GhlMPLcnd5zfi5aJR/3bvEEws6XunlHb7aNjlCIiDUh5RSWvLs7n8Q+y2FFykKvO7Mp/jOpDl6Tmke5avVKAiIiEyd2Zv24bv/jrGtYX7mNYz3b85PJ0Tk1OinTXIkIBIiIShtWbd/OLd1bzafZ2enZoybO3ZHBx/06EzgmKTwoQEZEjKDlYzs9mr2bm0o0kNW/CQ99I55vDutMkxq5rVRsKEBGRI3jk3bXMXLqR289J5e4L0mLqcuzHSwEiInIYn63fzoufbeC2Eakxez2r46F9MBGRGpQcLOeB17+ge/sW3D+qb6S70yBpD0REpAa/+ts6CnbsZ8bEs2neNCHS3WmQtAciIlLNwpztPL8gj/Fn92BIartId6fBUoCIiFRRcrCcH76+gpR2LXhgtA5dHYkOYYmIVPHrOevYsL2E6ROH0aKpPiKPRHsgIiKBxbnFwaGr7gzr2T7S3WnwFCAiIsD+gxU8MOsLurZtzgOj+0W6O1FB+2ciIsBv3ltH3vYSXvn20Ki5mm6kaQ9EROJeZl4x0z7N5eZh3Rneq0OkuxM1FCAiEtcOlFVw/6wVJLdpzqQxOnR1LLSfJiJx7bfvrSO3aB+v3K5DV8dKeyAiEreWbijmuU9y+ebQFIb31qGrY6UAEZG4dOjQ1SlJzZl8Wf9IdycqaX9NROLS4+9/RU7hPv48YSitdOiqVrQHIiJx5/P8HTz7cQ43DEnhnDQduqotBYiIxJUDZRXc/9oXdD6pGT+6TGddHQ/tt4lI3KiodB7921rWF+7jxduG0LqZ7i54PBQgIhLzDpRV8PrnBUz5KIcN20u4cWgK5/XpGOluRT0FiIjErN0Hyvjzwg1M+ySPor2lnNGtDZPH9OPS9M6R7lpMUICISMzZtvsAUz/N5eWF+ewtLee8Ph35zvk9Obtne8ws0t2LGWEFiJmNBp4AEoDn3P2Rao8nAi8CZwHbgevdPS94bDIwAagAvufuc8ysW1C/M1AJTHH3J4L67YAZQA8gD7jO3Xcc1yhFJC7kFu1jykfreX3pJsorK7n89FO447yenJqcFOmuxaSjBoiZJQBPA5cABcASM5vt7qurVJsA7HD33mY2DngUuN7M0oFxwADgFOADM+sDlAM/cPfPzaw1sNTM3g/anATMdfdHzGxSsP7DOhuxiMScFQU7+ePf1/Puyq9pktCIazO6MvG8nnRv3zLSXYtp4eyBDAGy3T0HwMymA2OBqgEyFngoWJ4FPGWh/cSxwHR3LwVyzSwbGOLunwFbANx9j5mtAZKDNscCI4O2XgA+RAEiIjVYvXk3v3hnNZ9mb6d1s8bceX4vbh2RSsfWiZHuWlwIJ0CSgY1V1guAoYer4+7lZrYLaB+UL6y2bXLVDc2sB3AmsCgoOtndD4XLFjPrVFOnzGwiMBEgJSUljGGISCwp3neQb/1pMRWVzuQx/bhxaIpOy61n4QRITTNOHmadI25rZq2A14F73X13GH35v0bcpwBTADIyMqr3R0RimLvzwKwv2FlSxhvfHa45jggJ55voBUC3Kutdgc2Hq2NmjYEkoPhI25pZE0Lh8bK7v1GlzlYz6xLU6QJsC3cwIhIfXvxsAx+s2cakMf0UHhEUToAsAdLMLNXMmhKaFJ9drc5sYHywfA0wz909KB9nZolmlgqkAYuD+ZGpwBp3f+wIbY0H3jrWQYlI7FqzZTe/eGcNF/brxK0jekS6O3HtqIewgjmNu4E5hE7jnebuq8zsYSDT3WcTCoOXgknyYkIhQ1BvJqHJ8XLgLnevMLNzgJuBL81sefBUP3L3d4BHgJlmNgHIB66tywGLSPTaf7CCe15dRlLzJvz6mtP1nY4Is9COQnTLyMjwzMzMSHdDRE6wyW98yfQl+bx021BdRbcOmNlSd8+o7fa6Gq+IRIV3vtzCq4vzueO8XgqPBkIBIiIN3qad+5n0+grO6JrEDy7tE+nuSEABIiINWnlFJfdOX0alw5M3nEmTBH1sNRS6mKKINGhPzc9mSd4Ofnf9QF2apIFRlItIg7U4t5gn52Zx1aBkrjwz+egbSL1SgIhIg7SrpIx7py8jpV0LHh57aqS7IzXQISwRaXDcnUlvrGDbnlLe+O5wWiXqo6oh0h6IiDQ4ry7eyLsrv+aB0X05vWubSHdHDkMBIiINStbWPTz89irOTevA7ef0jHR35AgUICLSYBwoC12qpGXTxvz2ujNo1EiXKmnIdGBRRBqMX76zhrVf7+FPtw6mU+tmke6OHIUCREQibmNxCU/Ny2ZG5kZuPyeVC/rWeB85aWAUICISMZt27uepedm8lrmRRo2MW0f04P7RfSPdLQmTAkRE6t2WXfv5w/z1TF+Sj2HcODSF747sTeckHbaKJgoQEak3W3cf4JkP1/PK4nzcnWszunHXBb1JbtM80l2TWlCAiMgJt23PAf74YQ4vL9pAeaVz7VldueuC3nRr1yLSXZPjoAARkROmaG8pUz7K4cXP8iircK46M5l7Lkwjpb2CIxYoQESkzrk7v/sgiykf5VBaXsGVA5O556I0UjvoarqxRAEiInXudx9k8cTcLC4/rQv3XdqHXh1bRbpLcgIoQESkTr21fBNPzM3i6kFd+c21p2Omb5PHKl3KRETqzNINxdz/2gqGpLbjl1edpvCIcQoQEakTG4tLmPjiUk5p04z/ueksmjbWx0us0/+wiBy33QfKuO35JZRVVDL1W4Np27JppLsk9UBzICJyXMorKrnr5c/JLdrHixOGaMI8jihARKTW3J2H/rKKj7OKePTq0xjeq0OkuyT1KKxDWGY22szWmVm2mU2q4fFEM5sRPL7IzHpUeWxyUL7OzEZVKZ9mZtvMbGW1th4ys01mtjz4uaz2wxORE+n5BXn8eWE+d5zXk+sHp0S6O1LPjhogZpYAPA2MAdKBG8wsvVq1CcAOd+8NPA48GmybDowDBgCjgT8E7QE8H5TV5HF3Hxj8vHNsQxKR+jBv7VZ+/vZqLk0/mR+O7hfp7kgEhLMHMgTIdvccdz8ITAfGVqszFnghWJ4FXGSh8/fGAtPdvdTdc4HsoD3c/SOguA7GICL1bM2W3dzzyjLSTzmJ340bqDsHxqlwAiQZ2FhlvSAoq7GOu5cDu4D2YW5bk7vNbEVwmKttGPVFpJ5s23OACc8voVWzxjx3y2BaNNVUarwKJ0Bq+tPCw6wTzrbVPQP0AgYCW4Df1tgps4lmlmlmmYWFhUdpUkTqwoGyCr794lJ2lJQxdfxg3b8jzoUTIAVAtyrrXYHNh6tjZo2BJEKHp8LZ9p+4+1Z3r3D3SuBZgkNeNdSb4u4Z7p7RsWPHMIYhIsejstL5wcwvWFGwkyfGDeTU5KRId0kiLJwAWQKkmVmqmTUlNCk+u1qd2cD4YPkaYJ67e1A+LjhLKxVIAxYf6cnMrEuV1X8HVh6urojUn8fe/4q/frmFyWP6cemAzpHujjQARz146e7lZnY3MAdIAKa5+yozexjIdPfZwFTgJTPLJrTnMS7YdpWZzQRWA+XAXe5eAWBmrwIjgQ5mVgD8p7tPBX5lZgMJHerKA+6oywGLyLE5UFbBtE9zeWp+NuMGd+Pb5/aMdJekgbDQjkJ0y8jI8MzMzEh3QySm7DlQxp8X5jP1kxyK9h7k4v6deOams2iSoCsgxQozW+ruGbXdXqdPiMg/2b63lOcX5PH8gjz2HCjn3LQO3HVBb4amttPVdeWfKEBEBIDNO/fz7Mc5vLo4n9LySkYP6Mx3R/bmtK6aLJeaKUBE4lxO4V7++Pf1vLlsE+4wdmAyd47sSe9OrSPdNWngFCAicWrV5l384cP1vPPlFpomNOLGISl8+7yedG3bItJdkyihABGJM5t27ucnb37J/HWFtEpszHfO78VtI1Lp2Dox0l2TKKMAEYkj23Yf4MZnF1K89yD3j+rLTcO6k9S8SaS7JVFKASISJ4r3HeSmqYso3FPKn28fyqAUXWZOjo8CRCQO7DlQxvhpi8nbXsLz3xqs8JA6oW8EicS4/QcrmPB8Jmu27OaZbw5ieG/dNVDqhgJEJIaVllcw8aVMMjcU8/j1A7mo/8mR7pLEEB3CEolR5RWVfO/VZXycVcSvrj6db5xxSqS7JDFGeyAiMaiy0rl/1grmrNrKf34jnesGdzv6RiLHSAEiEmPcnZ++tZI3l23iPy7tw60jUiPdJYlRChCRGOLuPPLuWl5elM93zu/FXRf0jnSXJIYpQERiyO/nZfM/H+Vwy9nd+eHovrp6rpxQChCRGDH1k1wee/8rrh7UlYe+MUDhISecAkQkBkxfnM/P317NmFM78+jVp9GokcJDTjwFiEiUe2v5Jia/+SXn9+nIE+POpLHuGCj1RN8DEYlSX2zcyZNzs5i7dhtDUtvxx5vOomljhYfUHwWISJRZlr+DJ+Zm8eG6QpKaN+EHl/RhwrmpNG+aEOmuSZxRgIhEiaUbivndB1l8nFVE2xZNuH9UX245uzutm+ly7BIZChCRBm5xbjFPzP2KT7O3075lUyaN6cfNw7rTMlG/vhJZegeKNEDuzsKcUHAszCmmQ6tEfnJ5f24cmkKLpvq1lYZB70SRBsTdWbB+O098kMXivGI6tU7kwSvSuWFIiuY4pMFRgIg0EPtKy/n+9OV8sGYrnU9qxs/+bQDXD+5GsyYKDmmYwjrnz8xGm9k6M8s2s0k1PJ5oZjOCxxeZWY8qj00OyteZ2agq5dPMbJuZrazWVjsze9/MsoJ/des0iXmFe0q54dmFzFu7lR9d1o8P7x/J+OE9FB7SoB01QMwsAXgaGAOkAzeYWXq1ahOAHe7eG3gceDTYNh0YBwwARgN/CNoDeD4oq24SMNfd04C5wbpIzMot2sfVzywga+tenr0lg4nn9VJwSFQIZw9kCJDt7jnufhCYDoytVmcs8EKwPAu4yEIX4hkLTHf3UnfPBbKD9nD3j4DiGp6valsvAFcew3hEosqy/B1c/cwC9paW8+rEYbpjoESVcAIkGdhYZb0gKKuxjruXA7uA9mFuW93J7r4laGsL0CmMPopEnfdXb+WGZxfSullj3rhzOAO7tYl0l0SOSTgBUtNV2TzMOuFsWytmNtHMMs0ss7CwsC6aFKk3Ly/awB0vZdL35Na8fudwenRoGekuiRyzcAKkAKh6P8yuwObD1TGzxkASocNT4Wxb3VYz6xK01QXYVlMld5/i7hnuntGxY8cwhiESee7Ob+as48dvrmRk3068OnEYHVolRrpbIrUSToAsAdLMLNXMmhKaFJ9drc5sYHywfA0wz909KB8XnKWVCqQBi4/yfFXbGg+8FUYfRRq8sopK/uO1FTw1P5sbhnRjys1n6UuBEtWO+u5193IzuxuYAyQA09x9lZk9DGS6+2xgKvCSmWUT2vMYF2y7ysxmAquBcuAud68AMLNXgZFABzMrAP7T3acCjwAzzWwCkA9cW6cjFomAvaXl3PnnpXycVcR9l/Thngt764ZPEvUstKMQ3TIyMjwzMzPS3RCp0bbdB7j1+SWs/XoPv7zqNK7L6Hb0jUTqgZktdfeM2m6v/WeREyh7217GT1vMjpKDTB2fwci+OqlQYocCROQEKC2v4K1lm/nvd9fQuJExY+LZnNY1KdLdEqlTChCROrSz5CAvL8rn+QV5FO4p5dTkk/jDjWeR0r5FpLsmUucUICJ1IH97CdM+zWXGko3sL6vgvD4defy6nozo3V6T5RKzFCAix2FZ/g6e+ziXd1duIaGRMXZgMrefm0q/zidFumsiJ5wCROQYVVY6H6zZyrMf57AkbwetmzXmjvN78a3hPTj5pGaR7p5IvVGAiITpQFkFr39ewNSPc8kp2kdym+Y8eEU61w3uRivdXlbikN71ImH4OKuQ+2Z+QeGeUk5LTuL3N5zJmFM70zghrFvqiMQkBYjIEVRUOk/MzeL387JI69SKJ8edybCe7TQxLoICROSwCveUcu+MZXyavZ2rB3Xl51cO0LWrRKrQb4NIDRbmbOeeV5exe38Zv7r6dK4brMuPiFSnABGporLSeebv6/nte+vo3r4lL942hP5ddEquSE0UICKBHfsO8v9mLufDdYVccXoXfnnVabRu1iTS3RJpsBQgIsDSDTu455XPKdp7kJ+PHcBNw7prolzkKBQgEtfcnamf5PLIu2vp0qYZr985XBc9FAmTAkTi1q79ZTww6wvmrNrKpekn8+trzyCpuQ5ZiYRLASJxaemGYu6dsZwtOw/wk8v7M+GcVB2yEjlGChCJG4euYfXcJ7kszi2mS1IzZtxxNmd1bxvprolEJQWIxLySg+W8vrSAqZ/kkre9hOQ2zfnJ5f25fnA3nWUlchwUIBKztu4+wAsL8nh5UT679pdxRrc2PDWqL6MH6BpWInVBASIxZ9XmXUz9OJe/rNhMRaUzakBnbj83lUEpbTXPIVKHFCASEyornQ+/2sZzH+eyYP12WjRN4JtDu3PbiFTdTlbkBFGASFRzd/628mt+89461hfuo0tSMyaP6ce4ISk6JVfkBFOASNTK317Cg7NX8uG6Qvp1bs0T4wZy2WldaKL5DZF6oQCRqFNaXsGUv+fw1PxsmiQ04sEr0rnl7O6aGBepZwoQiSqfZhfx07dWklO4j8tP78JPL0+nc5LuQy4SCWH9yWZmo81snZllm9mkGh5PNLMZweOLzKxHlccmB+XrzGzU0do0s+fNLNfMlgc/A49viBILtu05wPenL+Obzy2iotJ54bYhPH3jIIWHSAQddQ/EzBKAp4FLgAJgiZnNdvfVVapNAHa4e28zGwc8ClxvZunAOGAAcArwgZn1CbY5Upv3u/usOhifRLmKSuflRRv49Zx1lJZV8r2L0vjuyF40a5IQ6a6JxL1wDmENAbLdPQfAzKYDY4GqATIWeChYngU8ZaET7scC0929FMg1s+ygPcJoU+LcioKd/PjNlXy5aRfn9O7Aw2MH0LNjq0h3S0QC4QRIMrCxynoBMPRwddy93Mx2Ae2D8oXVtk0Olo/U5i/M7EFgLjApCCCJE7v2l/Hb99bx0sINdGiVyJM3nMk3Tu+iLwGKNDDhBEhNv7UeZp3Dldc093KozcnA10BTYArwQ+Dhf+mU2URgIkBKSkpN/ZYos2nnfqYvzueVRfnsKDnILcO684NRfTlJ16sSaZDCCZACoFuV9a7A5sPUKTCzxkASUHyUbWssd/ctQVmpmf0J+I+aOuXuUwgFDBkZGdUDTaJERaXzUVYhLy/cwLy123BgZJ+O3HdJX93YSaSBCydAlgBpZpYKbCI0KX5jtTqzgfHAZ8A1wDx3dzObDbxiZo8RmkRPAxYT2jOpsU0z6+LuW4I5lCuBlcc5RmmAivaWMjNzI68syqdgx346tGrKnSN7MW5wCt3a6dIjItHgqAESzGncDcwBEoBp7r7KzB4GMt19NjAVeCmYJC8mFAgE9WYSmhwvB+5y9wqAmtoMnvJlM+tIKGSWA9+pu+FKJLk7i3OL+fOifP62cgtlFc6wnu2YNKYfl6Z3pmljfRFQJJqYe/Qf/cnIyPDMzMxId0MOY9f+Mt78vICXF+WTtW0vrZs15pqzuvLNoSn07tQ60t0TiVtmttTdM2q7vb6JLifMxuISnvn7et78fBP7yyo4o2sSv7rmdL5x+ik0b6rvcYhEOwWI1Lncon08PT+bN5dtIsGMfz8zmZuGddekuEiMUYBIncnauoen5mfzly820yShEbec3Z07zuuly42IxCgFiBy3NVt289S8bN5ZuYVmjRO4/dye3H5uKp1aKzhEYpkCRGrty4JdPDkvi/dXb6VVYmO+O7IXE87pSbuWTSPdNRGpBwoQOWaf5+/g93OzmL+ukJOaNeb7F6Vx24hUklroG+Mi8UQBImE5WF7JR18V8sJneXycVUTbFk24f1Rfbj67uy41IhKnFCByWO7O0g07eHPZJv765RZ2lpTRoVUik8f046Zh3WmZqLePSDzTJ4D8i6yte/jf5Zt4a/lmCnbsp1mTRlya3pkrzzyFc9M66p7jIgIoQCSwdfcBZi/fzP8u38SqzbtpZHBOWkfuu6QPlw7oTCvtbYhINfpUiGO7D5Txt5Vf89byTSxYvx13OKNrEg9ekc4VZ3TRabgickQKkDhTWel8ur6I1zILmLPqa0rLK+nevgX3XJjGlQNP0R3/RCRsCpA4kb+9hFlLNzJraQGbdx0gqXkTrsvoxlWDkhnYrY3u9icix0wBEsNKDpbzzpdf81rmRhblFmMG56Z15EeX9+fi/ifTrIkuaCgitacAiTHuTuaGHbyWuZG/rtjCvoNkXG5bAAAJHUlEQVQV9GjfgvtH9eWqQcl0SWoe6S6KSIxQgMSIzTv38+ayTcxaWkBu0T5aNk3g8tO7cG1GNzK6t9UhKhGpcwqQKFVZ6azcvIsP1mxj7pqtrNq8G4Chqe2464LejDm1s77oJyInlD5hosj+gxV8kl3EvLVbmbtmG9v2lNLI4KzubZk0ph9jTu1M9/YtI91NEYkTCpAG7utdB5gbBMan2UWUllfSKrEx5/fpyEX9OzGybydd/VZEIkIB0sCUV1SyYtMu/r6ukLlrt7JyU+jQVLd2zblhSAoX9z+ZIantaNpYlxMRkchSgESYu/PV1r18ml3EgvVFLMopZk9pOY0MBqW05YHRfbm4/8mkdWqliXARaVAUIBGwsbiEBeuL+DR7OwvWb6dobykA3du34IozTmFE7/YM79VBh6ZEpEFTgNSD7XtLWbB++z9CI7+4BICOrRMZ0bs9I3p1YHjv9nRt2yLCPRURCZ8CpI65O/nFJSzJ20FmXjFL8opZX7gPgNaJjRnasz23jujBiN4ddFhKRKKaAuQ4lVdUsnrL7n8ERuaGHRTuCR2SOqlZYzJ6tOOqQV0Z3qs9pyUn0Vj30hCRGBFWgJjZaOAJIAF4zt0fqfZ4IvAicBawHbje3fOCxyYDE4AK4HvuPudIbZpZKjAdaAd8Dtzs7gePb5h1Z8+BMpZv3Elm3g4yNxSzLH8nJQcrAOjatjnn9O7AWd3bMrhHO9I6taJRI+1hiEhsOmqAmFkC8DRwCVAALDGz2e6+ukq1CcAOd+9tZuOAR4HrzSwdGAcMAE4BPjCzPsE2h2vzUeBxd59uZn8M2n6mLgZ7LMorKsnbXsK6r/ew9uvdrNmyh3Vbd7OxeD8AjQz6dT6Ja8/qSkaPdmT0aKvrTIlIXAlnD2QIkO3uOQBmNh0YC1QNkLHAQ8HyLOApCx3cHwtMd/dSINfMsoP2qKlNM1sDXAjcGNR5IWj3hAZI0d5S1m4JBcXaIDCytu6ltLwSCIVFaoeWnN61Dded1Y3Tu7XhzJQ2nNSsyYnslohIgxZOgCQDG6usFwBDD1fH3cvNbBfQPihfWG3b5GC5pjbbAzvdvbyG+nXuiQ+yeGlhHkV7/+8IWYdWifTv0pqbh3WnX5eT6Ne5Nb07tdKlz0VEqgknQGo6iO9h1jlceU0zyUeq/6+dMpsITARISUmpqcpRdU5K5IK+nf4RFH07t6ZDq8RatSUiEm/CCZACoFuV9a7A5sPUKTCzxkASUHyUbWsqLwLamFnjYC+kpucCwN2nAFMAMjIyagyZo7l+cArXD65d+IiIxLtwzildAqSZWaqZNSU0KT67Wp3ZwPhg+Rpgnrt7UD7OzBKDs6vSgMWHazPYZn7QBkGbb9V+eCIicqIcdQ8kmNO4G5hD6JTbae6+ysweBjLdfTYwFXgpmCQvJhQIBPVmEppwLwfucvcKgJraDJ7yh8B0M/svYFnQtoiINDAW+qM/umVkZHhmZmakuyEiElXMbKm7Z9R2e30tWkREakUBIiIitaIAERGRWlGAiIhIrShARESkVmLiLCwzKwQ21HLzDoS+wBiPNPb4Fc/jj+exwz+Pv7u7d6xtQzERIMfDzDKP5zS2aKaxx+fYIb7HH89jh7odvw5hiYhIrShARESkVhQgwQUZ45TGHr/iefzxPHaow/HH/RyIiIjUjvZARESkVuI2QMxstJmtM7NsM5sU6f7UFTObZmbbzGxllbJ2Zva+mWUF/7YNys3MngxegxVmNqjKNuOD+llmNr6m52pozKybmc03szVmtsrMvh+Ux/z4zayZmS02sy+Csf8sKE81s0XBOGYEt08guMXCjGDsi8ysR5W2Jgfl68xsVGRGdOzMLMHMlpnZ28F6PI09z8y+NLPlZpYZlJ349727x90PoUvIrwd6Ak2BL4D0SPerjsZ2HjAIWFml7FfApGB5EvBosHwZ8C6hO0EOAxYF5e2AnODftsFy20iPLYyxdwEGBcutga+A9HgYfzCGVsFyE2BRMKaZwLig/I/AncHyd4E/BsvjgBnBcnrw+5AIpAa/JwmRHl+Yr8F9wCvA28F6PI09D+hQreyEv+/jdQ9kCJDt7jnufhCYDoyNcJ/qhLt/ROieLFWNBV4Ill8ArqxS/qKHLCR0N8guwCjgfXcvdvcdwPvA6BPf++Pj7lvc/fNgeQ+wBkgmDsYfjGFvsNok+HHgQmBWUF597Idek1nARWZmQfl0dy9191wgm9DvS4NmZl2By4HngnUjTsZ+BCf8fR+vAZIMbKyyXhCUxaqT3X0LhD5kgU5B+eFeh6h/fYLDEmcS+ks8LsYfHMJZDmwj9Mu/HtjpodtDwz+P4x9jDB7fBbQnSscO/A54AKgM1tsTP2OH0B8L75nZUjObGJSd8Pd9OPdEj0VWQ1k8no52uNchql8fM2sFvA7c6+67Q39c1ly1hrKoHb+H7vY50MzaAG8C/WuqFvwbM2M3syuAbe6+1MxGHiquoWrMjb2KEe6+2cw6Ae+b2doj1K2z8cfrHkgB0K3Keldgc4T6Uh+2BruoBP9uC8oP9zpE7etjZk0IhcfL7v5GUBw34wdw953Ah4SOb7cxs0N/KFYdxz/GGDyeROjQZzSOfQTwb2aWR+hw9IWE9kjiYewAuPvm4N9thP54GEI9vO/jNUCWAGnBWRpNCU2kzY5wn06k2cChMyrGA29VKb8lOCtjGLAr2NWdA1xqZm2DMzcuDcoatOA49lRgjbs/VuWhmB+/mXUM9jwws+bAxYTmgOYD1wTVqo/90GtyDTDPQzOps4FxwZlKqUAasLh+RlE77j7Z3bu6ew9Cv8vz3P2bxMHYAcyspZm1PrRM6P26kvp430f67IFI/RA6E+ErQseJfxzp/tThuF4FtgBlhP6imEDo+O5cICv4t11Q14Cng9fgSyCjSju3EZpEzAZujfS4whz7OYR2uVcAy4Ofy+Jh/MDpwLJg7CuBB4PynoQ+BLOB14DEoLxZsJ4dPN6zSls/Dl6TdcCYSI/tGF+HkfzfWVhxMfZgnF8EP6sOfZ7Vx/te30QXEZFaiddDWCIicpwUICIiUisKEBERqRUFiIiI1IoCREREakUBIiIitaIAERGRWlGAiIhIrfx/QbGcQupha7gAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Test insertion sort on reverse-sorted lists of different size,\n",
    "# and plot the results\n",
    "\n",
    "N_values = list(range(10,5000,200))\n",
    "time_values = []\n",
    "\n",
    "for N in N_values:\n",
    "    input_list = reversed_list(N)\n",
    "    time_taken = time_sort(isort, input_list)\n",
    "    time_values.append(time_taken)\n",
    "\n",
    "plt.plot(N_values, time_values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f66a77cd6d8>]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZAAAAD8CAYAAABZ/vJZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xd8VuX9//HXh7C3LJmBQMIIAioRXLhxV6qi4rai1lWrVlucRcQq7jpaf1TUalFQUQmioojWOhhBZgKBsEOAAGEmZF+/P+5jvykmcnOT5Nzj/Xw8fOTc577OxeeKd/LOOdcZ5pxDRETkYNXxuwAREYlMChAREQmJAkREREKiABERkZAoQEREJCQKEBERCYkCREREQqIAERGRkChAREQkJHX9LqA6tGnTxnXr1s3vMkREIsr8+fO3Oefahrp9VARIt27dSEtL87sMEZGIYmbrDmV7HcISEZGQKEBERCQkChAREQmJAkREREKiABERkZAoQEREJCQKEBERCYkCREQkAuXuLuSRaemUlJX7VoMCREQkwqTn7GLYy98xae4Glm/a41sdChARkQjyefpmLnnlBwDeu/k4+nVu4VstUXErExGRaOec45V/r+bJGcvp37kl/7h6IO2aN/S1JgWIiEiYKyot4/4PljLlx2zO79+Bpy8ZQMN6cX6XpQAREQln2/cWcfO/5jNv7Q7uPCOJ35+ehJn5XRagABERCVsrtuzh+jfmsXVPES9efhS/GtDR75L+hwJERCQMfZWZy+/eXkCj+nFM/u1xHNmlpd8l/YwCREQkjDjneP27tYydnkHv9s2ZcF0KHVo08rusSilARETCRElZOQ9PTeedues5q+/hPHfZkTSuH76/psO3MhGRGLKzoJhbJ/7I96u2c+spPbjnzF7UqRMek+VVUYCIiPhsSfYufvfOj+TsLOSZSwZw8cDOfpcUFAWIiIhPysod479ZzTOfZ9K2WQPevnEwKd1a+V1W0BQgIiI+yNm5j7vfXcjs1Xmc2689f7mwHy0b1/e7rIOiABERqWXTF2/i/g+XUFJWzlPD+zN8YOewuTjwYChARERqyd6iUh5JTee9+dkM6NKSv152JN3aNPG7rJApQEREasGC9Tu4c/JCNuQV8LvTErnj9CTqxUX2DdEVICIiNais3PH3r7N4buZK2jdvyKSbjmNQQuRMlP8SBYiISA3J3lHA3ZMXMXdtHr8a0JGxvz6CFo3q+V1WtVGAiIjUgNRFOTzw4RKcg+cuG8Cvj+wUkRPlv0QBIiJSjQqKS3noo3Sm/JjN0fEtef6yo4hv3djvsmqEAkREpJpk5e7l1onzWZm7lztOT+KO0xKpG+ET5b9EASIiUg1SF+Vw35TFNKgXx5vXD2JIUlu/S6pxQUWjmZ1tZplmlmVmoyp5v4GZTfben2Nm3Sq8d5+3PtPMzjpQn2Z2upn9aGYLzexbM0s8tCGKiNScotIyHp66lDveWUDvDs2ZfseJMREeEESAmFkc8DJwDpAMXG5myfs1GwnscM4lAs8B47xtk4ERQF/gbOBvZhZ3gD7/DlzpnDsSeBt48NCGKCJSMzbkFXDpKz/w5g/ruHFIApNuOjZsn91RE4I5hDUIyHLOrQYws0nAMCCjQpthwGhv+X3gJQucbjAMmOScKwLWmFmW1x+/0KcDmnttWgA5oQ1NRKTmzFq+hbsmL6K83PHKVQM5+4j2fpdU64IJkE7Ahgqvs4HBVbVxzpWa2S6gtbd+9n7bdvKWq+rzBuATM9sH7AaOrawoM7sJuAkgPj4+iGGIiBy60rJynv1iBX/7ehXJHZrz96uOpmvryL0dyaEIZg6kshOXXZBtDnY9wF3Auc65zsDrwLOVFeWcG++cS3HOpbRtGxvHG0XEX7m7C7ny1Tn87etVXD6oCx/cenzMhgcEtweSDXSp8LozPz+s9FObbDOrS+DQU94Btv3ZejNrCwxwzs3x1k8GPguiRhGRGvXDqu387p0F7C0qiaiHPtWkYPZA5gFJZpZgZvUJTIqn7tcmFbjWWx4OzHLOOW/9CO8srQQgCZj7C33uAFqYWU+vr6HAstCHJyJyaMrLHS9/lcWVr86meaO6TL3tRIWH54B7IN6cxu3ADCAOeM05l25mY4A051wqMAF4y5skzyMQCHjt3iUwOV4K3OacKwOorE9v/Y3AFDMrJxAo11friEVEgrQhr4B731/E7NWBe1k9flE/mjbQ5XM/scCOQmRLSUlxaWlpfpchIlGivNwxcc46Hv90OXXMePC8Plx2TJeou5eVmc13zqWEur2iVESkgg15BfxpymK+X7WdIUlteOLi/nRqGTvXdhwMBYiICOCcY+Kc9Tz+yTLMjMcv6seIKNzrqE4KEBGJedk7Ansd32Vt58TENjxxcT86Hxadd9CtTgoQEYlZzjnembuBx6YHbqzx2IVHcMWgeO11BEkBIiIxaePOfYyaspj/rNzG8T1aM+7i/nRppb2Og6EAEZGY4pxj0rwNPDZ9GeXO8eivj+DKQfHUqaO9joOlABGRmJGzcx+jPljCNyu2clz31jw5XHsdh0IBIiJRzznHu2kbGPvxMsqcY8ywvlw1uKv2Og6RAkREolrFvY5ju7fiyYsHRO0zymubAkREopL2OmqeAkREok7FM6y011FzFCAiEjWcc0yet4Gx3hlW2uuoWQoQEYkK2uuofQoQEYlo2uvwjwJERCJWzs59/El7Hb5RgIhIxHHO8V5aNo9+nKEzrHykABGRiLJldyGjpizmq8ytDE5oxVPDtdfhFwWIiEQE5xxTF+bw59R0ikrL+POvkrn2uG7a6/CRAkREwt7WPUU8+NESZqRv4ej4ljx9yQC6t23qd1kxTwEiImFt+uJNPPjREvKLy7j/3N6MPLE7cdrrCAsKEBEJS3n5xTw8dSkfL97EgM4tePqSASQd3szvsqQCBYiIhJ3P0zdz/4dL2bWvmHvO7MnNJ/egblwdv8uS/ShARCRs7Coo4ZFp6XywYCPJHZrz1shB9OnQ3O+ypAoKEBEJC9+s2Mq97y9i295i7jg9idtPTaR+Xe11hDMFiIj4qrCkjCc/y+S179aQ1K4pr15zDP06t/C7LAmCAkREfLN8827unLSQ5Zv3cN3x3Rh1Tm8a1ovzuywJkgJERGqdc443vl/L458up3nDurx+3TGc2rud32XJQVKAiEityt1TyL3vLebfK7Zyeu92jBvenzZNG/hdloRAASIiteaLjC38acpi8otKefTXR3DV4HjMdFFgpFKAiEiN21dcxtjpGUycs57kDs154fIjSWyniwIjnQJERGrU0o27uGPSAlZvzeemk7rzhzN70qCuJsqjgQJERGpEeblj/H9W88znmbRqUp+JNwzmhMQ2fpcl1UgBIiLVbuPOfdzz7iJ+WL2dc45oz18u7MdhTer7XZZUMwWIiFSbn54UOObjDJxzjLu4H5emdNFEeZQK6j4BZna2mWWaWZaZjark/QZmNtl7f46Zdavw3n3e+kwzO+tAfVrAY2a2wsyWmdkdhzZEEakNubsLueGfafxxymL6dmzOZ3eexGXH6CyraHbAPRAziwNeBoYC2cA8M0t1zmVUaDYS2OGcSzSzEcA44DIzSwZGAH2BjsBMM+vpbVNVn9cBXYDezrlyM9PVRSJhbtqiHB6aupR9xWU8fH4y1x2vJwXGgmAOYQ0CspxzqwHMbBIwDKgYIMOA0d7y+8BLFvizYxgwyTlXBKwxsyyvP36hz1uAK5xz5QDOudzQhyciNSkvv5iHpi5l+uJNHNmlJc9cOoAeelJgzAgmQDoBGyq8zgYGV9XGOVdqZruA1t762ftt28lbrqrPHgT2Xi4EtgJ3OOdWBlGniNSimRlbGPXBEnbtK+bes3rx25O665kdMSaYAKlsP9QF2aaq9ZV9yn7qswFQ6JxLMbOLgNeAIT8ryuwm4CaA+Pj4yisXkWq3u7CEMdMyeH9+Nr3bN+PN6weR3FHP7IhFwQRINoE5iZ90BnKqaJNtZnWBFkDeAbatan02MMVb/hB4vbKinHPjgfEAKSkp+weaiNSA77K2ce97i9i8u5DbT03kjtOT9MyOGBbM//l5QJKZJZhZfQKT4qn7tUkFrvWWhwOznHPOWz/CO0srAUgC5h6gz4+A07zlk4EVoQ1NRKpLQXEpD09dypWvzqFh/Tim3HI895zVS+ER4w64B+LNadwOzADigNecc+lmNgZIc86lAhOAt7xJ8jwCgYDX7l0Ck+OlwG3OuTKAyvr0/skngIlmdhewF7ih+oYrIgcrc/Mebpk4nzXb8hl5YgL3ntVLz+wQACywoxDZUlJSXFpamt9liESdDxdkc/8HS2nasC5/HXEkx/fQrUiiiZnNd86lhLq9rkQXkZ8pLCljzMcZvD1nPYMTWvHiFUfRrllDv8uSMKMAEZH/sSGvgFsn/siSjbu4+eQe3HNmT52eK5VSgIjIf81avoW7Ji+i3Dn+cU0KQ5MP97skCWMKEBGhrNzx3BcreOmrLJI7NOfvVx1N19ZN/C5LwpwCRCTGbdtbxB3vLOD7VdsZcUwXRl/QV2dZSVAUICIxLG1tHre9/SM7C0p4anh/LknpcuCNRDwKEJEY5JxjwrdreOLT5XQ+rBFv3DaIPh10OxI5OAoQkRizu7CEUVMW88mSzZzdtz1PXtKf5g3r+V2WRCAFiEiMcM4xdWEOj32yjLz8Yh48rw8jT0zQA58kZAoQkRiwcsseHpq6lNmr8xjQpSWvXXsM/Tq38LssiXAKEJEoVlBcygtfZvHqf1bTpEFd/nJhP0Yc00VPC5RqoQARiULOOWakb2bMtAxydhVyycDOjDqnN62bNvC7NIkiChCRKLNuez5/Tk3n68yt9G7fjBcuP4qUbq38LkuikAJEJEoUlpTxyr9X8bevV1GvjvHQ+clce1xX3cdKaowCRCQKfJWZy+jUdNZtL+BXAzry4Hl9OLy57p4rNUsBIhLBcnbuY8y0DD5L30z3tk3418jBnJikZ3ZI7VCAiESg4tJyJny7hhe+XInDce9ZvbhhSAIN6uoeVlJ7FCAiEeb7rG08NHUpq7bmMzT5cB4+P5kurRr7XZbEIAWISITYsruQsdOXMW1RDl1aNeK161I4rbee1yH+UYCIhLmSsnL++f1anvtiBSXljt+fnsQtp/TQLdfFdwoQkTA2d00eD09dyvLNezilV1tG/6ov3droQU8SHhQgImFo654iHv90GR/8uJFOLRvxylUDOavv4brxoYQVBYhIGCkrd0ycs46nZmRSWFLGraf04PbTEmlcXz+qEn70qRQJE6u37uWuyQtZlL2LExJb88gFR5DYrqnfZYlUSQEi4jPnHJPnbeCRaRnUr1uHv444kgsGdNThKgl7ChARH+0sKOa+D5bw6dLNHN+jNc9cOoAOLRr5XZZIUBQgIj75Pmsbd7+7iO35Rdx3Tm9uHNJdz+mQiKIAEallxaXlPPNFJuO/WU1C6yb845oT9HRAiUgKEJFatGrrXn4/aQFLN+7m8kHxPHR+H51hJRFLn1yRWuCcY9K8DYyZlkGDenV45aqBnH1Ee7/LEjkkChCRGrYjv5hRHyxmRvoWTkhszbOXHqlndUhUUICI1KDvsrZx97sLycsv5oFz+zDyxARNlEvUUICI1ID8olKe/jyTN75fS/c2TZhw7TEc0UkT5RJdFCAi1ezrzFwe+HApObv2cfWxXbnvnD40qq8750r0qRNMIzM728wyzSzLzEZV8n4DM5vsvT/HzLpVeO8+b32mmZ11EH2+aGZ7QxuWSO3bvreIOyct4LrX59Gofhzv/fY4xgw7QuEhUeuAeyBmFge8DAwFsoF5ZpbqnMuo0GwksMM5l2hmI4BxwGVmlgyMAPoCHYGZZtbT26bKPs0sBWhZLSMUqWHOOT5auJEx0zLYW1TK709P4tZTe+jxshL1gjmENQjIcs6tBjCzScAwoGKADANGe8vvAy9Z4EY+w4BJzrkiYI2ZZXn9UVWfXmA9BVwBXHgIYxOpcRvyCnjgo6V8s2IrR8W3ZNzF/el5eDO/yxKpFcEESCdgQ4XX2cDgqto450rNbBfQ2ls/e79tO3nLVfV5O5DqnNukm8lJuCord7zx/VqenpFJHYNHLujLVcd2JU5nWEkMCSZAKvuJcEG2qWp9ZXMvzsw6ApcApxywKLObgJsA4uPjD9RcpNos37ybP01ZwqINOzm1V1vGXtiPTi11A0SJPcEESDbQpcLrzkBOFW2yzawu0ALIO8C2la0/CkgEsry9j8ZmluWcS9y/KOfceGA8QEpKyv6BJlLtCkvKeGlWFq/8exXNG9XTbdcl5gUTIPOAJDNLADYSmBS/Yr82qcC1wA/AcGCWc86ZWSrwtpk9S2ASPQmYS2DP5Gd9OufSgf/e38HM9lYWHiK1bd7aPP40ZTGrt+Zz0dGdePC8ZFo1qe93WSK+OmCAeHMatwMzgDjgNedcupmNAdKcc6nABOAtb5I8j0Ag4LV7l8CEeylwm3OuDKCyPqt/eCKHZk9hCU9+lslbs9fR+bBGvHn9IE7q2dbvskTCgjkX+Ud/UlJSXFpamt9lSJT5ankuD3y4hE27C/nN8Qn84cyeNGmga28lepjZfOdcSqjb66dBZD95+cWMmZbORwtzSGrXlCm3HM/R8Yf5XZZI2FGAiHicc6QuyuGRaRnsKSzRBYEiB6AAEQE27drHgx8u5cvluQzo0pInL+5Pr/a6IFDklyhAJKaVlzvenrueJz5dTlm548Hz+vCbExJ0QaBIEBQgErNWb93LqA+WMHdNHicktubxC/sT37qx32WJRAwFiMSc4tJyXv12Nc/PXEmDunV48uL+XJLSWRcEihwkBYjElB9WbeehqUvJyt3L2X3bM2ZYX9rp8bIiIVGASEzI3VPIX6Yv46OFOXQ+rBETrk3h9D6H+12WSERTgEhUKyt3/Gv2Op6ekUlRaTl3nJbIracm0rCeTs0VOVQKEIlaC9bv4MGPlpKes5sTE9swZlhfurdt6ndZIlFDASJRZ2dBMeM+y2TSvPW0a9aAl644ivP6ddAkuUg1U4BI1Cgvd7z/YzZPfLqcXftKGHlCAncO7UlT3b9KpEboJ0uiwrJNu3nwo6XMX7eDgV0PY+yvj6BPh+Z+lyUS1RQgEtGKSst4fuZKxn+zmhaN6vHk8P4MP7ozdXQluUiNU4BIxMrcvIc7Jy9k2abdXJrSmfvP7UPLxnrIk0htUYBIxCkvd0z4dg1PzcikeaO6vHpNCmck65oOkdqmAJGIkr2jgD+8u4g5a/I4M/lwHr+oH62bNvC7LJGYpACRiOCc44MfNzI6NR0HPDW8P8MH6v5VIn5SgEjYy8sv5v4PlvBZ+mYGdWvFM5cOoEsr3TVXxG8KEAlrs5Zv4Y/vL2H3vhLuO6c3Nwzprmd1iIQJBYiEpfyiUsZOX8Y7c9fTu30z3ho5SNd1iIQZBYiEnfnrdnD3uwtZn1fAb0/uzt1De+q55CJhSAEiYWNnQTHPfbGCt2avo2PLRky68VgGd2/td1kiUgUFiPiurNwxad56np6Rya59JVx1bFfuPasXzRrW87s0EfkFChDxVdraPP6cmk56zm4GJ7Ri9AV9NdchEiEUIOKLLbsLeeLT5Xy4YCMdWjTkxcuP4vz+uuW6SCRRgEitKiot47Vv1/LirJWUljluPzWRW0/tQeP6+iiKRBr91Eqt+SozlzHTMlizLZ8z+hzOQ+f3oWvrJn6XJSIhUoBIjVu7LZ9HP87gy+W5dG/ThDd+cwyn9Grnd1kicogUIFJjCopLeWlWFq/+Zw314oz7zunNb05IoH7dOn6XJiLVQAEi1c45xydLNjN2egabdhVy4VGdGHVObw5v3tDv0kSkGilApFqt3LKHP6em8/2q7fTp0JwXLj+KY7q18rssEakBChCpFnsKS/jrzJW88f1aGteP49FhfblicFfd+FAkiilA5JA45/ho4Ub+8slytu0tYsQxXbjnzF56yJNIDAhqNtPMzjazTDPLMrNRlbzfwMwme+/PMbNuFd67z1ufaWZnHahPM5vorV9qZq+Zme5nEaYycnZz6f/7gbsmL6Jji4Z8eOsJPH5Rf4WHSIw44B6ImcUBLwNDgWxgnpmlOucyKjQbCexwziWa2QhgHHCZmSUDI4C+QEdgppn19Lapqs+JwFVem7eBG4C/H+I4pRrtKijh2S8yeWv2Olo2rs+4i/txycAu1NHhKpGYEswhrEFAlnNuNYCZTQKGARUDZBgw2lt+H3jJAvekGAZMcs4VAWvMLMvrj6r6dM598lOnZjYX6Bzi2KSalZc73pu/gXGfZbKzoJirj+3K3UN70aKxdhJFYlEwAdIJ2FDhdTYwuKo2zrlSM9sFtPbWz95v207e8i/26R26uhr4fRA1Sg3LyNnNAx8tYcH6nRzT7TAeuWAwyR1100ORWBZMgFR2XMIF2aaq9ZXNvezf59+Ab5xz/6m0KLObgJsA4uPjK2si1SC/qJTnZ67gte/W0rJRPZ65ZAAXHd1JNz0UkaACJBvoUuF1ZyCnijbZZlYXaAHkHWDbKvs0sz8DbYHfVlWUc248MB4gJSVl//CRavB5+mZGp6aTs6uQywfF86eze9GycX2/yxKRMBFMgMwDkswsAdhIYFL8iv3apALXAj8Aw4FZzjlnZqnA22b2LIFJ9CRgLoE9k0r7NLMbgLOA051z5Yc4PglB9o4CRqdmMHPZFnq3b8aLVxzFwK66GFBE/tcBA8Sb07gdmAHEAa8559LNbAyQ5pxLBSYAb3mT5HkEAgGv3bsEJtxLgducc2UAlfXp/ZOvAOuAH7zDJB8458ZU24ilSiVl5bz+3Rqe+2IlAPefG7h3Vb043btKRH7OnIv8oz8pKSkuLS3N7zIi2vx1O3jgwyUs37yHM/q0Y/QFfel8WGO/yxKRGmRm851zKaFuryvRY9yughKe+Gw578xdT8cWDRl/9UDO7Nve77JEJAIoQGKUc46pC3MYOz2DHQUl3HBiAncN7UmTBvpIiEhw9NsiBi3J3sWYj9OZt3YHR3ZpyT+vP4K+HVv4XZaIRBgFSAzJ3VPI0zMyeW9+Nq0a1+fxi/pxWYpuQSIioVGAxICi0jJe/24tL83Koqi0jBuHdOf20xJp3lC3IBGR0ClAophzji8ytvDYJ8tYt72AM/q044Hzkklo08Tv0kQkCihAolTm5j2M+Tid77K2k9SuKW9eP4iTerb1uywRiSIKkCizI7+YZ79YwcQ562jWsB6jf5XMlcd21cWAIlLtFCBRoqSsnH/NXsfzM1eyt6iUq47tyl1n9OSwJrp3lYjUDAVIFPguaxujU9NZmbuXExJb8/D5fenVvpnfZYlIlFOARLDsHQU8Nn0Zny7dTHyrxoy/eiBDkw/XrdZFpFYoQCJQYUkZ//hmNS9/nQXAH4b25MaTutOwXpzPlYlILFGARBDnHDOX5fLoxxmszyvg3H7tuf/cPrrpoYj4QgESIdZsy+eRael8nbmVxHZNmXjDYE5IbON3WSISwxQgYS6/qJSXvspiwn/WUL9uHR48rw/XHt9Np+WKiO8UIGHKOce0xZv4y/RlbN5dyEVHd2LUOb1p16yh36WJiAAKkLC0bNNuRqemM2dNHn07NuflK/VIWREJPwqQMLJp1z6e/XwF7/+YTYtG9XjswiMYcUw8cbpbroiEIQVIGNhTWMIr/17FhG/XUF4ON5yYwG2nJtKysa4iF5HwpQDxUUlZOe/MXc9fZ65ke34xw47syD1n9qJLK52WKyLhTwHiA+ccM9I3M+6zTNZsy+fY7q14/dw+9O/c0u/SRESCpgCpZfPX7eDxT5aRtm4Hie2aMuHaFE7r3U63HxGRiKMAqSVrt+Uz7rPlfLp0M22bNeDxi/pxycDO1NX1HCISoRQgNSwvv5gXvlzJv2avo37dOtx5RhI3DulOkwb61otIZNNvsRpSUlbOWz+s4/mZK9hbVMplx8Rz19AkXQgoIlFDAVIDvlqey6PTM1i9NZ8hSW146Pxkeh6u53OISHRRgFSjlVv2MHb6Mv69Yivd2zThtetSOLWXJshFJDopQKrBzoJinp+5krdmr6Nx/TgePK8P1xzXjfp1NUEuItFLAXIISsrKmTh7Hc/NXMmewhKuGBzP3UN70UrPIReRGKAACdHXmbmMnb6MrNy9nJgYmOfQc8hFJJYoQA5SVu5exk7P4OvMrSS0acKr16Rweh/Nc4hI7FGABGnNtnxenLWSjxZspEmDuprnEJGYpwA5gNVb9/LSrCw+WriR+nXrMPLEBG4+uQetmzbwuzQREV8pQKqwyguOqV5w3DCkOzcO6U7bZgoOERFQgPxMVu5eXpq1ktRFOTSoG8eNQ7pz40ndaaM9DhGR/xFUgJjZ2cBfgTjgVefcE/u93wB4ExgIbAcuc86t9d67DxgJlAF3OOdm/FKfZpYATAJaAT8CVzvnig9tmAeWlbuHF77MYtriHBrWjePGkwJ7HAoOEZHKHTBAzCwOeBkYCmQD88ws1TmXUaHZSGCHcy7RzEYA44DLzCwZGAH0BToCM82sp7dNVX2OA55zzk0ys1e8vv9eHYOtzMote3hhVhYfL86hUb04fntSD24ckqA5DhGRAwhmD2QQkOWcWw1gZpOAYUDFABkGjPaW3wdessB5rcOASc65ImCNmWV5/VFZn2a2DDgNuMJr80+v3xoJkPs/XMI7c9fTqF4cN5/cgxuHdNdFgCIiQQomQDoBGyq8zgYGV9XGOVdqZruA1t762ftt28lbrqzP1sBO51xpJe3/h5ndBNwEEB8fH8Qwfi6+VWNuObkHNyg4REQOWjABUtkVci7INlWtr+ziiV9q//OVzo0HxgOkpKRU2uZAbj65RyibiYgIlf8i31820KXC685ATlVtzKwu0ALI+4Vtq1q/DWjp9VHVvyUiImEgmACZBySZWYKZ1ScwKZ66X5tU4FpveTgwyznnvPUjzKyBd3ZVEjC3qj69bb7y+sDrc2rowxMRkZpywENY3pzG7cAMAqfcvuacSzezMUCacy4VmAC85U2S5xEIBLx27xKYcC8FbnPOlQFU1qf3T/4JmGRmY4EFXt8iIhJmLPBHf2RLSUllN2jqAAAEt0lEQVRxaWlpfpchIhJRzGy+cy4l1O11J0AREQmJAkREREKiABERkZAoQEREJCRRMYluZluBdSFs2obAtSexKpbHH8tjh9gev8b+f7o659qG2llUBEiozCztUM5AiHSxPP5YHjvE9vg19uobuw5hiYhISBQgIiISklgPkPF+F+CzWB5/LI8dYnv8Gns1iek5EBERCV2s74GIiEiIYjZAzOxsM8s0sywzG+V3PdXBzF4zs1wzW1phXSsz+8LMVnpfD/PWm5m94I1/sZkdXWGba732K83s2sr+rXBjZl3M7CszW2Zm6Wb2e299rIy/oZnNNbNF3vgf8dYnmNkcbyyTvbtf490he7I3/jlm1q1CX/d56zPN7Cx/RnTwzCzOzBaY2cfe61ga+1ozW2JmC80szVtX859951zM/UfgDsCrgO5AfWARkOx3XdUwrpOAo4GlFdY9CYzylkcB47zlc4FPCTzE61hgjre+FbDa+3qYt3yY32MLYuwdgKO95WbACiA5hsZvQFNvuR4wxxvXu8AIb/0rwC3e8q3AK97yCGCyt5zs/Tw0ABK8n5M4v8cX5PfgbuBt4GPvdSyNfS3QZr91Nf7Zj9U9kP8+5905Vwz89Jz3iOac+4bA7fQrGkbg2fJ4X39dYf2bLmA2gQd5dQDOAr5wzuU553YAXwBn13z1h8Y5t8k596O3vAdYRuBxyLEyfuec2+u9rOf954DTgPe99fuP/6fvy/vA6WZm3vpJzrki59waIIvAz0tYM7POwHnAq95rI0bG/gtq/LMfqwFS2XPeK332ehQ43Dm3CQK/ZIF23vqqvgcR/73xDkkcReCv8JgZv3cIZyGQS+CHfxWw0zlX6jWpOJb/jtN7fxfQmsgd//PAH4Fy73VrYmfsEPhj4XMzm29mN3nravyzH8wz0aNR0M9ej2IH+xz7iGBmTYEpwJ3Oud2BPywrb1rJuogevws8rO1IM2sJfAj0qayZ9zVqxm9m5wO5zrn5ZnbKT6sraRp1Y6/gBOdcjpm1A74ws+W/0Lbaxh+reyDBPOc9Wmzxdk/xvuZ66w/2efVhz8zqEQiPic65D7zVMTP+nzjndgJfEzi+3dLMfvpDseJY/jtO7/0WBA5/RuL4TwAuMLO1BA5Hn0ZgjyQWxg6Acy7H+5pL4I+HQdTCZz9WAySY57xHi4rPq6/4jPlU4BrvjIxjgV3ebu4M4EwzO8w7a+NMb11Y845hTwCWOeeerfBWrIy/rbfngZk1As4gMA/0FTDca7b/+H/6vgwHZrnATGoqMMI7UykBSALm1s4oQuOcu88519k5143Az/Is59yVxMDYAcysiZk1+2mZwGd2KbXx2ff77AG//iNwJsIKAseJH/C7nmoa0zvAJqCEwF8TIwkc2/0SWOl9beW1NeBlb/xLgJQK/VxPYAIxC/iN3+MKcuwnEtjdXgws9P47N4bG3x9Y4I1/KfCwt747gV+CWcB7QANvfUPvdZb3fvcKfT3gfV8ygXP8HttBfh9O4f/OwoqJsXvjXOT9l/7T77Pa+OzrSnQREQlJrB7CEhGRQ6QAERGRkChAREQkJAoQEREJiQJERERCogAREZGQKEBERCQkChAREQnJ/wcl7h5Dr0Q+jQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Test insertion sort on nearly-sorted lists of different size,\n",
    "# and plot the results\n",
    "\n",
    "N_values = list(range(10,5000,200))\n",
    "time_values = []\n",
    "\n",
    "for N in N_values:\n",
    "    input_list = nearly_sorted_list(N)\n",
    "    time_taken = time_sort(isort, input_list)\n",
    "    time_values.append(time_taken)\n",
    "\n",
    "plt.plot(N_values, time_values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f66a77a2630>]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZYAAAD8CAYAAABU4IIeAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xl8VdW5//HPwxDmMQlTQiBKUIMyeQSLQx0rDtdYq9dYW1GxqFdqW2/r1V9b7Y/be1vtXMeiUMAJKE7pvbY4oKJWhjBKkCHMYQ6BMCYhyfP742z6O8aEHGLCSU6+79frvLL32mut/axDyHP2Xnufbe6OiIhIfWkR6wBERCS+KLGIiEi9UmIREZF6pcQiIiL1SolFRETqlRKLiIjUKyUWERGpV0osIiJSr5RYRESkXrWKdQANKSkpyfv37x/rMEREmpRFixYVuntyXdvHdWLp378/ubm5sQ5DRKRJMbNNX6a9ToWJiEi9UmIREZF6pcQiIiL1SolFRETqlRKLiIjUKyUWERGpV0osIiJSr5RYRETizLRPNvKP/MKY7V+JRUQkjvzv8u08/EYe0xduiVkMSiwiInFi4cYifjBzKaF+3XjshsExi0OJRUQkDuTvOsidU3NJ7daOZ28N0bZ1y5jFosQiItLE7TpQwpjJC2jd0ph6+wi6dUiIaTxx/SWUIiLx7lBpOXdMWUjRoTJm3HUufbu3j3VISiwiIk1VeUUl9760mM+2H+C5W0MMTu0a65CAKE+FmdloM1ttZvlm9mA129uY2Yxg+3wz6x+x7aGgfLWZXRFRPtnMdpnZiip9zTCzpcFro5ktDcr7m9mRiG3P1HXQIiJNnbvzk9dX8P7q3fz8ujO5+PQesQ7pn2o9YjGzlsCTwOVAAbDQzHLcfWVEtbHAXncfYGbZwKPATWaWCWQDg4A+wDtmNtDdK4ApwBPAtMj9uftNEfv+DVAcsXmduw898WGKiMSXx+fkM33hFsZfPICbR6TFOpzPieaIZQSQ7+7r3b0MmA5kVamTBUwNlmcBl5qZBeXT3b3U3TcA+UF/uPtcoKimnQbt/xV4+QTGIyIS9/6Su4Xfvr2G64en8O9fGxjrcL4gmsSSAkTeaVMQlFVbx93LCR9lJEbZtiYXADvdfW1EWbqZLTGzD8zsgij7ERGJG3PX7OahVz/l/AFJ/PL6wYQ/gzcu0UzeVxe1R1knmrY1uZnPH61sB9LcfY+ZnQ28bmaD3H3/5wIxGweMA0hLa1yHhyIiX8bKbfv5txcXM6BHR5761nASWjXOO0aiiaoA6Buxngpsq6mOmbUCuhA+zRVN2y8I+rgemHGsLDidtidYXgSsA75wDOjuE9095O6h5OTkWgcnItIUbN13hNunLKBT21ZMuX0Endu2jnVINYomsSwEMsws3cwSCE/G51SpkwOMCZZvAOa4uwfl2cFVY+lABrAgin1eBqxy94JjBWaWHFxIgJmdEvS1Poq+RESatOIjR7n9zws4XFbBlNtH0KtL21iHdFy1ngpz93IzGw/MBloCk909z8wmALnungNMAp43s3zCRyrZQds8M5sJrATKgXuDK8Iws5eBi4AkMysAHnH3ScFus/nipP2FwAQzKwcqgLvdvcbJfxGReFBaXsFdz+eyofAQU+8YwWm9OsU6pFpZ+MAiPoVCIc/NzY11GCIidbK/5CjjX1rC3DW7+UP2ULKGRnvt05djZovcPVTX9rrzXkSkEdq85zBjpy5kQ+EhHv3GWSctqdQHJRYRkUZm4cYi7np+ERWVzrSxIxh1alKsQzohSiwiIo3IK4sKeOjVT0nt1o5Jt51DelKHWId0wpRYREQagcpK59dvreap99cx6tREnr7lbLq0b7yXFB+PEouISIwdLivn/hnL+HveDm4ekcaErEG0btk4b36MhhKLiEgM7Sgu4c5pC8nbtp+fXH0GY89Pb5Rf03IilFhERGJkxdZixk5dyMGScp67NcSlZ/SMdUj1QolFRCQG/r5iOz+YsYzuHRKYdc8ozujdOdYh1RslFhGRk8jdefqDdTz299UMS+vKxG+HSO7UJtZh1SslFhGRBlJR6ew9XMaeg2XsOVhK4aEy3lm5k5xl27h2SB8eu2EwbVu3jHWY9U6JRUSkjtbuPMDCjXvZc7CUPYfKKDxYGk4ih8I/iw6XUfVbs8zg+5dl8L1LM5r8JH1NlFhEROpg674jXPvExxw5WgFA57atSOrYhsSOCZyS1JFz+ieQ2LENSR0TSOwQLk/qmEByp7Z0adc070+JlhKLiEgdTPhrHgB/+94FnJLcgTat4u+UVl013TtwRERiZM6qnczO28l3Lx3AGb07K6lUocQiInICSo5W8EhOHqcmd+DO80+JdTiNkk6FiYicgKfeX8eWoiO89J2RjfaZ87Gmd0VEJEobCg/xzPvryBrap8l9lf3JpMQiIhIFd+fhN1bQplULfnzVGbEOp1GLKrGY2WgzW21m+Wb2YDXb25jZjGD7fDPrH7HtoaB8tZldEVE+2cx2mdmKKn39zMy2mtnS4HVVbX2JiDS0v63YwYdrC/n3rw2kR+e2sQ6nUas1sZhZS+BJ4EogE7jZzDKrVBsL7HX3AcDvgEeDtplANjAIGA08FfQHMCUoq87v3H1o8Hozir5ERBrMwdJyJvx1JZm9O/Otc/vFOpxGL5ojlhFAvruvd/cyYDqQVaVOFjA1WJ4FXGrhW0qzgOnuXuruG4D8oD/cfS5QdAKx1tiXiEhD+sM7a9ixv4Sff/1MWjXh56ScLNG8QynAloj1gqCs2jruXg4UA4lRtq3OeDNbHpwu63YCcYiI1KvVOw4w+eON3DyiL8PTutXeQKJKLNV9mY1HWSeatlU9DZwKDAW2A785gTgws3Fmlmtmubt3765lVyIiNXN3fvr6Cjq3bcUDV5we63CajGgSSwHQN2I9FdhWUx0zawV0IXyaK5q2n+PuO929wt0rgWf5/6e7ourL3Se6e8jdQ8nJybUMTUSkZq8u3sqCjUU8eOXpdOuQEOtwmoxoEstCIMPM0s0sgfAEek6VOjnAmGD5BmCOu3tQnh1cNZYOZAALjrczM+sdsfp14NhVYyfcl4hIXRUfPsp/v/kZw9O6cuPZfWtvIP9U65337l5uZuOB2UBLYLK755nZBCDX3XOAScDzZpZP+EglO2ibZ2YzgZVAOXCvu1cAmNnLwEVAkpkVAI+4+yTgMTMbSvg010bgrtr6EhGpb796axV7D5cxbewIWrSIz6+3byjmVR8WEEdCoZDn5ubGOgwRaWKWF+wj68mPuW1Ufx75l0GxDuekM7NF7h6qa3tdNyciEqGi0vnJ6ytI7tiG+y8fGOtwmiQlFhGRCC8t2MzygmJ+fPUZdGob3w/kaihKLCIigcKDpfzq76sYdWoi1w7pE+twmiwlFhGRwC/eXMWRoxVMyDozbp9HfzIosYiIAB+u3c0riwv4zgWnMKBHx1iH06TpQV8i0qyVllfw+Lv5PP3BOvontmf8JQNiHVKTp8QiIs3WpwXF/PAvy1i98wA3nJ3KT6/OpH2C/ix+WXoHRaTZKS2v4Ik5+Tz1/jqSOiYw+bYQl5zeM9ZhxQ0lFhFpVqo7SunSXpcV1yclFhFpFnSUcvIosYhI3NNRysmlxCIicausvJLH56zVUcpJpsQiInFpxdbwUcqqHQf4xvBUHr5GRyknixKLiMSdd1bu5O4XFpGoo5SYUGIRkbiSt62Y+6YvYVCfzky7Y6SOUmJAX+kiInFj5/4Sxk7JpWu71jw7JqSkEiM6YhGRuHC4rJw7p+ZyoOQos+4ZRY9ObWMdUrOlxCIiTV5lpXP/jGXkbSvm2VtDnNG7c6xDataiOhVmZqPNbLWZ5ZvZg9Vsb2NmM4Lt882sf8S2h4Ly1WZ2RUT5ZDPbZWYrqvT1KzNbZWbLzew1M+salPc3syNmtjR4PVPXQYtIfPnVW6v5e94Ofnx1JpeeoYn6WKs1sZhZS+BJ4EogE7jZzDKrVBsL7HX3AcDvgEeDtplANjAIGA08FfQHMCUoq+pt4Ex3HwysAR6K2LbO3YcGr7ujG6KIxLOZuVt4+v113DIyjTvO6x/rcITojlhGAPnuvt7dy4DpQFaVOlnA1GB5FnCphZ+SkwVMd/dSd98A5Af94e5zgaKqO3P3t9y9PFidB6Se4JhEpJmYt34PP37tUy7ISOJn1w7Sw7kaiWgSSwqwJWK9ICirtk6QFIqBxCjbHs8dwN8i1tPNbImZfWBmF5xAPyISZzYUHuLuFxbRL7EDT3xzOK1b6iLXxiKayfvqPgJ4lHWiaVv9Ts1+DJQDLwZF24E0d99jZmcDr5vZIHffX6XdOGAcQFpaWjS7EpEmZt/hMu6YspAWZkwecw5d2umy4sYkmhRfAPSNWE8FttVUx8xaAV0In+aKpu0XmNkY4BrgFnd3gOB02p5geRGwDhhYta27T3T3kLuHkpOToxieiDQlZeWV3P3CIrbuPcLEb59NWmL7WIckVUSTWBYCGWaWbmYJhCfjc6rUyQHGBMs3AHOChJADZAdXjaUDGcCC4+3MzEYD/wFc6+6HI8qTj038m9kpQV/ro4hfROKEu/OT1z9l3voiHrthMKH+3WMdklSj1lNh7l5uZuOB2UBLYLK755nZBCDX3XOAScDzZpZP+EglO2ibZ2YzgZWET2vd6+4VAGb2MnARkGRmBcAj7j4JeAJoA7wdTMTNC64AuxCYYGblQAVwt7t/YfJfROLXxLnrmZlbwH2XDOC6YScyXSsnkwVnmuJSKBTy3NzcWIchIvVgdt4O7n5hEVed1ZvHs4fRooWuAGsoZrbI3UN1ba/LKESk0VuxtZjvT1/KkNSu/ObGIUoqjZy+0kVEGq0dxSVM+cdGXpy3ie4dEnj21hBtW7esvaHElBKLiDQ6n23fz7Mfruevy7ZRUemMPrMXP7ridJI7tYl1aBIFJRYRaRTcnblrC3nuw/V8uLaQ9gktuWVkP+44L12XFDcxSiwiElOl5RXkLN3GpI82sGrHAXp0asMDo0/jlhH99DyVJkqJRURiovjwUV6Yv4mp/9jIrgOlnN6rE7++cQjXDulDQitdV9SUKbGIyEm1c38JT7+/jpm5WzhcVsEFGUn8+sYhXJCRpC+RjBNKLCJy0hQdKuOmP33C1n1HuHZICndekK6HcsUhJRYROSlKjlYwblou24pLmD7uXM7up69jiVc6kSkiDa6y0nlg1nJyN+3lt/86REklzimxiEiD++3ba8hZto0HRp/GNYP7xDocaWBKLCLSoGYu3MIT7+WTfU5f7vnqqbEOR04CJRYRaTAf5xfyf4JHB//ndWfqqq9mQolFRBrE2p0HuPuFRZya3JEnb9Gjg5sT/UuLSL3bdaCE2/68kLatWzL59nPo3FZ30DcnSiwiUq+OlFXwnam5FB0qY/KYc0jp2i7WIclJpvtYRKTeVFQ635+xhOVbi5n47RBnpXaJdUgSAzpiEZF684s3P2N23k5+enUml2f2jHU4EiNRJRYzG21mq80s38werGZ7GzObEWyfb2b9I7Y9FJSvNrMrIsonm9kuM1tRpa/uZva2ma0NfnYLys3M/hj0tdzMhtd10CJS/57/ZCPPfbSB20b1547z02MdjsRQrYnFzFoCTwJXApnAzWaWWaXaWGCvuw8Afgc8GrTNBLKBQcBo4KmgP4ApQVlVDwLvunsG8G6wTrD/jOA1Dng6uiGKSEN7b9UuHsnJ47IzevDTa6r+eZDmJpojlhFAvruvd/cyYDqQVaVOFjA1WJ4FXGrhC9azgOnuXuruG4D8oD/cfS5QVM3+IvuaClwXUT7Nw+YBXc2sdzSDFJGGk7etmPEvLSazT2f+kD2MlnoefbMXTWJJAbZErBcEZdXWcfdyoBhIjLJtVT3dfXvQ13agxwnEISIn0cbCQ9wxZSFd2rVm0phz6NBG1wNJdImluo8fHmWdaNpGK6q+zGycmeWaWe7u3bvruCsRqc3cNbu59omPKC2vZNJt59Czc9tYhySNRDSJpQDoG7GeCmyrqY6ZtQK6ED7NFU3bqnYeO8UV/Nx1AnHg7hPdPeTuoeTk5Fp2JSInyt15du56bvvzAvp0bUfOvefrmSryOdEkloVAhpmlm1kC4cn4nCp1coAxwfINwBx396A8O7hqLJ3wxPuCWvYX2dcY4I2I8luDq8POBYqPnTITkZOj5GgF989cxn+9+RlXDOrFK/eMIi2xfazDkkam1hOi7l5uZuOB2UBLYLK755nZBCDX3XOAScDzZpZP+EglO2ibZ2YzgZVAOXCvu1cAmNnLwEVAkpkVAI+4+yTgl8BMMxsLbAZuDEJ5E7iK8AUAh4Hb6+MNEJHobC8+wl3PL2J5QTH3Xz6Q8RcPoIUm6qUaFj6wiE+hUMhzc3NjHYZIk5e7sYi7X1hMydEKfnfTUN38GOfMbJG7h+raXpdwiMhxvbxgMw+/sYKUru14+TsjyejZKdYhSSOnxCIi1TpaUcmEv67k+XmbuHBgMo9nD6NLe31LsdROiUVEvqDwYCn/9uJiFmwo4q4LT+GB0afrxkeJmhKLiHzOiq3F3PX8IgoPlvL7m4Zy3TDdhywnRolFRP4pZ9k2Hpi1jG7tE5h19yh97b3UiRKLiFBaXsEv3lzFlH9s5Jz+3XjqlrNJ7tQm1mFJE6XEItLMbSk6zPiXFrOsoJix56fzH6NPJ6GVHtUkdafEItKMvbNyJ//+l2VUVjrPfOtsRp/ZK9YhSRxQYhFpho5WVPLrt1bzpw/WM6hPZ566ZTj9EjvEOiyJE0osIs3MjuISvvvyYhZu3MstI9P46TWZtG3dsvaGIlFSYhFpRj5cu5vvTV9KydEK/pA9lKyhupRY6p8Si0gzUFHp/OHdtTw+Zy0ZPTry1C1nM6BHx1iHJXFKiUUkzu0+UMr3Zyzh4/w9XD88hZ9fdybtE/RfXxqOfrtE4tj89Xv47stLKD5ylMe+MZgbQ6mY6atZpGEpsYjEoS1Fh5nyj438+eMN9EvswNQ7Rugpj3LSKLGIxInKSufD/EKm/WMjc1bvooUZXx+Wys+uzaRTW30rsZw8SiwiTVzxkaPMWlTA859sZOOewyR1TGD8xQP45sg0endpF+vwpBlSYhFpolbt2M+0Tzbx2uKtHDlawfC0rvzg8oGMPrMXbVrpvhSJnagSi5mNBv5A+Jn3z7n7L6tsbwNMA84G9gA3ufvGYNtDwFigArjP3Wcfr08z+xA49oi6HsACd7/OzC4C3gA2BNtedfcJdRizSJN1tKKS2Xk7mPbJJhZsKKJNqxZkDe3DrV/pz5kp+iZiaRxqTSxm1hJ4ErgcKAAWmlmOu6+MqDYW2OvuA8wsG3gUuMnMMoFsYBDQB3jHzAYGbart090viNj3K4STyTEfuvs1dR2sSFN1qLSc5z7cwEsLNrFzfyl9u7fjoStP519DfenWISHW4Yl8TjRHLCOAfHdfD2Bm04EsIDKxZAE/C5ZnAU9Y+JrGLGC6u5cCG8wsP+iP2vo0s07AJcDtdRuaSHzYfaCUO6Ys5NOtxXx1YDL//fV+XHRaDz3RURqtaBJLCrAlYr0AGFlTHXcvN7NiIDEon1el7bHvkKitz68D77r7/oiyr5jZMmAb8EN3z4sifpEma/3ug4z58wJ2HyjluVtDXJbZM9YhidQqmsRS3ccij7JOTeXVPeyhap83A89FrC8G+rn7QTO7CngdyPhCsGbjgHEAaWlp1exGpGlYvHkvY6csxMx4+TvnMiytW6xDEolKNE/zKQD6RqynEj5iqLaOmbUCugBFx2l73D7NLJHwKbP/PVbm7vvd/WCw/CbQ2sySqgbr7hPdPeTuoeTk5CiGJ9L4vL1yJ998dh6d27XmlXtGKalIkxJNYlkIZJhZupklEJ6Mz6lSJwcYEyzfAMxxdw/Ks82sjZmlEz7CWBBFnzcC/+PuJccKzKxXMG+DmY0IYt9zYsMVafxemLeJu57P5bSenXjlnlGkJ+k5KdK01HoqLJgzGQ/MJnxp8GR3zzOzCUCuu+cAk4Dng8n5IsKJgqDeTMKT8uXAve5eAVBdnxG7zQY+d0kz4YR1j5mVA0eA7CB5icQFd+c3b63hiffyufi0ZJ68Zbi+LFKaJIvnv82hUMhzc3NjHYZIrY5WVPLgK5/yyuICss/py8+vO5NWLfXceYkNM1vk7qG6ttfHIZEYO1hazj0vLOLDtYX84LKB3HfpAH0DsTRpSiwiMbRrfwm3T1nIqh0HeOwbg/nXc/rW3kikkVNiEYmR/F0HGTN5AXsPl/HcmBAXn9Yj1iGJ1AslFpEYWLSpiLFTc2nVwpg+7lwGp3aNdUgi9UaJReQk2rbvCI/PyecvuVvo2709U28fQVpi+1iHJVKvlFhEToJdB0p46r11vDR/M45zy8g0vn/ZQH2BpMQlJRaRBrT3UBl/mrueqf/YSFlFJTeencr4SwaQ2k1HKRK/lFhEGsCBkqNM+mgDkz7cwMGycrKG9OF7lw3UXfTSLCixiNSjw2XlTP3HJv40dx37Dh9l9KBe/ODygZzWq1PtjUXihBKLSD0oOVrByws28+R76yg8WMrFpyVz/+WncVaqnuoozY8Si8iX9MbSrfzyb6vYXlzCuad055lvDSfUv3uswxKJGSUWkTo6VFrOT99YwauLtzIktQu/uXEIowZ84UkOIs2OEotIHeRtK+a7Ly1h455DfO/SDO67NEOPChYJKLGInAB3Z9onm/iv//2Mbh1a8+Kd5/KVUxNjHZZIo6LEIhKlfYfLeGDWct5auZOLT0vm1zcOIbFjm1iHJdLoKLGIRGHRpiLue3kpuw6U8JOrz+CO89JpoVNfItVSYhE5jspK5+kP1vHbt9eQ0rUds+4exZC++sJIkeNRYhGpwa4DJdw/Yxkf5RdyzeDe/Pf1Z9G5betYhyXS6EX17FMzG21mq80s38werGZ7GzObEWyfb2b9I7Y9FJSvNrMrauvTzKaY2QYzWxq8hgblZmZ/DOovN7PhX2bgIsczd81urvrDh+RuKuKX15/F4zcPU1IRiVKtRyxm1hJ4ErgcKAAWmlmOu6+MqDYW2OvuA8wsG3gUuMnMMoFsYBDQB3jHzAYGbY7X54/cfVaVUK4EMoLXSODp4KdIvSktr+D376zl6ffXMbBnR176zrkM7KmvYxE5EdGcChsB5Lv7egAzmw5kAZGJJQv4WbA8C3jCwg/tzgKmu3spsMHM8oP+iKLPqrKAae7uwDwz62pmvd19exRjEDmuw2XlvLxgC8/OXc+O/SXcPCKNh6/JpF1Cy1iHJtLkRJNYUoAtEesFfPFI4Z913L3czIqBxKB8XpW2KcHy8fr8LzN7GHgXeDBITNXFkQJ8LrGY2ThgHEBaWloUw5PmrPjwUaZ9spHJH29g7+GjjEzvzq9uHMwFGcmxDk2kyYomsVR3TaVHWaem8urmdo71+RCwA0gAJgL/AUyIMg7cfWLQjlAo9IXtIhCemJ/00QZenLeZg6XlXHp6D/7t4lM5u5++40vky4omsRQAfSPWU4FtNdQpMLNWQBegqJa21ZZHnNoqNbM/Az88gThEjmtL0WEmzl3PjNwtlFdUcvXgPtzz1VPJ7NM51qGJxI1oEstCIMPM0oGthCfjv1mlTg4wBvgEuAGY4+5uZjnAS2b2W8KT9xnAAsJHH9X2eWzeJJijuQ5YEbGP8cF8zEigWPMrEq38XQd46v11vLF0Gy0MvjE8lbu+eqoevCXSAGpNLMGcyXhgNtASmOzueWY2Ach19xxgEvB8MDlfRDhRENSbSXhSvhy4190rAKrrM9jli2aWTDj5LAXuDsrfBK4C8oHDwO1fevQS9z4tKObJ9/KZvXIHbVu15LZR/bnzgnR6d2kX69BE4paFL7KKT6FQyHNzc2MdhsRAydEKfj17NZM+3kCnNq24bVR/bjsvne4dEmIdmkijZ2aL3D1U1/a6817izoqtxfxgxlLW7jrIrV/px4+uOI1OurlR5KRRYpG4UV5RyTMfrOP376wlsWMC0+4YwYUDddmwyMmmxCJxYUPhIe6fuZQlm/fxL0P68J9Zg+jaXqe9RGJBiUWaNHfnhXmb+O83V5HQqgV/vHkY1w7pE+uwRJo1JRZpsnYUl/DAK8uZu2Y3Fw5M5rFvDKZXl7axDkuk2VNikSYpZ9k2fvr6CsrKK/nP687kWyPTCN/6JCKxpsQiTcq+w2X89I08/rpsG0P7duV3Nw3VTY4ijYwSizQJ5RWVvLVyJ//3r3nsOVjGD782kLu/eiqtWkb1SCEROYmUWKRR27W/hOkLt/Dygs1sLy4ho0dHJo05hzNTusQ6NBGpgRKLNDruzifr9vDC/E28lbeT8krngowkHvmXQVx2Rg8dpYg0ckos0mgUHz7KrMUFvDh/E+t3H6Jr+9bcfl5/vjmyn+ZRRJoQJRaJuWVb9vHCvE38dfk2So5WMiytK7+5cQhXD+5N29Z6gqNIU6PEIjFRcrSCnKXbeGH+JpYXFNM+oSVfH5bKt85NY1AfzZ+INGVKLHJSVVQ6ry/Zym/fXsPWfUcY2LMjE7IGcd2wFDrriyJF4oISi5wU7s77a3bz6N9WsWrHAc5K6cKj3xjMeQMSdWOjSJxRYpEGt2zLPn7xt8+Yt76IfonteeKbw7jqzN60aKGEIhKPlFikwWwoPMSvZ6/mfz/dTmKHBCZkDSL7nDQSWulyYZF4psQi9W73gVL++O5aXl6wmYRWLbjv0gzGXXgKHdvo102kOYjqo6OZjTaz1WaWb2YPVrO9jZnNCLbPN7P+EdseCspXm9kVtfVpZi8G5SvMbLKZtQ7KLzKzYjNbGrwe/jIDl/p3sLSc3729hq/+6j1eWrCZ7BF9ef9HF3H/5QOVVESakVr/t5tZS+BJ4HKgAFhoZjnuvjKi2lhgr7sPMLNs4FHgJjPLBLKBQUAf4B0zGxi0qanPF4FvBXVeAu4Eng7WP3T3a+o+XGkIh8vK+UtuAY/PWUvhwTKuOqsXP/zaaZyS3DHWoYlIDETzMXIEkO/u6wHMbDqQBUQmlizgZ8HyLOAJC1/qkwVMd/dSYIOZ5Qf9UVOf7v7msU7NbAGQWsexSQNbs/MAL87bxKuLt3KgtJyR6d3l5YEMAAAMJklEQVR59tbTGZbWLdahiUgMRZNYUoAtEesFwMia6rh7uZkVA4lB+bwqbVOC5eP2GZwC+zbwvYjir5jZMmAb8EN3z6sarJmNA8YBpKWlRTE8ORFl5ZX8PW8HL8zbxIINRSS0bMFVZ/XilnP7EerXTZcOi0hUiaW6vxQeZZ2ayqub26na51PAXHf/MFhfDPRz94NmdhXwOpDxhU7cJwITAUKhUNU+pY62FB3m5QWbmZm7hcKDZaR1b8+DV57OjWenktixTazDE5FGJJrEUgD0jVhPJXzEUF2dAjNrBXQBimppW2OfZvYIkAzcdazM3fdHLL9pZk+ZWZK7F0YxBqmDikrn/dW7eGHeJt5fsxsDLj2jJ7eMTOPCjGTdhyIi1YomsSwEMswsHdhKeDL+m1Xq5ABjgE+AG4A57u5mlgO8ZGa/JTx5nwEsIHwkU22fZnYncAVwqbtXHtuBmfUCdgb9jiB81LOnbsOW4yk8WMqMhVt4af5mtu47QnKnNnz34gFkj0ijT9d2sQ5PRBq5WhNLMGcyHpgNtAQmu3uemU0Act09B5gEPB9MzhcRThQE9WYSnugvB+519wqA6voMdvkMsAn4JDhf/6q7TyCcsO4xs3LgCJDt7jrVVY/W7z7Isx9u4JXFBZSVVzLq1ER+fPUZXJ7Zk9Z6BoqIRMni+W9zKBTy3NzcWIfR6C3ZvJc/fbCe2St30LplC244O5U7zktnQA9dLizSHJnZIncP1bW97lprpiornffX7OKZD9azYEMRndu24t6LBjBmVH+SO2kyXkTqTomlmSkrryRn2TYmzl3Hmp0HSenajoevyeSmc/rSQXfHi0g90F+SZuJAyVGmL9jCpI82sGN/Caf36sTvbxrK1YN7a/5EROqVEkucK9h7mBfnb+aFeZs4UFLOqFMTefSGwVyYkaSbGUWkQSixxKHiI0d589PtvLZ4Kws2FtHC4MqzenPXhacwOLVrrMMTkTinxBInysoreX/1Ll5bspV3P9tFWUUlpyZ34EdXnEbW0D6kdmsf6xBFpJlQYmnC3J3Fm/fy2pKt/M/y7ew7fJSkjgnccm4a1w9L5cyUzjrdJSInnRJLE7Sh8BCvLdnK60u2srnoMG1bt+Brmb34+vAULhiQRCtNxotIDCmxNBH7Dpfx1+XbeXVxAUs278MMRp2ayH2XZjD6zF56kJaINBr6a9SIHZs3eXXxVt5dtZOjFc5pPTvx0JWnkzU0hV5d2sY6RBGRL1BiaWTcnU+3FvPq4q3kLNtG0aEykjomcOtX+nP98BQye2veREQaNyWWRmJ78RFeW7KVVxdvJX/XQRJateDyzJ58Y3gKF2Qk6yZGEWkylFhi6FBpObPzdvDq4q18vK4Qdwj168Yvrj+Lq87qTZd2rWMdoojICVNiOcl2Hyjl3c928vbKnXyUX0hpeSV9u7fjvksyuH54Cv0SO8Q6RBGRL0WJpYG5O+t2H+StlTt5Z+VOlmzZhzukdG3HzSPSuOqs3pzTX8+KF5H4ocTSACoqwzcuvr0yfGSyofAQAGeldOEHlw3k8syenN6rk5KJiMQlJZZ6cqi0nI/yC3l75U7mrNpF0aEyWrc0vnJqEnecn85lZ/Sgdxc91ldE4l9UicXMRgN/IPwY4efc/ZdVtrcBpgFnE34O/U3uvjHY9hAwFqgA7nP32cfr08zSgelAd2Ax8G13LzvePmLhaEUly7bs46P8Qj7OL2TJ5n2UVzqd27bi4tN7cHlmT746MJlObTUBLyLNS62JxcxaAk8ClwMFwEIzy3H3lRHVxgJ73X2AmWUDjwI3mVkmkA0MAvoA75jZwKBNTX0+CvzO3aeb2TNB30/XtI8v+wZEy91ZvfMAH+fv4eP8Quav38OhsgrMYHBKF75z4SlcMCCJc9K769JgEWnWojliGQHku/t6ADObDmQBkYklC/hZsDwLeMLCEwhZwHR3LwU2mFl+0B/V9WlmnwGXAN8M6kwN+n26pn24u5/IgE/E1n1H+Dg4Ivk4fw+FB0sBOCWpA9cPT+W8AYmce0oiXdsnNFQIIiJNTjSJJQXYErFeAIysqY67l5tZMZAYlM+r0jYlWK6uz0Rgn7uXV1O/pn0URjGGE7K8YB/fm770n5PuSR3bcP6AREYNSOK8AUmkdNVciYhITaJJLNVdulT1KKGmOjWVV3eu6Hj1o40DMxsHjANIS0urpknt+nRtR3pSB751bj/OH5DEwJ4ddQWXiEiUokksBUDfiPVUYFsNdQrMrBXQBSiqpW115YVAVzNrFRy1RNavaR+f4+4TgYkAoVCoTqfJkjq2YfJt59SlqYhIsxfNLPNCIMPM0s0sgfBkfE6VOjnAmGD5BmBOMPeRA2SbWZvgaq8MYEFNfQZt3gv6IOjzjVr2ISIijUitRyzBfMZ4YDbhS4Mnu3uemU0Act09B5gEPB9MzhcRThQE9WYSnugvB+519wqA6voMdvkfwHQz+zmwJOibmvYhIiKNi8Xzh/5QKOS5ubmxDkNEpEkxs0XuHqpre91wISIi9UqJRURE6pUSi4iI1CslFhERqVdKLCIiUq/i+qowM9sNbKpj8yQa4OtimojmPHZo3uNvzmOH5j3+yLH3c/fkunYU14nlyzCz3C9zuV1T1pzHDs17/M157NC8x1+fY9epMBERqVdKLCIiUq+UWGo2MdYBxFBzHjs07/E357FD8x5/vY1dcywiIlKvdMQiIiL1SomlCjMbbWarzSzfzB6MdTz1xcwmm9kuM1sRUdbdzN42s7XBz25BuZnZH4P3YLmZDY9oMyaov9bMxlS3r8bGzPqa2Xtm9pmZ5ZnZ94LyuB+/mbU1swVmtiwY+/8NytPNbH4wjhnB4ysIHnExIxj7fDPrH9HXQ0H5ajO7IjYjOnFm1tLMlpjZ/wTrzWnsG83sUzNbama5QVnD/967u17Bi/BX+K8DTgESgGVAZqzjqqexXQgMB1ZElD0GPBgsPwg8GixfBfyN8FM7zwXmB+XdgfXBz27BcrdYjy2KsfcGhgfLnYA1QGZzGH8who7BcmtgfjCmmUB2UP4McE+w/G/AM8FyNjAjWM4M/j+0AdKD/yctYz2+KN+D+4GXgP8J1pvT2DcCSVXKGvz3XkcsnzcCyHf39e5eBkwHsmIcU71w97l88YmbWcDUYHkqcF1E+TQPm0f4qZ69gSuAt929yN33Am8Doxs++i/H3be7++Jg+QDwGZBCMxh/MIaDwWrr4OXAJcCsoLzq2I+9J7OAS83MgvLp7l7q7huAfML/Xxo1M0sFrgaeC9aNZjL242jw33slls9LAbZErBcEZfGqp7tvh/AfX6BHUF7T+9Dk35/g9MYwwp/cm8X4g1NBS4FdhP8orAP2efjx3/D5cfxzjMH2YiCRJjp24PfAA0BlsJ5I8xk7hD9EvGVmi8xsXFDW4L/30Tzzvjmxasqa42VzNb0PTfr9MbOOwCvA9919f/jDaPVVqylrsuP38FNbh5pZV+A14IzqqgU/42bsZnYNsMvdF5nZRceKq6kad2OPcJ67bzOzHsDbZrbqOHXrbfw6Yvm8AqBvxHoqsC1GsZwMO4NDXYKfu4Lymt6HJvv+mFlrwknlRXd/NShuNuMHcPd9wPuEz593NbNjHywjx/HPMQbbuxA+hdoUx34ecK2ZbSR8WvsSwkcwzWHsALj7tuDnLsIfKkZwEn7vlVg+byGQEVw1kkB4Ai8nxjE1pBzg2BUeY4A3IspvDa4SORcoDg6ZZwNfM7NuwZUkXwvKGrXgPPkk4DN3/23Eprgfv5klB0cqmFk74DLCc0zvATcE1aqO/dh7cgMwx8MzuDlAdnDlVDqQASw4OaOoG3d/yN1T3b0/4f/Lc9z9FprB2AHMrIOZdTq2TPj3dQUn4/c+1lctNLYX4Ssj1hA+D/3jWMdTj+N6GdgOHCX8CWQs4fPH7wJrg5/dg7oGPBm8B58CoYh+7iA8eZkP3B7rcUU59vMJH7ovB5YGr6uaw/iBwcCSYOwrgIeD8lMI/3HMB/4CtAnK2wbr+cH2UyL6+nHwnqwGroz12E7wfbiI/39VWLMYezDOZcEr79jfs5Pxe68770VEpF7pVJiIiNQrJRYREalXSiwiIlKvlFhERKReKbGIiEi9UmIREZF6pcQiIiL1SolFRETq1f8D2IVeV7ry/CQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Test insertion sort on randomly-sorted lists of different size,\n",
    "# and plot the results\n",
    "\n",
    "N_values = list(range(10,5000,200))\n",
    "time_values = []\n",
    "\n",
    "for N in N_values:\n",
    "    input_list = random_list(N)\n",
    "    time_taken = time_sort(isort, input_list)\n",
    "    time_values.append(time_taken)\n",
    "\n",
    "plt.plot(N_values, time_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that above we can get extra randomness in our timings due to the randomness in the input lists - some inputs were harder to sort than others. How could you improve this test?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Selection sort "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The selection sort algorithm similar to the insertion sort algorithm discussed in lectures, but even simpler to implement. Here is a version of the algorithm in words:\n",
    "\n",
    "1. Initialise the sorted list as an empty list\n",
    "2. Search the original list for the smallest element\n",
    "3. Remove this element from the original list and insert it at the end of the sorted list \n",
    "4. Repeat from step 2 until the unsorted list is empty\n",
    "\n",
    "Since we built the sorted list from the smallest to the largest element, we can just add each new element on to the end."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Challenge:** \n",
    "\n",
    "Think theoretically: what do you expect the upper-bound (big-O) asymptotic complexity of selection sort to be?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Challenge:** \n",
    "\n",
    "1. Implement selection sort below. \n",
    "2. Draw plots similar to the insertion sort plots above to test the behaviour of selection sort with random, inverted, and nearly-sorted lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(unsorted):\n",
    "    # Replace the code below so that we sort the list instead\n",
    "    # of just returning the original list\n",
    "    sorted_list = []\n",
    "    \n",
    "    \"\"\"\n",
    "    Sort a list using selection sort\n",
    "    \"\"\"\n",
    "    \n",
    "    # while the unsorted list is not exhausted\n",
    "    while len(unsorted) > 0:\n",
    "        # position of the smallest item\n",
    "        min_index = 0\n",
    "        # find the smallest item in the remaining list\n",
    "        for index in range(1, len(unsorted)):\n",
    "            # if a value is smaller than the current, replace the index\n",
    "            if unsorted[index] < unsorted[min_index]:\n",
    "                min_index = index\n",
    "        # add the smallest item to the sorted list\n",
    "        sorted_list.append(unsorted[min_index])\n",
    "        # remove the smallest item from the unsorted list (+ concatenates lists)\n",
    "        unsorted = unsorted[:min_index] + unsorted[(min_index + 1):]\n",
    "    return sorted_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 3, 4, 5, 7, 22]\n"
     ]
    }
   ],
   "source": [
    "x = [5,3,7,22,4,3]\n",
    "print(selection_sort(x))\n",
    "assert selection_sort(x) == sorted(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f66a760bbe0>]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAD8CAYAAAB3u9PLAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xl8VPXZ9/HPRSAhQNhJ2JewCoosA4q9RetKvavYqgVqESwFSutt27vLrd1rn6fVej+21SpKQRRccG+pa7WuaAUSQBZZDAQh7JEtAUK26/ljDhoikAlZziT5vl+vec2ZM79zzjWZyXzn/M5m7o6IiEijsAsQEZH4oEAQERFAgSAiIgEFgoiIAAoEEREJKBBERARQIIiISECBICIigAJBREQCjWNpZGZjgD8DCcBsd7+93PNJwDxgOPAJMM7dN5vZpcDtQCJQCPzY3V8PpnkT6AQcCWZzmbvvPlUd7du39549e8b2ykREBIDMzMxcd+9QUbsKA8HMEoB7gUuBHGCpmS109w/LNJsC7HP3PmY2HrgDGAfkAle6+3YzOxN4BehSZrrr3T0j1hfVs2dPMjJibi4iIoCZfRxLu1i6jEYCWe6+yd0LgQXA2HJtxgIPB8NPAxebmbn7cnffHoxfAzQN1iZERCTOxBIIXYCtZR7ncPyv/OPauHsxcABoV67NNcBydz9aZtxcM1thZr8wMzvRws1smpllmFnGnj17YihXRERORyyBcKIv6vKnSD1lGzMbRLQbaXqZ569397OA84PbxBMt3N1nuXvE3SMdOlTYBSYiIqcplkDIAbqVedwV2H6yNmbWGGgF7A0edwWeA25w943HJnD3bcF9HvAY0a4pEREJSSyBsBToa2a9zCwRGA8sLNdmITApGL4WeN3d3cxaAy8At7r7u8cam1ljM2sfDDcBvgysrtpLERGRqqgwEIJtAjcR3UNoLfCku68xs9vM7Kqg2RygnZllAf8N3BKMvwnoA/wi2FawwsxSgSTgFTNbCawAtgF/rc4XJiIilWN16YppkUjEtdupiEjlmFmmu0cqaqcjlUVE4timPfnc+co6Skpr/se7AkFEJE7l5h9l8tylPL5kK7vzCmp8eQoEEZE4dLiwmCkPLWV3XgFzJkXo1Cq5xpepQBARiTPFJaXc/PhyVm07wD0ThjG0e5taWW5MJ7cTEZHa4e78+h9reG3tbn47dhCXDkyrtWVrDUFEJI7MfGsjj7y/hekXpDNxVM9aXbYCQUQkTvx9xTb+8PJ6rjq7M/9z+YBaX74CQUQkDry3MZcfPfUB56a35c7rBtOo0QnP91mjFAgiIiFbvzOP6fMz6dmuOQ9MjJDUOCGUOhQIIiIh2nmggMlzl5DcJIGHvjmSVslNQqtFgSAiEpK8giImz13CwSNFzL1xBF1a1/yxBqei3U5FREJQWFzKjEeWkbU7nwcnj2BQ51Zhl6RAEBGpbe7OLc+uZFFWLndeO5jR/eLj4l/qMhIRqWV/fHUDzy7bxg8u6cd1kW4VT1BLFAgiIrVowZIt3P16FuMi3bj54j5hl3McBYKISC15Y/1ufva31Yzu14H/85UzMav9Yw1ORYEgIlILVuUc4LuPLmNAxxTuu34YTRLi7+s3/ioSEalntu49zI0PLaVNs0TmTh5Bi6T43J8nPqsSEakn9h8uZPLcJRQWl7Bg2jmktmwadkknpUAQEakhBUUlTJ2Xwda9R5g/ZSR9UlPCLumUFAgiIjWgtNT54VMfsHTzPu6ZMJRz0tuFXVKFtA1BRKQG/P6ltbywcgc/vWIAV57dOexyYqJAEBGpZnPfzeav72QzaVQPpp6fHnY5MVMgiIhUo5dX7+C25z/ksoFp/PLKQXF3rMGpKBBERKpJ5sd7+d6CFQzp1po/jx9KQggXuakKBYKISDXYtCefbz2cQadWTZl9Q4TkxHAuclMVCgQRkSrKzT/K5LlLMTMeunEk7VokhV3SaVEgiIhUweHCYqY8tJTdeQXMmRShZ/vmYZd02hQIIiKnqbiklP96bDmrth3gngnDGNq9TdglVYkOTBMROQ3uzq8WruFf63bz27GDuHRgWtglVZnWEERETsPMtzby6OItTL8gnYmjeoZdTrVQIIiIVNLfV2zjDy+v56qzO/M/lw8Iu5xqE1MgmNkYM1tvZllmdssJnk8ysyeC5xebWc9g/KVmlmlmq4L7i8pMMzwYn2Vmd1tdOnpDRBqs9zbm8qOnPuDc9Lbced1gGtWxYw1OpcJAMLME4F7gS8BAYIKZDSzXbAqwz937AH8E7gjG5wJXuvtZwCRgfplpZgLTgL7BbUwVXoeISI1bvzOP6fMy6dmuOQ9MjJDUuO4da3AqsawhjASy3H2TuxcCC4Cx5dqMBR4Ohp8GLjYzc/fl7r49GL8GaBqsTXQCWrr7v93dgXnA1VV+NSIiNWTngQImz11CcmICD31zJK2Sm4RdUrWLJRC6AFvLPM4Jxp2wjbsXAweA8ud6vQZY7u5Hg/Y5FcwTADObZmYZZpaxZ8+eGMoVEaleeQVFTJ67hINHiph74wi6tE4Ou6QaEUsgnKiDzCvTxswGEe1Gml6JeUZHus9y94i7Rzp06BBDuSIi1aewuJQZjywja3c+M78xnEGdW4VdUo2JJRBygG5lHncFtp+sjZk1BloBe4PHXYHngBvcfWOZ9l0rmKeISKjcnVueXcmirFx+/9WzGN2vfv8ojSUQlgJ9zayXmSUC44GF5dosJLrRGOBa4HV3dzNrDbwA3Oru7x5r7O47gDwzOzfYu+gG4O9VfC0iItXqj69u4Nll2/jBJf24LtKt4gnquAoDIdgmcBPwCrAWeNLd15jZbWZ2VdBsDtDOzLKA/waO7Zp6E9AH+IWZrQhuqcFzM4DZQBawEXipul6UiEhVPb5kC3e/nsW4SDduvrhP2OXUCovu5FM3RCIRz8jICLsMEann3li/m289nMEX+rRnzqQITRLq9jG8Zpbp7pGK2tXtVykiUs1W5Rzgu48uY0DHFO67flidD4PKaDivVESkAlv3HubGh5bSplkicyePoEVSwzr/Z8N6tSIiJ7H/cCGT5i6hsLiEBdPOIbVl07BLqnUKBBFp8AqKSpg6L4OcvUeYP2UkfVJTwi4pFAoEEWnQSkudHz75AUs37+OeCUM5J738SRYaDm1DEJEG7XcvruWFVTv46RUDuPLszmGXEyoFgog0WHPfzWb2omwmjerB1PPTwy4ndAoEEWmQXl69g9ue/5DLBqbxyysHoUuyKBBEpAHK/Hgv31uwgiHdWnP3hKEk1KOL3FSFAkFEGpRNe/L51sMZdGrVlNk3RGjapH5d5KYqFAgi0mDk5h9l8tylmBkP3TiSdi2Swi4prigQRKRBOFxYzJSHlrI7r4A5kyL0bN887JLijgJBROq94pJS/uux5azadoB7JgxjaPc2YZcUl3RgmojUa+7Orxau4V/rdvPbsYO4dGBa2CXFLa0hiEi9NvOtjTy6eAvfvqA3E0f1DLucuKZAEJF662/Lt/GHl9dz1dmd+cnl/cMuJ+4pEESkXnovK5cfP/0B56a35c7rBtNIxxpUSIEgIvXO+p15TJ+fSc92zXlgYoSkxjrWIBYKBBGpV3YeKGDy3CUkJybw0DdH0iq5Sdgl1RkKBBGpN/IKipg8dwkHjxQx98YRdGmdHHZJdYp2OxWReqGwuJQZjywja3c+D04ewaDOrcIuqc5RIIhInefu3PLsShZl5XLntYMZ3a9D2CXVSeoyEpE6765XN/Dssm384JJ+XBfpFnY5dZYCQUTqtMeXbOGe17MYF+nGzRf3CbucOk2BICJ11hvrd/Pzv61mdL8O/J+vnKmL3FSRAkFE6qRVOQf47qPLGNAxhfuuH0aTBH2dVZX+giJS52zde5gbH1pKm2aJzJ08ghZJ2j+mOuivKCJ1yv7DhUyau4TC4hIWTDuH1JZNwy6p3lAgiEidUVBUwtR5GeTsPcL8KSPpk5oSdkn1igJBROqE0lLnh09+wNLN+7hnwlDOSW8Xdkn1jrYhiEid8LsX1/LCqh389IoBXHl257DLqZcUCCIS9+a+m83sRdlMGtWDqeenh11OvRVTIJjZGDNbb2ZZZnbLCZ5PMrMngucXm1nPYHw7M3vDzPLN7C/lpnkzmOeK4JZaHS9IROqXl1fv4LbnP+SygWn88spBOtagBlW4DcHMEoB7gUuBHGCpmS109w/LNJsC7HP3PmY2HrgDGAcUAL8Azgxu5V3v7hlVfA0iUk9lfryX7y1YwZBurbl7wlASdJGbGhXLGsJIIMvdN7l7IbAAGFuuzVjg4WD4aeBiMzN3P+Tui4gGg4hIzDbtyedbD2fQqVVTZt8QoWkTXeSmpsUSCF2ArWUe5wTjTtjG3YuBA0AsuwDMDbqLfmEnWQ80s2lmlmFmGXv27IlhliJS1+3JO8qkuUtoZMbD3xxJuxZJYZfUIMQSCCf6ovbTaFPe9e5+FnB+cJt4okbuPsvdI+4e6dBBp7QVqe8OFxYz5eGl7Mk7ypzJI+jRrnnYJTUYsQRCDlD2fLJdge0na2NmjYFWwN5TzdTdtwX3ecBjRLumRKQBKy4p5b8eW87qbQe4Z8IwhnRrHXZJDUosgbAU6GtmvcwsERgPLCzXZiEwKRi+Fnjd3U+6hmBmjc2sfTDcBPgysLqyxYtI/eHu/GrhGv61bje/uWoQlw5MC7ukBqfCvYzcvdjMbgJeARKAB919jZndBmS4+0JgDjDfzLKIrhmMPza9mW0GWgKJZnY1cBnwMfBKEAYJwGvAX6v1lYlInTLzrY08ungL376gNxNH9Qy7nAYpplNXuPuLwIvlxv2yzHABcN1Jpu15ktkOj61EEanv/rZ8G394eT1Xnd2Zn1zeP+xyGiwdqSwioXovK5cfP/0B56a35c7rBtNIxxqERoEgIqFZt/Mg0+dn0qt9cx6YGCGpsY41CJMCQURCsePAEW6cu5RmSQnMvXEkrZKbhF1Sg6dAEJFal1dQxI1zl3LwSBEPTh5Bl9bJYZck6HoIIlLLCotLmfHIMrJ25/Pg5BEM6twq7JIkoEAQkVqTV1DE9xesYFFWLndeO5jR/XT2gXiiQBCRWpGde4ip8zLIzj3Eb8cO4rpIt4onklqlQBCRGvf2hj3c9NgyEhoZ86eM5Lze7cMuSU5AgSAiNcbdmbMom9+9uJZ+aSn89YYI3do2C7ssOQkFgojUiIKiEn763CqeXbaNywelcdfXhtA8SV858UzvjohUu10HC5g2P5MPtu7n+5f05eaL+uoI5DpAgSAi1Wr5ln1Mn59J/tFi7v/GcMac2THskiRGCgQRqTZPZ+bw02dXkdYqiXlTzmNAx5ZhlySVoEAQkSorLinl9y+tY86ibM7r3Y57vz6MNs0Twy5LKkmBICJVcuBwETc9vox3Pspl8nk9+dl/nkGTBJ0Vpy5SIIjIaftoVx5T52Wwbf8R7rjmLMaN6B52SVIFCgQROS2vfriL7y9YTnJiYxZMO5fhPdqGXZJUkQJBRCrF3bn3jSz+36sbOLNzKx6YOJzOOltpvaBAEJGYHS4s5sdPreSFVTsYO6Qzd1wzmKZNdFGb+kKBICIxydl3mGnzMlm78yC3fmkA00anY6aDzeoTBYKIVGjxpk/4zqPLKCwp5cHJI/hi/9SwS5IaoEAQkVN65P2P+fXCNXRv24y/TorQu0OLsEuSGqJAEJETKiwu5Tf/WMOji7dwYf8O/Hn8UF33uJ5TIIjI5+TmH+U7jyxjyea9TL8gnZ9cPoAEnZyu3lMgiMhx1mw/wLR5meTmH+VP44Zw9dAuYZcktUSBICKfen7ldn701Ae0Tk7kqW+PYnDX1mGXJLVIgSAilJY6d726gb+8kcXwHm2Y+Y1hpKY0DbssqWUKBJEGLq+giB88sYLX1u5mXKQbt109iKTGOtisIVIgiDRgm3MPMXVeBptyD/GbqwZxw6geOtisAVMgiDRQb2/Yw02PLaNRI2P+N0dyXp/2YZckIVMgiDQw7s6cRdn87sW19E1N4a83ROjerlnYZUkcUCCINCAFRSX87LnVPLMsh8sHpXHX14bQPElfAxIV02WNzGyMma03sywzu+UEzyeZ2RPB84vNrGcwvp2ZvWFm+Wb2l3LTDDezVcE0d5s6LkVq1K6DBYyf9T7PLMvhexf3Zeb1wxUGcpwKA8HMEoB7gS8BA4EJZjawXLMpwD537wP8EbgjGF8A/AL40QlmPROYBvQNbmNO5wWISMWWb9nHlfcsYsOuPO7/xjB+cGk/GunIYyknljWEkUCWu29y90JgATC2XJuxwMPB8NPAxWZm7n7I3RcRDYZPmVknoKW7/9vdHZgHXF2VFyIiJ/ZMZg7jZr1PUpNGPPud8xhzZqewS5I4Fcv6Yhdga5nHOcA5J2vj7sVmdgBoB+SeYp455eZ5wuPjzWwa0TUJunfX9VpFYlVcUsrtL61j9qJsRqW3497rh9G2eWLYZUkciyUQTrRe6afR5rTau/ssYBZAJBI51TxFJHDgcBE3Pb6Mdz7KZdKoHvz8ywNpkhDTJkNpwGIJhBygW5nHXYHtJ2mTY2aNgVbA3grm2bWCeYrIafhoVx5T52Wwbf8Rbv/qWYwfqTVriU0sPxmWAn3NrJeZJQLjgYXl2iwEJgXD1wKvB9sGTsjddwB5ZnZusHfRDcDfK129iBzntQ938ZX73iP/aDGPTz1XYSCVUuEaQrBN4CbgFSABeNDd15jZbUCGuy8E5gDzzSyL6JrB+GPTm9lmoCWQaGZXA5e5+4fADOAhIBl4KbiJyGlwd+57cyP/+8/1DOrcklkTI3RunRx2WVLH2Cl+yMedSCTiGRkZYZchElcOFxbz46dX8sLKHYwd0pnbvzqY5ESdnE4+Y2aZ7h6pqJ2OShGpw7btP8LUhzNYu/Mgt3xpANNHp+vkdHLaFAgiddTiTZ/wnUeXUVhcyoOTRvDFAalhlyR1nAJBpA565P2P+fXCNXRv24xZN0Tok9oi7JKkHlAgiNQhhcWl/OYfa3h08RYu6NeBuycMpVVyk7DLknpCgSBSR3ySf5QZjy5jSfZepo9O5ydjBpCg8xFJNVIgiNQBa7YfYNq8THLzj/KncUO4eugJz/QiUiUKBJE498LKHfzoqQ9oldyEp749isFdW4ddktRTCgSROFVa6vzxtQ3c83oWw7q35v6Jw0lNaRp2WVKPKRBE4lBeQRE/eGIFr63dzdciXfnt1WeS1FgHm0nNUiCIxJnNuYeYOi+DTbmH+PWVA5l0Xk8dbCa1QoEgEkfe+WgPNz22HDOY982RfKFP+7BLkgZEgSASB9ydOYuy+d2La+mT2oLZN4yge7tmYZclDYwCQSRkBUUl/Oy51TyzLIfLBqZx17ghtEjSv6bUPn3qREK0+2AB0+ZnsmLrfm6+uC/fv7gvjXSwmYREgSASkhVb9zN9fgZ5BcXMvH4YXzqrU9glSQOnQBAJwTOZOdz63CpSU5J4ZsZ5nNGpZdgliSgQRGpTcUkpt7+0jtmLsjk3vS33XT+cts0Twy5LBFAgiNSaA4eLuOnxZbzzUS6TRvXg518eSJOEWC5rLlI7FAgitSBrdx7fejiDbfuP8PuvnsWEkd3DLknkcxQIIjXsX2t38b0FK2japBGPTT2XET3bhl2SyAkpEERqiLtz35sb+d9/rmdQ55Y8MDFCl9bJYZclclIKBJEacLiwmJ88vZLnV+7gqrM7c8c1g0lO1MnpJL4pEESq2bb9R5j6cAZrdx7kf8YM4NsXpOvkdFInKBBEqtGS7L3MeCSTwuJS5kyKcNGAtLBLEomZAkGkmjy6+GN+9fc1dG/bjFk3ROiT2iLskkQqRYEgUkVFJaX85h9reOT9LVzQrwN3TxhKq+QmYZclUmkKBJHTVFRSyj8+2M7MNzfy0e58po9O5ydjBpCgk9NJHaVAEKmkgqISnli6lVlvb2Lb/iMM6JjCAxOHc/mgjmGXJlIlCgSRGB04UsQj73/Mg4uy+eRQIcN7tOG2sYO4aECq9iKSekGBIFKBPXlHmbMom0ff/5i8o8Vc0K8D37mwNyN7tVUQSL2iQBA5ia17D/PA2xt5MiOHopJSrjirEzMu6M2ZXVqFXZpIjYgpEMxsDPBnIAGY7e63l3s+CZgHDAc+Aca5++bguVuBKUAJcLO7vxKM3wzkBeOL3T1SDa9HpMrW78xj5ptZ/GPlDhoZXDOsK9Mv6E2v9s3DLk2kRlUYCGaWANwLXArkAEvNbKG7f1im2RRgn7v3MbPxwB3AODMbCIwHBgGdgdfMrJ+7lwTTfdHdc6vx9YictsyP9zHzzSxeW7ubZokJ3HheT751fjodWzUNuzSRWhHLGsJIIMvdNwGY2QJgLFA2EMYCvw6Gnwb+YtHO1bHAAnc/CmSbWVYwv39XT/kiVePuvP1RLve9kcXi7L20btaE71/Sl0mjetJGF66RBiaWQOgCbC3zOAc452Rt3L3YzA4A7YLx75ebtksw7MA/zcyBB9x9VuXLFzk9JaXOy6t3MvOtLFZvO0jHlk35+X+ewYSR3WmepE1r0jDF8sk/0W4UHmObU037BXffbmapwKtmts7d3/7cws2mAdMAunfXRUWkagqLS3lueQ4PvLWJTbmH6NW+OXdccxZXD+1CUmOdjVQatlgCIQfoVuZxV2D7SdrkmFljoBWw91TTuvux+91m9hzRrqTPBUKw5jALIBKJlA8ikZgcOlrM40u2MPudbHYeLGBQ55bc+/VhjDmzo44sFgnEEghLgb5m1gvYRnQj8dfLtVkITCK6beBa4HV3dzNbCDxmZncR3ajcF1hiZs2BRu6eFwxfBtxWLa9IpIz9hwt56L3NPPTeZvYfLuKcXm2549rBjO7bXscQiJRTYSAE2wRuAl4hutvpg+6+xsxuAzLcfSEwB5gfbDTeSzQ0CNo9SXQDdDHwXXcvMbM04LngH7Ix8Ji7v1wDr08aqJ0HCpj9ziYeW7KFw4UlXHJGKjMu7MPwHm3CLk0kbpl73emFiUQinpGREXYZEseycw/xwFsbeWZZDqUOV53dmW9f0Jv+HVPCLk0kNGaWGcuxXtqdQuqF1dsOMPOtjby0ageNExoxfkR3po1Op1vbZmGXJlJnKBCkznJ3lmTv5b43N/LWhj20SGrMtNG9+eZ/9CQ1RQeTiVSWAkHqHHfn9XW7ue/NjWR+vI92zRP58eX9+ca5PXRhGpEqUCBInVFcUsoLq3Yw882NrNuZR5fWydw2dhBfi3SjaRMdQyBSVQoEiXsFRSU8nZnDrLc3sWXvYfqmtuCur53NlWd3pklCo7DLE6k3FAgSt/IKinjk/S3MWZRNbv5RhnRrzc//8wwuOSONRjqYTKTaKRAk7nySf5S5727m4X9vJq+gmPP7tmfGhUMYld5OB5OJ1CAFgsSNnH2Hmf1ONguWbuFocSljBnVkxoW9Gdy1ddiliTQICgQJ3Ue78pj51kYWroieIusrQ7sw/YLe9EltEXJlIg2LAkFCs2Lrfu57I4t/friL5CYJTBzVg6nnp9O5dXLYpYk0SAoEqVXuzrtZnzDzrSzezfqElk0bc/NFfZj8hV601QVpREKlQJBaUVrq/PPDncx8cyMf5BwgNSWJn14xgK+f04MWuiCNSFzQf6LUqKKSUv62fBv3v7WRjXsO0aNdM373lbO4ZrguSCMSbxQIUiOOFJawYOkW/vr2JrYfKOCMTi25Z8JQrjirky5IIxKnFAhSrQ4cLmLevzcz973N7D1UyIiebfi/XzmLC/t30DEEInFOgSDVYvfBAuYsyubRxVvIP1rMRQNSmXFhb0b0bBt2aSISIwWCVMmWTw5z/9sbeTozh+KSUr48uDMzLuzNGZ1ahl2aiFSSAkFOy9odB5n55kaeX7mdxo0acW2kK9NHp9OjXfOwSxOR06RAkErJ2By9IM3r63bTPDGBqeenM+U/epHaUhekEanrFAhSIXfnzQ17mPnGRpZs3kvb5on88NJ+3DCqJ62a6YI0IvWFAkFOqqTUeTG4IM2HOw7SuVVTfnXlQMaN6EazRH10ROob/VfL5xQUlfDc8m088NZGNn9ymN4dmnPntYMZO6QLiY11QRqR+kqB0ICVljpb9x1m/c686G1X9D479xDFpc7grq24/xvDuGxgR12QRqQBUCA0AO5Obn5hmS/9g6zflc9Hu/I4XFjyabvubZvRLy2Fywd15Lze7RjVWxekEWlIFAj1TP7RYjYEv/TL/vLfe6jw0zbtWyTSv2MK40Z0Y0DHFPp3bEnf1BY010nmRBo0fQPUUYXFpWzKzf/cF3/OviOftmmWmEC/tBQuG5hG/44p9E9LoV/HFNq3SAqxchGJVwqEOFda6uTsO3JcV8/6nQfZtCfazw/QuJHRu0MLhnVvw4SR3emflkL/jil0aZ2svn8RiZkCIY7k5h897hf/ul15n+vn79ommQEdU7h0YBr90lIY0LElvdo3194/IlJlCoQQHOvn37Azj3U78z7t8/+kTD9/u+bRfv6vRaL9/P06ptAvLUUXkxGRGqNvlxpUWFxKdu4h1u08+NmG3l15bN17fD9/37QULjkjjX4dU6Jf/mkpdEhRP7+I1C4FQjUoLXW27T9y3L7863fmsSk3n6KSz/r50zs05+yurRkX6fZpd0/XNurnF5H4oECopE+Cfv5jXT3rdkb7+Q+V6efv0jraz3/RGamf/uJP79Bcl4wUkbgWUyCY2Rjgz0ACMNvdby/3fBIwDxgOfAKMc/fNwXO3AlOAEuBmd38llnmG7dCxfv5dx/fz5+Z/1s/fplkT+ndM4brgF3//jin0S2tBSlOd8E1E6p4KA8HMEoB7gUuBHGCpmS109w/LNJsC7HP3PmY2HrgDGGdmA4HxwCCgM/CamfULpqlonrWiqORYP3+wW+fOfNbvOnhcP39ykwT6pbXgi/1To/vzB7cOLZJ0JK+I1BuxrCGMBLLcfROAmS0AxgJlv7zHAr8Ohp8G/mLRb8qxwAJ3Pwpkm1lWMD9imGe1cg/25y/Tz79hVx4b93zWz5/QyOjVvjmDu7bmuuHd6B9s5O3Wppn6+UWk3oslELoAW8s8zgHOOVkbdy82swNAu2D8++Wm7RIMVzSjcSRhAAAGO0lEQVTPajPloaUszt5L/tHizwpunUy/tBZc2D+V/h1b0D+tJb1T1c8vIg1XLIFwop/GHmObk40/0VFU5ecZnbHZNGAaQPfu3U9e5Sn0aNecLm2SP/3F3zcthZbq5xcROU4sgZADdCvzuCuw/SRtcsysMdAK2FvBtBXNEwB3nwXMAohEIicMjYr88sqBpzOZiEiDEsv5DpYCfc2sl5klEt1IvLBcm4XApGD4WuB1d/dg/HgzSzKzXkBfYEmM8xQRkVpU4RpCsE3gJuAVoruIPujua8zsNiDD3RcCc4D5wUbjvUS/4AnaPUl0Y3Ex8F13LwE40Tyr/+WJiEisLPpDvm6IRCKekZERdhkiInWKmWW6e6SidjpFpoiIAAoEEREJKBBERARQIIiISECBICIiQB3by8jM9gAfx9i8PZBbg+WcLtVVOaqrclRX5TSUunq4e4eKGtWpQKgMM8uIZTer2qa6Kkd1VY7qqhzVdTx1GYmICKBAEBGRQH0OhFlhF3ASqqtyVFflqK7KUV1l1NttCCIiUjn1eQ1BREQqoV4GgpmNMbP1ZpZlZrfU8rIfNLPdZra6zLi2ZvaqmX0U3LcJxpuZ3R3UudLMhtVgXd3M7A0zW2tma8zse/FQm5k1NbMlZvZBUNdvgvG9zGxxUNcTwWnSCU6l/kRQ12Iz61kTdQXLSjCz5Wb2fLzUFCxvs5mtMrMVZpYRjIuHz1hrM3vazNYFn7NRYddlZv2Dv9Ox20Ez+37YdQXL+kHwmV9tZo8H/wvhfsbcvV7diJ5OeyOQDiQCHwADa3H5o4FhwOoy4/4A3BIM3wLcEQxfAbxE9Mpy5wKLa7CuTsCwYDgF2AAMDLu2YP4tguEmwOJgeU8C44Px9wMzguHvAPcHw+OBJ2rwb/bfwGPA88Hj0GsKlrEZaF9uXDx8xh4GvhUMJwKt46GuMvUlADuBHmHXRfRSwtlAcpnP1uSwP2M1+gaEcQNGAa+UeXwrcGst19CT4wNhPdApGO4ErA+GHwAmnKhdLdT4d+DSeKoNaAYsI3p97Vygcfn3lOg1NEYFw42DdlYDtXQF/gVcBDwffEGEWlOZ2jbz+UAI9X0EWgZfcBZPdZWr5TLg3Xioi8+uQ982+Mw8D1we9mesPnYZHftDH5MTjAtTmrvvAAjuU4PxodQarG4OJfprPPTagq6ZFcBu4FWia3j73b34BMv+tK7g+QNAuxoo60/AT4DS4HG7OKjpGAf+aWaZFr3mOIT/PqYDe4C5QTfbbDNrHgd1lTUeeDwYDrUud98G/C+wBdhB9DOTScifsfoYCHaCcfG6K1Wt12pmLYBngO+7+8FTNT3BuBqpzd1L3H0I0V/lI4EzTrHsGq/LzL4M7Hb3zLKjw6ypnC+4+zDgS8B3zWz0KdrWVm2NiXaVznT3ocAhol0xYdcVXVi0L/4q4KmKmp5gXLXXFWyzGAv0AjoDzYm+nydbdq3UVR8DIQfoVuZxV2B7SLUcs8vMOgEE97uD8bVaq5k1IRoGj7r7s/FUG4C77wfeJNp329rMjl3iteyyP60reL4V0cu2VqcvAFeZ2WZgAdFuoz+FXNOn3H17cL8beI5oiIb9PuYAOe6+OHj8NNGACLuuY74ELHP3XcHjsOu6BMh29z3uXgQ8C5xHyJ+x+hgIS4G+wdb6RKKriQtDrmkhMCkYnkS0//7Y+BuCPRvOBQ4cW42tbmZmRK99vdbd74qX2sysg5m1DoaTif6jrAXeAK49SV3H6r0WeN2DjtXq4u63untXd+9J9PPzurtfH2ZNx5hZczNLOTZMtF98NSG/j+6+E9hqZv2DURcTvZZ66J/9wAQ+6y46tvww69oCnGtmzYL/zWN/r3A/YzW5ESesG9E9BTYQ7Yv+WS0v+3GifYJFRFN9CtG+vn8BHwX3bYO2Btwb1LkKiNRgXf9BdBVzJbAiuF0Rdm3AYGB5UNdq4JfB+HRgCZBFdDU/KRjfNHicFTyfXsPv54V8tpdR6DUFNXwQ3NYc+3yH/T4GyxoCZATv5d+ANnFSVzPgE6BVmXHxUNdvgHXB534+kBT2Z0xHKouICFA/u4xEROQ0KBBERARQIIiISECBICIigAJBREQCCgQREQEUCCIiElAgiIgIAP8fboQoOL6SXEcAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Test selection sort on randomly-sorted lists of different size,\n",
    "# and plot the results\n",
    "\n",
    "N_values = list(range(10,1000,200))\n",
    "time_values = []\n",
    "\n",
    "for N in N_values:\n",
    "    input_list = random_list(N)\n",
    "    time_taken = time_sort(selection_sort, input_list)\n",
    "    time_values.append(time_taken)\n",
    "\n",
    "plt.plot(N_values, time_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the merge sort code given in lectures:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def msort(items):\n",
    "    len_list = len(items)\n",
    "    if len_list <= 1:\n",
    "        return items\n",
    "    else:\n",
    "        mid_point = len_list//2\n",
    "        top = items[:mid_point]\n",
    "        bottom = items[mid_point:]\n",
    "        return merge(msort(top), msort(bottom))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This function won't work yet because it depends on a `merge()` function, which we haven't defined."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Challenge:** Write a merge function to merge two lists. Assume both lists are already sorted, and ensure that the resulting list is sorted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "#remember, both lists are sorted due to recursion\n",
    "def merge(list1, list2):\n",
    "    merged = [0] * (len(list1) + len(list2)) # create a list of zeros\n",
    "    \n",
    "    #create index variables for each list\n",
    "    index1 = 0\n",
    "    index2 = 0\n",
    "    indexm = 0 # index in merged list\n",
    "    \n",
    "    #compare each list and merge until all indexes in either one list are covered\n",
    "    while index1 < len(list1) and index2 < len(list2):\n",
    "        #if the smaller item is in list1, add it to the merged list and increment index\n",
    "        if list1[index1] < list2[index2]:\n",
    "            merged[indexm] = list1[index1]\n",
    "            index1 += 1\n",
    "        else:\n",
    "            merged[indexm] = list2[index2]\n",
    "            index2 += 1\n",
    "        indexm += 1\n",
    "    \n",
    "    #if one list is exhausted, the other has all elements are larger than the merged list\n",
    "    #these elements are already sorted by the recursive calls\n",
    "    #listA.extend(listB) adds the elements of listB to the end of listA\n",
    "    while index1 < len(list1):\n",
    "        merged[indexm] = list1[index1]\n",
    "        index1 += 1\n",
    "        indexm += 1\n",
    "    while index2 < len(list2):\n",
    "        merged[indexm] = list2[index2]\n",
    "        index2 += 1\n",
    "        indexm += 1\n",
    "    \n",
    "    return merged"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note on efficiency**: If the size of the list is known, for instance the length of the merged list is the sum of the length of the two lists, initialising the merged lists with zeros and replacing the values turns out to be much faster than starting off with an empty merged list and then appending values to it (dynamic length)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 6, 9, 20, 21]\n"
     ]
    }
   ],
   "source": [
    "x1 = [4,6,9]\n",
    "x2 = [2,6,20,21]\n",
    "print(merge(x1,x2))\n",
    "assert merge(x1,x2) == [2,4,6,6,9,20,21]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have `merge()` working, `msort()` should work correctly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 3, 4, 5, 7, 22]\n"
     ]
    }
   ],
   "source": [
    "x = [5,3,7,22,4,3]\n",
    "print(msort(x))\n",
    "assert msort(x) == sorted(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Draw plots similar to the insertion sort plots above to test the behaviour of merge sort with random, inverted, and nearly-sorted lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f66a75c7278>]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAD8CAYAAABpcuN4AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xd8VGW+x/HPj0BCD70T6SBFWij2LuiKYAWxreLF9dpWV9eurK5e3WtfXbuirg1RMFaKHRUk1NBS6KFDICSBkDLP/WMO9+ZGCEMKJzPzfb9eeeXMmeccfs8wme+c85xizjlEREQOpobfBYiISPWmoBARkTIpKEREpEwKChERKZOCQkREyqSgEBGRMikoRESkTAoKEREpk4JCRETKVNPvAg5Hs2bNXIcOHfwuQ0QkrMybN2+7c655eZcPq6Do0KEDycnJfpchIhJWzGxtRZbXricRESmTgkJERMqkoBARkTIpKEREpEwKChERKZOCQkREyqSgEBGRMikoRESqsbQtOfzj6xX4edtqBYWISDVUHHC89MNKzn1uFh/MXc+m7HzfagmrM7NFRKLBqm253P7RIuav28WwXi155Pw+NKsf51s9CgoRkWoiEHC89esaHv96BbExNXhmdD9G9muDmflal4JCRKQaWJ+1hzsmL2L2qixO7d6cxy48hpYNa/tdFqCgEBHxlXOO939bzyNfLMPMePzCPlyS2N73rYiSFBQiIj7ZlL2XOz9O4ce0bRzXuSn/uOgY2jWu63dZv6OgEBE5wpxzfDJ/AxM+W0pRseOhkb24fMhR1KhRfbYiSlJQiIgcQdty9nHPlBRmLNvCoA6N+e+L+tKhWT2/yyqTgkJE5Aj5PnUrt364kLyCYu77w9FcfXxHYqrpVkRJCgoRkSpWHHA8+006//w2ne4tG/D82P50adHA77JCpqAQEalCWXkF3PLBAn5K386FA9rx91G9qRMb43dZh0VBISJSRRas28kN785ne14B/3VBH8YMql6HvYZKQSEiUsmcc7wzey0Pf76Mlg1r8/GfjqNPu3i/yyo3BYWISCXK21fE3Z+kkLRoI6f3aMFTl/Qjvm4tv8uqEAWFiEglydiay/X/nsfKbbncMaw715/cudqeG3E4FBQiIpXg88UbuXPyYmrXiuGdcUM4vkszv0uqNAoKEZEKKCgK8OiXy5n4yxoGHtWYF8YOoFV89biYX2VRUIiIlNOm7L3c8O585q/bxTXHd+Tuc3pQKyby7genoBARKYcf0rZx64cL2VdYzPNj+3PuMW38LqnKKChERA5DUXGAp2ak8a/vV9KjVQOeHzuALi3q+11WlVJQiIiEaHN2Pje9P5+5a3Zy6eD2PDiiF7VrhddZ1uWhoBARCcH3qVu5bdIi8guLeWZ0P0b1b+t3SUeMgkJEpAxFxQGenJHGi96uphcuG0Dn5pG9q6k0BYWIyEFsyt7Lze8v8HY1JfDgiJ5RsaupNAWFiMgBfJe6lds+XEhBUYBnx/RjZL/o2dVUmoJCRKQE7Wr6vZDODDGz4WaWamYZZnbXAZ6PM7MPvefnmFkHb/6ZZjbPzFK836eVWGagNz/DzJ6zcLz2rohElE3Ze7n01dm8+P1KLh2cwNQbjo/6kIAQtijMLAZ4ATgTyATmmlmSc25ZiWbjgJ3OuS5mNgZ4HBgNbAdGOOc2mllvYBqwf/vtRWA8MBv4EhgOfFU53RIROTyz0rdz0/vztavpAELZohgMZDjnVjnnCoAPgJGl2owE3vKmJwOnm5k55xY45zZ685cCtb2tj9ZAQ+fcr845B7wNjKpwb0REyuGd2Wu56s3faNGgNp/ddIJCopRQxijaAutLPM4EhhysjXOuyMyygaYEtyj2uxBY4JzbZ2ZtvfWUXOcB/2fMbDzBLQ8SEhJCKFdEJDRFxQH+/kXwgn6n92jBs5f2p36chm5LC+UVOdDYgTucNmbWi+DuqLMOY53Bmc69ArwCkJiYeMA2IiKHKye/kJveX8D3qdsYd0JH7jnnaGIi4N4RVSGUoMgE2pd43A7YeJA2mWZWE4gHsgDMrB0wBbjSObeyRPt2h1iniEiVWJ+1h2vfSmbltlwePb8PY4dob0VZQhmjmAt0NbOOZhYLjAGSSrVJAq7ypi8CvnXOOTNrBHwB3O2c+3l/Y+fcJiDHzIZ6RztdCXxawb6IiBzSvLU7GfXCz2zK3stb1wxWSITgkEHhnCsCbiR4xNJyYJJzbqmZPWRm53nNXgeamlkGcBuw/xDaG4EuwP1mttD7aeE9dz3wGpABrERHPIlIFft04QYufXU29WvX5JP/PD6i7kJXlSx40FF4SExMdMnJyX6XISJhxjnH0zPTee6bdAZ3bMLLlw+kcb1Yv8s6YsxsnnMusbzLa3hfRCJafmExt3+0iM8Xb+Lige145Pw+xNaMvLvQVSUFhYhErK05+Yx/ex6LMndx19k9uO6kTugiEIdPQSEiEWn5pt1c+1YyWXkFvHjZQIb3buV3SWFLQSEiEaU44Hh3zloe/2oF9WvX5KM/HUvvtvF+lxXWFBQiEjGWbMjm3ikpLMrM5oQuzXji4r60iq/td1lhT0EhImEvb18RT81I482fV9OkXizPjunHeX3baDyikigoRCSsTV+6mQlJS9mYnc/YIQncOawH8XVr+V1WRFFQiEhY2rhrLxOSljJ92Ra6t2zAx2P7M/CoJn6XFZEUFCISVoqKA0z8ZQ1Pz0ij2DnuOrsH407oSK0YnRtRVRQUIhI2Fq3fxT1TUli6cTendm/OQyN7075JXb/LingKChGp9nLyC3liWipvz15L8/px/OuyAZzdu5UGq48QBYWIVGtz12Rxy/sL2LQ7nyuHHsVfhnWnYW0NVh9JCgoRqZYCAceLP6zkqRlptGtch0+uP47+CY39LisqKShEpNrZmpPPbR8uYlbGdkb0bcOj5/emgbYifKOgEJFqZVb6dv784UJy9xXy2AV9GD2ovcYifKagEJFqoag4wDMz03nh+wy6NK/Pu9cOoXurBn6XJSgoRKQa2LhrLze/v4DktTsZndieCef1ok5sjN9liUdBISK+mrFsC3dMXkRhUYBnx/RjZL+2fpckpSgoRMQX+4qKeeyrFbz58xp6tWnI82MH0LFZPb/LkgNQUIjIEbd2Rx43vreAlA3Z/PG4Dtx9Tg/iampXU3WloBCRI8Y5x9SFG7h/6lJiahgvXzGQYb1057nqTkEhIkfEtpx93DslhenLtpB4VGOevbQ/bRvV8bssCYGCQkSq3OeLN3L/1CXkFRRzzzk9GHdCJ2Jq6NyIcKGgEJEqk5VXwP1Tl/BFyib6tovnyUv60qWFzo0INwoKEakSXy/ZzH1TU9i9t4i/Du/O+BM7UVP3jAhLCgoRqVS79hQwIWkpUxdupHfbhrx7bT+dYR3mFBQiUmm+Wb6Fuz5JYWdeAbee0Y3/PLWz7jwXARQUIlJh2XsLeeizZXw8P5MerRow8epB9GoT73dZUkkUFCJSId+nbuWuj1PYlruPm07rwk2ndSW2prYiIomCQkTKJXdfEY98sZz3f1tH1xb1efmKgfRt38jvsqQKKChE5LDNWbWD2ycvInPnXq47qRO3ntmN2rV0CY5IpaAQkZDlFxbzxLRUXv95Ne0b12XSdccyqEMTv8uSKqagEJGQLM7cxW2TFpGxNZfLhyZw99lHUy9OHyHRIKQRJzMbbmapZpZhZncd4Pk4M/vQe36OmXXw5jc1s+/MLNfMni+1zPfeOhd6Py0qo0MiUrkKiwM8NSON8//1C7n5Rbx9zWD+PqqPQiKKHPJ/2sxigBeAM4FMYK6ZJTnnlpVoNg7Y6ZzrYmZjgMeB0UA+cD/Q2/sp7TLnXHIF+yAiVSRtSw63TVrIkg27uaB/Wx4c0Yv4urX8LkuOsFC+EgwGMpxzqwDM7ANgJFAyKEYCE7zpycDzZmbOuTxglpl1qbySRaSqFQccr89axRPT02gQV5OXLh/A8N6t/S5LfBJKULQF1pd4nAkMOVgb51yRmWUDTYHth1j3m2ZWDHwM/N0550o3MLPxwHiAhISEEMoVkYpYuyOP2z9axNw1OxnWqyWPnN+HZvXj/C5LfBRKUBzoWsClP9BDaVPaZc65DWbWgGBQXAG8/buVOPcK8ApAYmLiodYpIuUUCDje+20dj365nJgaxlOX9OX8/m0x0+XAo10oQZEJtC/xuB2w8SBtMs2sJhAPZJW1UufcBu93jpm9R3AX1++CQkSq3todedz58WJmr8rixK7NePzCY2ijmwqJJ5SgmAt0NbOOwAZgDDC2VJsk4CrgV+Ai4NsD7UbazwuTRs657WZWCzgXmFmO+kWkAooDjjd/Xs0T01OpVaMGj13Qh9GD2msrQv6fQwaFN+ZwIzANiAHecM4tNbOHgGTnXBLwOvCOmWUQ3JIYs395M1sDNARizWwUcBawFpjmhUQMwZB4tVJ7JiJlytiawx2TF7Ng3S5O79GCv5/fm9bx2oqQ37MyvvhXO4mJiS45WUfTilREYXGAV35cxbMz06kXF8OE83pxXt822oqIYGY2zzmXWN7ldcaMSBRZujGbOz5azLJNu/nDMa3523m9dESTHJKCQiQK7Csq5p/fZPDSDytpVDeWly4fyPDerfwuS8KEgkIkws1ft5O/Tl5MxtZcLhzQjvvPPZpGdWP9LkvCiIJCJELtLSjmyenBK722blibiVcP4pTuuqSaHD4FhUgEmr9uJ3+ZtIjV2/O4fGgCdw7vQYPaukaTlI+CQiSCFBQF+Oe36bzwXQat4+vw3rVDOK5LM7/LkjCnoBCJECWv9HrRwHY8MKInDbUVIZVAQSES5gIBxxs/r+Yf01KpH1dTRzRJpVNQiISxzJ17+MukRcxZncUZR7fgvy44huYNdF6EVC4FhUgYcs4xeV4mf/tsGc45/nHhMVyc2E5nV0uVUFCIhJntufu4+5MUZizbwuCOTXjy4r60b1LX77IkgikoRMLI9KWbufuTFHLyi7j3nKMZd0JHatTQVoRULQWFSBjYmpPPf3+dykfzMunZuiHv/Uc/urdq4HdZEiUUFCLV2Mptubz64yo+mb+BokCAG07tzC2ndyO2Zg2/S5MooqAQqYbmrc3ipR9WMXP5FmJjanBxYjuuPbETHZvV87s0iUIKCpFqIhBwzFy+hZd/XMW8tTtpVLcWN53ahSuP66BLgYuvFBQiPssvLGbqgg288tMqVm3Lo13jOkwY0ZNLBrWnbqz+RMV/eheK+CR7TyH/nrOWib+sYVvOPnq3bchzl/bnnN6tqBmjMQipPhQUIkdYQVGAp2em8fYva8grKOakbs15ZnQnjuvcVCfMSbWkoBA5grLyCrj+3/OYszqLkf3acN1JnenZpqHfZYmUSUEhcoSkb8lh3FvJbN6dzzOj+zGqf1u/SxIJiYJC5Aj4LnUrN7+3gLhaMXwwfigDEhr7XZJIyBQUIlXIOcfrs1bz6JfL6dGqIa9elUjbRnX8LkvksCgoRKpIQVGA+6cu4cPk9Qzr1ZKnR/fT4a4SlvSuFakCWXkF/Onf8/htdRY3ntqF287spov3SdhSUIhUsrQtOVzrDVo/O6YfI/tp0FrCm4JCpBJ9t2IrN72/gDqxMXw4fij9NWgtEUBBIVIJSg9av3ZVIm00aC0RQkEhUkEFRQHum5rCpORMhvdqxVOj+2rQWiKK3s0iFZC+JYfbP1rEosxsbjqtC7eeoUFriTwKCpFyKCoO8OpPq3l6Rhr14mJ48bIBnN2ntd9liVQJBYXIYcrYmsNfPlrMovW7OLt3Kx4e1Vv3i5CIpqAQCVFxwPHqT6t4akYadWNjeO7S/ow4prWu+CoRL6SL3pvZcDNLNbMMM7vrAM/HmdmH3vNzzKyDN7+pmX1nZrlm9nypZQaaWYq3zHOmvzapxjK25nLhi7/w2FcrOLV7c2bcejLn9W2jkJCocMgtCjOLAV4AzgQygblmluScW1ai2Thgp3Oui5mNAR4HRgP5wP1Ab++npBeB8cBs4EtgOPBVxbojUrmKA47XflrFk95WxLNj+ikgJOqEsutpMJDhnFsFYGYfACOBkkExEpjgTU8Gnjczc87lAbPMrEvJFZpZa6Chc+5X7/HbwCgUFFKNrNyWyx0fLWL+ul2c2bMlj5zfmxYNavtdlsgRF0pQtAXWl3icCQw5WBvnXJGZZQNNge1lrDOz1Dp1nQOpFooDjjdmreaJ6anUrhXDM6P7MbKftiIkeoUSFAf663DlaFOu9mY2nuAuKhISEspYpUjFrduxh1snLWTe2p2ccXQLHj2/Dy0aaitColsoQZEJtC/xuB2w8SBtMs2sJhAPZB1ine0OsU4AnHOvAK8AJCYmlhU+IhXyxeJN3PXxYjB46pK+nN+/rbYiRAjtqKe5QFcz62hmscAYIKlUmyTgKm/6IuBb59xBP9Sdc5uAHDMb6h3tdCXw6WFXL1IJ8guLuW9qCje8N5/OLerz5c0ncsGAdgoJEc8htyi8MYcbgWlADPCGc26pmT0EJDvnkoDXgXfMLIPglsSY/cub2RqgIRBrZqOAs7wjpq4HJgJ1CA5iayBbjrhV23K54b0FLN+0m/EndeKOYd2pFRPSUeMiUcPK+OJf7SQmJrrk5GS/y5AIMXXBBu6ZkkJczRo8eUlfTuvR0u+SRKqEmc1zziWWd3mdmS1RZ29BMQ8mLWFSciaDOjTmuUv70zpelwQXORgFhUSVtC053PDufDK25XLjqV348xldqaldTSJlUlBIVHDO8VFyJg8kLaF+XE3evmYwJ3Zt7ndZImFBQSERL3dfEfdNSWHqwo0c17kpz4zup3MjRA6DgkIi2rKNu7nxvfms2ZHHbWd244ZTuxCjGwuJHBYFhUSkfUXF/Ou7lfzr+wya1Ivlvf8YytBOTf0uSyQsKSgk4sxetYN7pqSwalseI/u14YFze9JUNxYSKTcFhUSMXXsKePTL5UxKzqR9kzq8dc1gTu6mAWuRilJQSNhzzpG0aCMPf76MnXsK+dPJnbnl9K7UiY3xuzSRiKCgkLC2bsce7p2awk/p2+nbvhFvX9OHnm0a+l2WSERRUEhYKiwO8NpPq3n2mzRq1qjB387rxeVDj9IRTSJVQEEhYWfBup3c/UkKKzbnMKxXSyac10uX4BCpQgoKCRs5+YU8MS2Vt2evpWWD2rx8xUCG9Wrld1kiEU9BIdWec45pS7cwIWkpW3LyuerYDvzlrG40qF3L79JEooKCQqq1Dbv28uCnS5m5fAtHt27IS1cMpF/7Rn6XJRJVFBRSLRUVB3jr17U8OT0V5+Cec3pwzfEddaVXER8oKKTaScnM5u4pi1myYTendm/OQyN7075JXb/LEolaCgqpNnL3FfHU9DQm/rKapvXjeGHsAM7p00r3rhbxmYJCqoUZy7bw4KdL2LQ7n8uGJHDHsB7E19FgtUh1oKAQX23OzufBpCVMW7qF7i0b8M+xAxh4VGO/yxKREhQU4ovigOOdX9fwxPQ0igIB7hzeg2tP7EgtDVaLVDsKCjniFmfu4t4pS0jZkM2JXZvxyKg+JDTVYLVIdaWgkCMme28hT05P5Z3Za2lWP47nLu3PiGNaa7BapJpTUEiV+7/LgC8nK28fVx3bgdvO6kZDnVktEhYUFFKlVm7L5YFPl/Bzxg76tovnzT8Ook+7eL/LEpHDoKCQKpFfWMy/vsvgpR9WEVerBg+P7MXYIboMuEg4UlBIpfs+dSsPfLqUdVl7GNWvDff84WhaNKjtd1kiUk4KCqk0m7PzeejzpXyZsplOzevx3rVDOK5LM7/LEpEKUlBIhRUVB5j4yxqenpFGUcBx+1nd+I+TOhFXU/esFokECgqpkDmrdvBg0lJWbM7hlO7Neei83jonQiTCKCikXLbszue/vlzO1IUbaduoDi9fMZCzerbUOREiEUhBIYelsDjAxJ/X8MzMNAoDjptP68L1p3ShTqx2M4lEKgWFhOzXlTt44NMlpG/N5dTuzXlwRC86NKvnd1kiUsVCugKbmQ03s1QzyzCzuw7wfJyZfeg9P8fMOpR47m5vfqqZDSsxf42ZpZjZQjNLrozOSNXYnJ3PTe8v4NJXZ7O3sJhXr0zkjT8OUkiIRIlDblGYWQzwAnAmkAnMNbMk59yyEs3GATudc13MbAzwODDazHoCY4BeQBtgppl1c84Ve8ud6pzbXon9kUpUUBTgzZ9X89w36RQGHLec3pXrT+lM7VrazSQSTULZ9TQYyHDOrQIwsw+AkUDJoBgJTPCmJwPPW3BUcyTwgXNuH7DazDK89f1aOeVLVfk5YzsPfLqEldvyOOPoFjxwbi8dzSQSpUIJirbA+hKPM4EhB2vjnCsys2ygqTd/dqll23rTDphuZg542Tn3yuGXL5Vtc3Y+D3+xjC8WbyKhSV3e+GMip/Vo6XdZIuKjUILiQMc7uhDblLXs8c65jWbWAphhZiuccz/+7h83Gw+MB0hISAihXCmP0ifN3XpGN647uZN2M4lISEGRCbQv8bgdsPEgbTLNrCYQD2SVtaxzbv/vrWY2heAuqd8Fhbel8QpAYmJi6YCSSjBvbRb3TlnCis05nNq9OX/TSXMiUkIoRz3NBbqaWUcziyU4OJ1Uqk0ScJU3fRHwrXPOefPHeEdFdQS6Ar+ZWT0zawBgZvWAs4AlFe+OHI6svALunLyYC1/8ley9hbx0+UDe+OMghYSI/D+H3KLwxhxuBKYBMcAbzrmlZvYQkOycSwJeB97xBquzCIYJXrtJBAe+i4AbnHPFZtYSmOKdxVsTeM8593UV9E8OIBBwTEpez2NfryA3v4jrTu7Ezad1pV6cTqsRkd+z4Bf/8JCYmOiSk3XKRUUs27ib+6amMH/dLgZ3aMLDo3rTvVUDv8sSkSpkZvOcc4nlXV5fIaNETn4hT89IZ+Ivq2lcN5YnL+7LBQPa6tpMInJICooI55zji5RNPPz5Mrbm7GPs4AT+OqwH8XV1v2oRCY2CIoKt27GH+z5dwo9p2+jdtiEvX5FIv/aN/C5LRMKMgiICFRYHePWnVTw7M51aMTWYMKInVxzbQferFpFyUVBEmHlrs7jnkyWkbsnh7N6teHBEL1rF637VIlJ+CooIkb23kH98vYJ356yjTXxtXrsykTN66tIbIlJxCoow55zj88Wb+Ntny8jK28e1J3Tk1jO76ZwIEak0+jQJY+uz9nDf1CX8kLaNY9rFM/HqQfRuG+93WSISYRQUYaiwOMDrs1bzzMw0Ysx4cERPrtRgtYhUEQVFmJm/bif3fJLCis05DOvVkgnn9aJ1fB2/yxKRCKagCBNrd+TxxPQ0Plu0kdbxtXnlioGc1auV32WJSBRQUFRz23P38c9v0nl3zjpqxhg3ntqFP53SmfoarBaRI0SfNtVU7r4iXvtpFa/+uIr8ogBjBrXnltO70qKhzokQkSNLQVHNFBQFeP+3dfzz23S25xZwTp9W3H5Wdzo1r+93aSISpRQU1UQg4Pg8ZRNPTEtlXdYehnZqwqtX9qB/QmO/SxORKKegqAZmpW/nsa+Xs2TDbnq0asDEqwdxcrfmugS4iFQLCgofLdmQzeNfr+Cn9O20bVSHp0f3ZWTfttTQ+RAiUo0oKHywLWcfT0xLZdK89TSqU4v7z+3J5UMTiKsZ43dpIiK/o6A4ggqKAkz8ZTXPfZPBvqJirj2hIzed3pWGtXUTIRGpvhQUR4Bzjm+Wb+WRL5ezensep/dowb1/OFpHMolIWFBQVLH0LTk89PkyfkrfTufm9Zh49SBO6d7C77JEREKmoKgiu/YU8MzMdN6ZvZZ6sTE8OKInlw89iloxNfwuTUTksCgoKllRcfCEuSdnpLF7byFjhyRw25ndaVIv1u/SRETKRUFRiX7O2M5Dny0jdUsOx3ZqygMjenJ064Z+lyUiUiEKikqwZEM2T05P5bvUbbRvUoeXLh/AsF6tdMKciEQEBUUFpG3J4ekZaXy1ZDPxdWpx5/AeXH18B2rX0vkQIhI5FBTlsHp7Hs/OTOPTRRupF1uTP5/RlWtO6KjzIUQkIikoDsOGXXt5bmY6k+dnUivGuO6kzlx3Uicaa6BaRCKYgiIEW3fn88J3Gbz/23oArjz2KK4/pTMtGujeECIS+RQUZcjKK+ClH1by1i9rKA44Lk5sz02ndaFNI92jWkSih4LiAHbk7mPiL2t4Y9Zq9hYWM6p/W245vStHNa3nd2kiIkecgqKE9C05vD5rNZ8s2EBBUYA/9GnNrWd2pUuLBn6XJiLim6gPCuccP6Vv57VZq/kxbRu1a9Xg4oHtuPr4jnRpoYv2iYiEFBRmNhx4FogBXnPOPVbq+TjgbWAgsAMY7Zxb4z13NzAOKAZuds5NC2WdVS2/sJhPF27g9VmrSduSS/MGcdx+VjfGDjlKl9sQESnhkEFhZjHAC8CZQCYw18ySnHPLSjQbB+x0znUxszHA48BoM+sJjAF6AW2AmWbWzVvmUOusEttz9/Hv2Wt559e17Mgr4OjWDXny4r6c27e1bhwkInIAoWxRDAYynHOrAMzsA2AkUPJDfSQwwZueDDxvwetXjAQ+cM7tA1abWYa3PkJYZ6VK25LD6z+tZsrC4PjD6T1aMO7EjhzbqakutSEiUoZQgqItsL7E40xgyMHaOOeKzCwbaOrNn11q2bbe9KHWWSkCAce1byfz7Yqt/zv+cM0JHemsmwaJiIQklKA40NdtF2Kbg80/0E0ZSq8zuGKz8cB4gISEhINXeRA1ahgdmtbjjmHdGTs4QWdRi4gcplCCIhNoX+JxO2DjQdpkmllNIB7IOsSyh1onAM65V4BXABITEw8YJofywIie5VlMREQ48Df70uYCXc2so5nFEhycTirVJgm4ypu+CPjWOee8+WPMLM7MOgJdgd9CXKeIiFQDh9yi8MYcbgSmETyU9Q3n3FIzewhIds4lAa8D73iD1VkEP/jx2k0iOEhdBNzgnCsGONA6K797IiJSURb84h8eEhMTXXJyst9liIiEFTOb55xLLO/yoex6EhGRKKagEBGRMikoRESkTAoKEREpk4JCRETKFFZHPZnZNmBtORZtBmyv5HLCSTT3P5r7DtHdf/X9/xzlnGte3pWFVVCUl5loBXQjAAAEe0lEQVQlV+TQsHAXzf2P5r5DdPdffa+8vmvXk4iIlElBISIiZYqWoHjF7wJ8Fs39j+a+Q3T3X32vJFExRiEiIuUXLVsUIiJSThEfFGY23MxSzSzDzO7yu57KYGZvmNlWM1tSYl4TM5thZune78befDOz57z+LzazASWWucprn25mVx3o36puzKy9mX1nZsvNbKmZ3eLNj5b+1zaz38xskdf/v3nzO5rZHK8vH3qX78e7xP+HXv/nmFmHEuu625ufambD/OnR4TOzGDNbYGafe4+jqe9rzCzFzBaaWbI3r+rf+865iP0heAnzlUAnIBZYBPT0u65K6NdJwABgSYl5/wDu8qbvAh73ps8BviJ4t8GhwBxvfhNglfe7sTfd2O++hdD31sAAb7oBkAb0jKL+G1Dfm64FzPH6NQkY481/Cbjem/5P4CVvegzwoTfd0/t7iAM6en8nMX73L8TX4DbgPeBz73E09X0N0KzUvCp/70f6FsVgIMM5t8o5VwB8AIz0uaYKc879SPC+HyWNBN7ypt8CRpWY/7YLmg00MrPWwDBghnMuyzm3E5gBDK/66ivGObfJOTffm84BlhO8D3u09N8553K9h7W8HwecBkz25pfu//7XZTJwupmZN/8D59w+59xqIIPg30u1ZmbtgD8Ar3mPjSjpexmq/L0f6UHRFlhf4nGmNy8StXTObYLghynQwpt/sNcg7F8bb1dCf4LfqqOm/96ul4XAVoJ/5CuBXc65Iq9Jyb78bz+957OBpoRv/58B/goEvMdNiZ6+Q/BLwXQzm2dm4715Vf7eD+We2eHMDjAv2g7zOthrENavjZnVBz4G/uyc2x38onjgpgeYF9b9d8G7RPYzs0bAFODoAzXzfkdM/83sXGCrc26emZ2yf/YBmkZc30s43jm30cxaADPMbEUZbSut/5G+RZEJtC/xuB2w0adaqtoWb7MS7/dWb/7BXoOwfW3MrBbBkHjXOfeJNztq+r+fc24X8D3B/c+NzGz/F7+SffnffnrPxxPcbRmO/T8eOM/M1hDcjXwawS2MaOg7AM65jd7vrQS/JAzmCLz3Iz0o5gJdvaMiYgkOaCX5XFNVSQL2H71wFfBpiflXekdADAWyvc3TacBZZtbYO0riLG9etebtY34dWO6ce6rEU9HS/+belgRmVgc4g+A4zXfARV6z0v3f/7pcBHzrgiOaScAY78igjkBX4Lcj04vycc7d7Zxr55zrQPBv+Vvn3GVEQd8BzKyemTXYP03wPbuEI/He93sUv6p/CI78pxHcj3uv3/VUUp/eBzYBhQS/HYwjuO/1GyDd+93Ea2vAC17/U4DEEuu5huBAXgZwtd/9CrHvJxDcTF4MLPR+zomi/h8DLPD6vwR4wJvfieCHXQbwERDnza/tPc7wnu9UYl33eq9LKnC23307zNfhFP7vqKeo6LvXz0Xez9L9n2dH4r2vM7NFRKRMkb7rSUREKkhBISIiZVJQiIhImRQUIiJSJgWFiIiUSUEhIiJlUlCIiEiZFBQiIlKm/wEf1nFRPhrNzAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Test selection sort on randomly-sorted lists of different size,\n",
    "# and plot the results\n",
    "\n",
    "N_values = list(range(10,5000,200))\n",
    "time_values = []\n",
    "\n",
    "for N in N_values:\n",
    "    input_list = random_list(N)\n",
    "    time_taken = time_sort(msort, input_list)\n",
    "    time_values.append(time_taken)\n",
    "\n",
    "plt.plot(N_values, time_values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}