Created
July 29, 2015 07:35
-
-
Save mikkkee/6ebf566eef2a4419bd47 to your computer and use it in GitHub Desktop.
Running time of several search algorithms
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"execution_count": 30, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [], | |
"source": [ | |
"# Best case and worst case comparison for some algorithms.\n", | |
"import random\n", | |
"import time\n", | |
"import copy\n", | |
"\n", | |
"%matplotlib inline\n", | |
"import numpy as np\n", | |
"import matplotlib.pyplot as plt\n", | |
"\n", | |
"from insertion_sort import insertion_sort\n", | |
"from merge_sort import merge_sort\n", | |
"from quicksort import quicksort" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 31, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [ | |
"# Input for following usage.\n", | |
"input_list = {}\n", | |
"for i in range(1000, 21000, 1000):\n", | |
" values = [random.uniform(0, 100000) for x in range(i)]\n", | |
" input_list[i] = values" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 32, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [], | |
"source": [ | |
"# Insertion sort, inplace sort.\n", | |
"# Worst case: random input, O(n^2)\n", | |
"# Best case: sorted input, O(n)\n", | |
"\n", | |
"insertion_input = copy.deepcopy(input_list)\n", | |
"\n", | |
"worst_time_insertion = []\n", | |
"best_time_insertion = []\n", | |
"\n", | |
"for length in insertion_input:\n", | |
" # Worst case.\n", | |
" start = time.time()\n", | |
" insertion_sort(insertion_input[length])\n", | |
" duration = time.time() - start\n", | |
" worst_time_insertion.append([length, duration])\n", | |
" # Best case.\n", | |
" start = time.time()\n", | |
" insertion_sort(insertion_input[length])\n", | |
" duration = time.time() - start\n", | |
" best_time_insertion.append([length, duration])" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 33, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEZCAYAAACJjGL9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8FdX9//HXJ8i+iiAIArFBrVYrflVQFEhdAIu1tm6t\nQLVV237rV7TaukAt2LrUtmqV9vutUNwVl1pFTatYKCKiUBdQqBv5gcoioOwgiOTz+2NO4uSS3Nwk\nd0vyfj4e95E7M3fOnHsyM587c86cY+6OiIhIdQpynQEREclvChQiIpKUAoWIiCSlQCEiIkkpUIiI\nSFIKFCIikpQCheSUmQ0ys7dznY9sM7NlZnZCPdNIa9mZ2bfM7EMz22xmh6Ur3Vwzs97hO1mu89JQ\nNZpAYWZXm9nfE+a9V828s9K43UIzKzOz3crSzO4wswvN7Dwz2xV21s1mVmpmP07Dts8zsxdS+Nww\nM5ttZpvMbI2ZzTKzb9R3+ynmcWTse28LZVU+vcndX3D3L2cjLyE/55jZK2H7K83s72Z2bLa2H+Ph\nVfcEEsouBJ/j65Hk74GfuHt7d19Yn7yF/Mwys/Prm04dtlupHNz9g/Cd0v7QmJl908wWmNlGM1tr\nZjPMrLCOaRWb2YfpzWF6NJpAATwPDCz/1WBm+wB7AP3KT+JhXhEwuzYJm1mzVD5WxbzhQEl4/2LY\nWdsDpwO/NbN+tclHXZjZGcAjwN1AT3ffG/glkJVA4e4PxL73ycCK8ml375CNPJQzs8uAW4HrgL2B\nXsCfgFOzmY8McqreD2sUjpvewH/quH5V55J6B8Na5mGP2HYzfvVgZn2Be4CfuntHYD+i/WlXHdLa\no+ZP5ZC7N4oX0ALYChweps8C7gRmAf8Vm/deeN8DeBL4BHgPuCCW1gTgr8B9wEbgB0B/4JUw/RHw\n+/DZD4AyYHN4DQjzvwosDO/PA15IyO884Dux6aOBucB6YAEwJLbsPKAU2AT8P+Ac4MvAduDzsN11\nVZSJhfxdnqTcioCZwMfAWuB+oGNs+ZXA8rDtt4HjY2lfBSwJ6z4M7FnD/6gY+DDZPGAZ8DPgjfC9\npgDdgH+Esn8O6JRKuSVsp2NI7/Qk+WsJ/AFYEV63Ai1i+VwO/BxYA6wETgO+Drwb9qOrqtiHHgpl\n9yrw1djypamUJfB/wF9j690E/DOx7Ij21V3AtvA9fw48DfxPwnd8A/hmFd97C9F+vIUvjpGDiI6f\n9cAi4Buxde4Oeft7WOf4KsrzX8APEsrvMmB1KL/zYp/9OrA4lNVyYvsscEr4364HXgQOTdhfrgAW\nEh0PDyaUw8+AwvDdClI89h8hCgCbwvc+opr95Qzg9XruT1cAq8I2t4W8bw7b7p7Nc2jSYzfXGUjr\nl4lOeJeG938Evk/06zE+7y/h/eww3QI4jOjg/1psZ/kMODVMtwJeAkaG6TZ8ERD6xHfCWF6uAq4P\n788jFiiIgs56oG+Y7kl0ghgepk8M03sBbYlOkPuHZd2Ag8P7c0kIQAl5+HLIW58knykCTgCaA12I\nrsxuDcsOJAo03cN0b+BL4f0lRCfoHmHdPwMP1vD/KabmQLE0pNs1pL0aeC38j1oCM4Bf1lBuXarY\n9nBgZ+L/KeEzvwrb7hJeLwK/iuVzJ/ALoBlwQdjWA+F/dDDRgd4nYR/6dvj85URBvlnsex5fU1kC\nrYF3wv96EFEw75Gk7I6PTZ8JvBybPizkeY9qvn9Z7P/bnChwXUV0Zf41opPXAWH53cAG4Jgw3bKK\n9BIDxc5QLs2Iri63En6UEJ0sjw3vO/LFD77Dwz5wFFFA/V74ns3D8mVh/+hZnocqyqGQyoGipmP/\nU6L9xYAbgJeqKa/9wmdvCd+vXR32pxtDWbcChpBwfOTLK+cZSOuXgfHA38L7BUQnwWGxeQuB0US3\nHD4H2sbWvQG4K7azzEpI+/kwv0vC/Eo7YWz+7NiOf17YKdaHg60MuC322SuBexPWfyYcFG3Cet8G\nWid85jySB4pjw7Za1KIMTwNeC+/7hoP0hPIDM/a5/yQcjPsQnRiTnYiLEw+ExHlEB/l3Y9N/Bf4U\nm/4f4PGayq2KbY8EVtXw3ZcQgk6YHgosjeVzG2Bhun0o26Nin3+FL35cTADmxpYZ0a/oY2PfszxQ\nJC1Loh8W64hOimfXUHbxdFqF9YrC9O+BPyb5/vFAMSixvIh+rY8P7+8G7q6hPBMDxbb4/hH2rf7h\n/fvAD4EOCWn8H+HkGpv3NjAo9p3PS1hebaAgtWN/emzZwcC2JN9xANEV4BqioHFXedop7E87iB2b\nif/PfHo1pjoKiE7Ox5nZnkBXdy8luhIYGOZ9JXymB9Gtmq2xdT8g+lVSbnlC2ucDBwBvmdl8MxtR\nXSbMrBPRr/m5sdkvu/ueHt2X7w4cYmY3hGV9gDPNbH35i+gk393dtwFnAz8GVprZ02Z2YIrl8Un4\nu0+SvHYzs4fMbLmZbSS6hbEXgLsvAS4lOnhWm9nUUM8D0cH3eCy//yE6ALulmLdkVsfef5owvR1o\nF95XW25VpPkJ0KWae+nlehCdsMp9EOZVpOHhiA75qiqv7WLTFftQWG95QnrlCklSlu4+n+hqBODR\nJPmvxN23E93SGB3qIL5D9P9NRQ8gsWL1/Vj+vYrlNfnE3cti09v4orxOJ7r9tCxUgh8d5vcBLk/4\nH+9L5XKsTT5SOfbj/9NtQKvq9ht3n+fuZ3tU9zcIGAyMi20r2f601t0/q0Xec6axBYqXiS5bLyS6\nzMPdNxH9kvshsNLd3w/Tnc0sflD3pnJwcOIT7kvc/Rx370p0n/ivZtY68XPBMGBG7KRSibuvAf7G\nFxXKHwD3hUBS/mrv7r8Nn5/u7kOJToBvA5OrymMV3iE6iM5I8pkbiO6LHuJRhdxoYvuFu09190FE\nB6yH716e5+EJeW7j7qtqyFNdVFcxmbTcErxE9AvuW0m2s5LopF2ud5hXV73K34QTzb7VpJe0LM3s\nIqLbJCuJ7mlXp6r94R6iq6kTiX4Zz0sx7yuBXglNSvsQ3WtPO3d/xd1PI7rl+ARRgIOobK5PKJt2\n7v5wfPXE5JJsKpVjv07c/RXgcaIfpOXbKkzYTvz/X5t851SjChTu/inR5f9lVG7ZNCfMez587kOi\nX/s3mllLM/sqUYX1/dWlbWajzKxrmNxI9E8tI7pnXEZ0m6vc1/mitVNVae1FdMJaFGbdD3zDzIaa\nWTMzaxWayvU0s71DE7y2RLevtvJFq4rVwL5m1rya8vDwva8JTWk7mFmBmR1nZneEj7ULaW4ys55E\nlaDl+TzAzI43s5ZEJ9ntsW3/GbjBzHqHz3Y1s2y3Hqq23BI/6O4biVp7/SmUZxsza25mJ5tZefCb\nCvzCzLqYWZfw+VR/gVflCIueTdiD6MpsO9GPmUTVlqWZHQD8muhk/z3gCqv+GYfVVN4PcfeXiPbV\n3wP31iLvLxP9mr4ilFMxUaXyQ2F52loVhfRHmllHdy+vzC3fzyYDPzaz/hZpa2YjEk70iXYrh3J1\nOfaT5PtYM7ug/LxgZl8m+vFX/j+u7f60GtjLzLLaGjAlub73le4XX/xC7hebd2aYd2FsXk/gKaJb\nEkuAH8aWjWf3e9/3Ef0jNwNvEu5Fh2XXEt2jXEfUCmcVsboMoorI8tZJm0M6DyR8pj9RC5NPQlpP\nEf0C7R7mbyCqq5gJfDms05yoZcsnwJokZTKMKHBuDmnPBE72L+7BvhKWvUYUWD4Iyw4lap21KWzj\nSb6o2Dbgp0RXOJtCGV5Xw/+muDzt6uax+/3l+wiV12H6fCrfQ66q3HolycM5wL+JWuqsCp8/Oixr\nCdxG9KtvJVGLlRbV5HOPsE/1js17ATgntg89SuVWT/2q+p7VlSVRpe884IrYej8marnUvIo8nUp0\nq2M9cFls/i+IfswU1vD/2UWoo4jtG7OI9r1FxFpLEd2L/1UN6SXWUST+75cCx4fv8g+i42dj+M4D\nE/bf+eF7rSSqE2ibWI7VlQPRr/pdfFHnk/Kxn7huwna+QnRMfER0/Cwlqpwub7CQ8v4US3MKUYOD\ndeRRq6fyirm0M7NeRL9g9ib6RTPJ3W83s85E/+g+RJVzZ7n7hoxkIgfMrD9wu7sfXeOHpdEys/FE\nrdpG50FeRhP9SBqc67xIw5TJW087iR5E+QrRr+yLzOwgouZ2z7n7AURNHa/KYB5ywYl+lUjTlhfd\nRZhZG+AiYFKu8yINV8YChbt/5O4LwvstwFtEl3ynElWwEf6elqk85IK7/9vdn811PiTnnBxXTprZ\nMKLbcauImraK1EnGbj1V2kjU98nzwCFE9+X2DPONqKnanhnPhIiI1EnGWz2F1gmPAZe4++b4Mo+i\nVN42CRMRkajlRsaEZpuPEbV1fyLMXm1m3d39o/Dw1poq1lPwEBGpA3dPe/1Yxq4owm2lKcB/3P0P\nsUVPEjUXJfx9InFdaHzNdnP5Gj9+fM7z0JheKk+VZ76+MiWTVxTHAqOAN8zs9TDvauA3wCMW9VO/\njKhHVxERyVMZCxTuPofqr1hOzNR2RUQkvRpVFx5SteLi4lxnoVFReaaXyjP/ZaV5bG2ZmedjvkRE\n8pmZ4RmozM7v4fdEJKMqdw4rDUk2f0wrUIg0cbp6b3iyHeBVRyEiIkkpUIiISFIKFCIiDdzskhJ+\nMWxYxtJXqyeRJiy0ksl1NqSW4v+32SUlPHvJJVxfWorRwLrwEBGpqxtvvJGvf/3rlebtv//+Vc57\n5JFHSJdly5ZRUFBAWVlZ0s+9++67nHnmmXTt2pVOnTpx2GGHceutt9a4XiZMv/12ri8tzeg2FChE\nZDfltzImFBfzi2HDmF1S7RDwGUljyJAhzJ07t+JX86pVq/j8889ZsGBBxcl41apVlJaWMnhw7Qbu\n27VrV42fSXaVVVpayoABA+jTpw+LFi1iw4YNPProo7z66qts3ry52vUyZY8dOzK/kVx3YlVNx1Yu\nIplX1bH2/NNP+9iiIneoeI0tKvLnn3465XTrm8aOHTu8TZs2/tprr7m7+8MPP+zf//73fciQIf7q\nq69WzOvbt6+7u69YscK/8Y1veOfOnb1v374+efLkirTGjx/vp59+uo8aNco7dOjgU6ZM8Xnz5vkR\nRxzhHTp08G7duvnll1/u7u69evVyM/N27dp5u3bt/OWXX94tbyNHjvRTTjklaf7POOMM7969u3fs\n2NEHDx7sixcvrlhWUlLiBx98sLdv39579uzpv//97yuWPfXUU37YYYd5p06dfODAgf7GG29UmX78\n/zZu6NCKMg7z039OzkSi9c6UAoVIVlR1rMVPPPHXL4YNSznddKTxta99zW+99VZ3d7/ooov8zjvv\n9HHjxlWad/7557u7+6BBg/yiiy7yHTt2+IIFC7xr164+c+ZMd48CRfPmzX3atGnu7v7pp5/60Ucf\n7ffff7+7u2/durUiICxbtszNzHft2lVtvrp37+5333130rzfddddvmXLFv/ss8/80ksv9X79+lVa\nf86cOe7uvmHDhopg+Nprr/nee+/t8+fP97KyMr/nnnu8sLDQd+zYsVv68f9bPChnKlDo1pOIVFLd\nrYxm27dnNY0hQ4Ywe/ZsAObMmcPgwYMZNGhQxbwXXniBIUOG8OGHHzJ37lxuuukmWrRowWGHHcYF\nF1zAvffeW5HWwIEDOfXUUwFo1aoVLVq04L333uPjjz+mTZs2DBgwAEjt4cNPPvmEffbZJ+lnzjvv\nPNq2bUvz5s0ZP348CxcurLgt1aJFCxYvXsymTZvo2LEjhx9+OACTJk3iRz/6EUcddRRmxve+9z1a\ntmzJyy+/nHRbg0eMYNhtt3FNBls9KVCISCWft2xZ5fxdrVplNY3BgwczZ84c1q9fz9q1aykqKuKY\nY45h7ty5rF+/nsWLFzN48GBWrlxJ586dadu2bcW6vXv3ZsWKFRXT++67b6W0p0yZwrvvvstBBx1E\n//79KalF/clee+3FypUrq11eVlbGVVddRd++fenYsSP77bcfZsbHH38MwGOPPcbf//53CgsLKS4u\nrggE77//PjfffDN77rlnxWv58uWsWrWq5rIaMYJfP/NMyt+hthQoRKSSoWPGMK6oqNK8sUVFnHTx\nxVlN4+ijj2bjxo1MnjyZY489FoAOHTrQo0cPJk2aRI8ePejTpw89evRg3bp1bNmypWLdDz74oFJw\nSOzyom/fvjz44IOsXbuWK6+8kjPOOINPP/00pa4xTjzxRB577LFqlz/wwAM8+eSTzJgxg40bN7J0\n6dL4bXWOPPJInnjiCdauXctpp53GWWdFQ/L07t2bcePGsX79+orXli1bOPvss1Mus0xRoBCRSuK3\nMiYMGcI1w4Yx/LbbGDxiRFbTaN26NUceeSS33HJLpZZNxx13HLfccgtDhgwBoFevXgwcOJCrr76a\nHTt28MYbb3DnnXcyatSoatO+//77Wbt2LQAdO3bEzCgoKKBr164UFBRQmqS56bXXXsvcuXO54oor\nWL16NQBLlixh9OjRbNy4kS1bttCyZUs6d+7M1q1bGTt2bMW6O3fu5IEHHmDjxo00a9aM9u3b06xZ\nMwAuvPBC/vznPzN//nzcna1bt1JSUlIpAOZMJio+6vtCldkiWZHvx9rVV1/tBQUF/vrrr1fMe+SR\nR7ygoMAnTZpUMW/58uV+yimneOfOnb2oqMjvuOOOimUTJkzw0aNHV0p31KhRvvfee3u7du38kEMO\nqajodnf/5S9/6V27dvVOnTr5vHnzqszXO++842eeeabvtdde3rFjRz/ssMP8tttu8127dvmWLVv8\nm9/8prdv394LCwv93nvv9YKCAi8tLfXPPvvMhw8f7nvuuad36NDB+/fv7y+++GJFus8884wfddRR\n3qlTJ99nn338rLPO8s2bN++2/er+b2SoMltPZos0YXoyu2Gq7v+WqfEodOtJRESSUqAQEZGkFChE\nRCQpBQoREUlKgUJERJJSoBARkaQUKEREJCkFChERSUqBQkREklKgEJG8VFhYSJs2bWjfvj2dO3fm\nlFNOYfny5WlJd+bMmUk/s2nTJi699FL69OlD+/bt6du3Lz/96U/55JNP6r39hkiBQkR2UzJzJsPG\njKH4kksYNmYMJTWcWDORhpnx9NNPs3nzZlatWkW3bt24uBa9zyZLN1m3JZ999hknnHACb731Fs8+\n+yybN2/mpZdeokuXLsyfP7/e22+QMtGBVH1f5HlHZSKNRVXH2tMzZnjRBRc4//pXxavoggv86Rkz\nUk43HWkUFhb6jNjnS0pK/IADDqiY3r59u19++eXeu3dv79atm//4xz/2Tz/91N3d165d6yNGjPBO\nnTp5586dfdCgQV5WVuajRo3ygoICb926tbdr185/97vf7bbdyZMne7du3Xzr1q3V5u3GG2/0oqIi\nb9++vR988MH++OOPVyx77733fPDgwd6xY0fv0qWLn3322RXL3nrrLT/xxBO9c+fOfuCBB/ojjzyS\ncnnEVXeORCPciUg23P7EE5SOHFlpXunIkUycNi2racAXI85t27aNhx9+mGOOOaZi2VVXXcWSJUtY\nuHAhS5YsYcWKFfzqV78C4Oabb6ZXr158/PHHrFmzhhtvvBEz47777qN3794VVyo/+9nPdtvmP//5\nT04++WTatGlTbb769u3LnDlz2LRpE+PHj2fUqFEVXY5fc801DB8+nA0bNrBixQrGjBkDwNatWznp\npJMYNWoUa9eu5aGHHuInP/kJb731Vq3KJBcUKESkkh3VDN6T+iCm6UnD3TnttNPYc8896dSpEzNm\nzKg4sbs7kydP5pZbbqFTp060a9eOq6++moceegiIhhtdtWoVy5Yto1mzZhUDH6Vi3bp1NQ51esYZ\nZ9C9e3cAzjrrLPbff/+K21ItWrRg2bJlrFixghYtWjBw4EAAnn76afbbbz/OPfdcCgoK6NevH9/+\n9rd59NFHa1EquaFAISKVtKzm/n3qg5imJw0zY9q0aaxfv54dO3YwceJEhgwZwpo1a1i7di3btm3j\niCOOqBg29OSTT64YbvTnP/85ffv2ZejQoRQVFXHTTTelvN2ahjoFuPfeezn88MMrtr1o0aKKbf/2\nt7/F3enfvz+HHHIId911FxANdTpv3rxKQ50++OCDFVcieS0T97Pq+0J1FCJZUdWxVmX9wvnn17+O\nopZpJNZRuLt37drVH3vsMd+1a5e3adPGV65cWWM6ixYt8r333ttnzpzp7u777bffbunG/eUvf/Hu\n3btXW0exbNkyb9mypb/44oteVlbm7u79+vXzKVOm7PbZOXPmeKtWrXzJkiU+depUP+mkk2rMbyqq\nO0eiOgoRyYYRxx/Pbd/9LsMef5whjz/OsMcf57ZzzmHE8cdnNQ34oo7C3SuuLg466CAKCgq48MIL\nufTSSyuGNF2xYgXTp08HoKSkhCVLluDudOjQgWbNmlFQEJ3uunXrlnSo09GjR9OrVy9OP/103nnn\nHcrKyvjkk0+44YYb+Mc//sHWrVsxM7p06UJZWRl33XUXixYtqlj/0UcfrWjG26lTJ8yMZs2accop\np/Duu+9y//33s3PnTnbu3Mm///1v3n777VqVSU5kIvrU94WuKESyIp+PtcLCworWSe3bt/dDDz3U\nH3zwwYrl27dv97Fjx/qXvvQl79Chgx900EE+ceJEd3e/9dZbvbCw0Nu2bev77ruvX3fddRXrTZs2\nzXv37u2dOnXym2++ucptb9y40S+99FLv1auXt2vXzouKivzyyy/3devWubv7uHHjvHPnzt6lSxe/\n7LLLvLi4uOKK4oorrvCePXtWrDd58uSKdN955x0fMWKEd+3a1ffaay8/4YQTfOHChbUum+r+b2go\nVBFJNw2F2jBpKFQREckrChQiIpKUAoWIiCSlQCEiIkkpUIiISFIKFCIiktQeuc6AiOSWVdMvk0g5\nBQqRJkzPUNTf7JISpt9+O3vs2MHnLVsydMwYBo8YketspZUChYhIHc0uKeHZSy7h+liXIOPC+8YU\nLFRHISJSR9Nvv71SkAC4vrSU5yZOzFGOMiOjgcLM7jSz1Wb2ZmzeBDNbbmavh9fwTOZBRCRT9tix\no8r5zbbXZuSN/JfpK4q7gMRA4MAt7n54eD2T4TyIiGTE5y1bVjl/V6vajLyR/zIaKNz9BWB9FYvU\nzEJEGryhY8Ywrqio0ryxRUWcdPHFOcpRZuSqMvtiM/se8ApwubtvyFE+RETqrLzC+pqJE2m2fTu7\nWrVi+MUXN6qKbCDz3YybWSHwlLsfGqb3BtaGxb8G9nH38xPW8fHjx1dMFxcXU1xcnNF8iog0NLNm\nzWLWrFkV09dee21GuhnPeqBIZZnGoxARqb1GMx6Fme0Tm/wW8GZ1nxURkdzLaB2FmU0FhgBdzOxD\nYDxQbGb9iFo/LQV+lMk8iIhI/WgoVBGRRqLR3HoSEZGGRYFCRESSUqAQEZGkFChERCQpBQoREUlK\ngUJERJJSoBARkaQUKEREJCkNhSoiTVZTGO86HRQoRKRJairjXaeDbj2JSJPUVMa7TgcFChFpkprK\neNfpoEAhIk1SUxnvOh2S1lGYWXNgKDAYKCTqGvx9YDbwrLt/nukMiohkwtAxYxhXWlrp9tPYoiKG\nN7LxrtOh2m7Gzewa4HTgJWA+sJLoCmQfoD9wNPBXd78u7ZlSN+MikgWzS0p4Ljbe9UkNfLzrTHUz\nnixQnEo0TGmVHzCzAuAUd38y7ZlSoBARqbWsB4pqMlEAtHP3TenOSMJ2FChERGopZwMXmdlUM+tg\nZm2BRcBbZnZFujMiIiL5KZVWTweHK4jTgH8QVWqPzmSmREQkf6QSKPYIrZ9OI6qz2EnU+klERJqA\nVALFHcAyoB0w28wKgY2Zy5KIiOSTWlVmA5iZAXuEK4uMUGW2iEjtZb0y28zOM7PdHsjzyE4za2Fm\n3093hkREJL8kezK7HfBvM3sbeAVYBRjQHTgS+DIwOeM5FBGRnEp66yncZjoWOA7oHWa/D8wB5mbq\n/pBuPYmI1F5ePHCXLQoUIiK1l7MH7kREpGnTCHci0iBpGNPsUaAQkQZHw5hmVyp9PXU3sylm9kyY\nPtjMzs981kREqqZhTLMrlTqKu4HpQI8w/R7w00xlSESkJhrGNLtSCRRd3P1hYBdAeCJbI9uJSM5o\nGNPsSiVQbDGzvconzOxo1NeTiOTQ0DFjGFdUVGne2KIiTtIwphlR43MUZnYEMBH4CrAY6Aqc4e4L\nM5YpPUchIjVobMOYpkNOH7gL3YwfQNSFxzuZ7BAwbE+BQkSklnIWKELHgCOIBiwqb07r7n5LujMT\n26YChYhILWUqUKTyHMVTwKfAm0BZujMgIiL5LZVA0dPdv5rxnIiISF5KpdXTdDMblvGciIhIXkrl\nimIu8LiZFQDlldju7h0yly0REckXqVRmLwNOBRa5e1bqKFSZLSJSe7nsZvwDYHG2goSIiOSXVG49\nLQX+ZWb/AD4L8zLaPFZERPJHqoFiKdAivAzQfSERqReNJ9Fw1Bgo3H1CFvIhIk2IxpNoWKqtzDaz\n29z9EjN7qorF7u6nZixTqswWadR+MWwY102fvtv8a4YN49fPPJODHDUOuXgy+/7w9+YqluksLiJ1\npvEkGpZkgWIScLi7z6pr4mZ2J1E/UWvc/dAwrzPwMNAHWAac5e4b6roNEWl4NJ5Ew5JK89j6uAsY\nnjDvKuA5dz8AmBGmRaQJ0XgSDUuyOorlwC1ErZwSpdw81swKgadiVxRvA0PcfbWZdQdmufuXE9ZR\nHYVII6fxJNIv692Mm9kq4M/Vreju16a0gd0DxXp33zO8N2Bd+XRsHQUKEZFaykVl9kepBoO6cnc3\nsyojwoQJEyreFxcXU1xcnMmsiIg0OLNmzWLWrFkZ306yK4rX3f3wem+g6ltPxe7+kZntA/xLt55E\nROovF309nZjujQVPAueG9+cCT2RoOyIikgYpjZld58TNpgJDgC7AauCXwDTgEaA31TSP1RWFiEjt\n5WzM7FxQoBARqb1cdjMuIiJNWI2Bwsw2V/FabmaPm9mXspFJERHJnVS6Gb8N+BCYGqa/AxQBrwN3\nAsUZyZl05Q2YAAAOXklEQVSIiOSFVIZCfcPdv5owb4G79zOzhe5+WNozpToKkbymsSTyUy4euCu3\nzczOBh4N02cA5V086mwu0sRoLImmJ5XK7JHAaGBNeH0PGGVmrYH/yWDeRCQPTb/99kpBAuD60lKe\nmzgxRzmSTEtlhLtS4JRqFs9Jb3ZEJN9pLImmp8ZAYWZ7AxcChbHPu7v/IIP5EpE8pbEkmp5Ubj1N\nAzoAzwElsZeINEEaS6LpSaXV0wJ375el/JRvU62eRPKYxpLITznrwsPMrgNecvesXUUoUIiI1F4u\nA8UWoA3wGbAzzHZ375DuzMS2qUAhIlJLOXuOwt3bpXujIiLScFQbKMzsIHd/y8z+q6rl7v5a5rIl\nIiL5ItkId5Pd/UIzm0UVT2C7+9cylindehLJGHW/0Xhl/daTu18Y3g5390pP0piZGkyLNEDqfkPq\nIpXnKOamOE9E8py635C6SFZHsQ/QA2gT6imM6BZUB6JWUCLSwKj7DamLZK2ehgLnAT2Bm2PzNwNj\nM5gnEckQdb8hdZGsjuIeM7sf+I67P5DFPIlIhgwdM4ZxpaWVbj+NLSpiuLrfkCRSeeDuVXc/Ikv5\nKd+mWj2JZIi632i8cvlk9m+Aj4GHga3l8919XbozE9umAoWISC3lMlAsY/fnKNzdv5TuzMS2qUAh\nIlJLOQsUuaBAISJSeznr68nMWgD/DQwmurJ4Hvizu+9MuqKIiDQKqdx6mkIUUO4hepZiNPC5u1+Q\nsUzpikJEpNZyWUfxhrt/taZ5ac2UAoWISK1lKlCk0oXH52bWN5aRIuDzdGdERETyU411FMDPgZlm\ntjRMFwLfz1iORKRa6vlVciGVgYtmmNkBwIFEldnvuHvVHcaISMao51fJlWpvPZlZ/9AxIKGb8X7A\ndcDvzKxzlvInIoF6fpVcSVZHcQewA8DMBgO/IWr5tAmYlPmsiUicen6VXEl266kg1k3H2cAd7v4Y\n8JiZLcx81kQkTj2/Sq4ku6JoZmbNw/sTgX/FlqVSCS4iaTR0zBjGFRVVmje2qIiT1POrZFiyE/5U\n4Hkz+xjYBrwAYGb7AxuykDcRiSmvsL4m1vPrcPX8KlmQ9IE7MzsG6A5Md/etYd4BQDt3fy1jmdID\ndyIitaZOAUVEJKlcPpktIiJNmAKFiIgkpUAhIiJJqZmrSBapryZpiBQoRLJEfTVJQ6VbTyJZor6a\npKFSoBDJEvXVJA2VAoVIlqivJmmoFChEskR9NUlDpSezRbJodkkJz8X6ajpJfTVJGjW6LjzMbBnR\n2Ba7gJ3u3j+2TIFCRKSWMhUoctk81oHi2JgXIiKSh3JdR5H2yCciIumVy0DhwD/N7BUzuzCH+RAR\nkSRyeevpWHdfZWZdgefM7G13f6F84YQJEyo+WFxcTHFxcfZzKCKSx2bNmsWsWbMyvp28aPVkZuOB\nLe5+c5hWZbbkHfXTJPmuUVVmm1kboJm7bzaztsBQ4Npc5EUkFeqnSZqyXNVRdANeMLMFwDzgaXef\nnqO8iNRI/TRJU5aTKwp3Xwr0y8W2RepC/TRJU5br5rEiDYL6aZKmTIFCJAXqp0masrxo9ZRIrZ4k\nH6mfJsl3ja6vp2QUKEREai9TgUK3nkREJCkFChERSSqXXXiIZI2eqhapOwUKafT0VLVI/ejWkzR6\neqpapH4UKKTR01PVIvWjQCGNnp6qFqkfBQpp9PRUtUj96IE7aRL0VLU0BXoyW0REkmpUAxeJ1Iae\ngRDJLQUKyWt6BkIk91SZLXlNz0CI5J4CheQ1PQMhknsKFJLX9AyESO4pUEhe0zMQIrmn5rGS9/QM\nhEhq9ByFiIgkpecopMHScxAiDZsChWSUnoMQafhUmS0ZpecgRBo+BQrJKD0HIdLwKVBIRuk5CJGG\nT4FCMkrPQYg0fGoeKxmn5yBEskPPUUhOqGmrSMOh5ygk69S0VURAdRSShJq2iggoUEgSatoqIqBA\nIUmoaauIgAKFJKGmrSICavXUqKWjxZKatoo0HGoeK7VSZYuloiKG3XabTvQijVSmAoVuPTVSarEk\nIumiQNFIqcWSiKSLHrjLU/WtX1CLJRFJFwWKPJSOJ6KHjhnDuNLSSmmMLSpiuFosiUgtqTI7D/1i\n2DCumz59t/nXDBvGr595JuV01GJJpGlRX09NSLrqFwaPGKHAICL1pkCRIfWpY1D9gojkEwWKDKhv\nHYPqF0Qkn6iOIgPSUceg+gURqa1GVUdhZsOBPwDNgL+4+025yEd16ts0NR11DKpfEJF8kfVAYWbN\ngD8CJwIrgH+b2ZPu/lY60q/vST4dTVPzrY5h1qxZFBcX52TbjZHKM71UnvkvF1cU/YEl7r4MwMwe\nAr4J1DtQzC4p4Y9jxrCxeXN2tGpFy+3beXfMGCD1k/z0229n4MqVDDvwwIo0xnzwAc9NnFirZxjO\nWrKkUj467NzJxbWoYyiZOZPbn3iCHWa0dGfMaacx4vjjU14/nsY78+Zx4IAB9UojHfmoaxr5kId4\nGrksz3wri1yWZ759j3w4RjIlF4GiJ/BhbHo5MCAdCf/pxht5rXdvSsePr5hXdO21/O+NN6Z8kv9/\n69fz0IABldIovfZa+q9bl3I+NrduzYsDBrDyhz+smNdj0iTOa906pfVLZs7kkqlTKR058os8PPAA\nQMo7T6U0Nm3i/W9/u35ppCMfdUgjH/KwWxo5Ks+8LIt0pFGH8szL75GjNCqtn6G+3HLR11PGaqlf\n2bWr0gkeoHT8eF4pK0s5jZebN68yjXnNm6ecxu1PPFEpSACs/OEPmThtWsrrx3cagNKRI1NevzGl\nkQ95yJc08iEP+ZJGPuQhX9Koav10y3qrJzM7Gpjg7sPD9NVAWbxC28wabpMnEZEcahTjUZjZHsA7\nwAnASmA+8N10VWaLiEh6Zb2Owt0/N7P/AZ4lah47RUFCRCR/5eUDdyIikj/ybuAiMxtuZm+b2Xtm\ndmWu85OvzGyZmb1hZq+b2fwwr7OZPWdm75rZdDPrFPv81aFM3zazobH5R5jZm2HZbbn4LrlgZnea\n2WozezM2L23lZ2YtzezhMP9lM+uTvW+XfdWU5wQzWx720dfN7OTYMpVnNcysl5n9y8wWm9kiMxsT\n5udu/3T3vHkR3YpaAhQCzYEFwEG5zlc+voClQOeEeb8FrgjvrwR+E94fHMqyeSjbJXxxNTkf6B/e\n/x0YnuvvlqXyGwQcDryZifIDfgL8b3h/NvBQrr9zDspzPHBZFZ9VeSYvy+5Av/C+HVGd7kG53D/z\n7Yqi4mE8d98JlD+MJ1VLbN1wKnBPeH8PcFp4/01gqrvv9OhBxyXAADPbB2jv7vPD5+6NrdOoufsL\nwPqE2eksv3hajxE13mi0qilP2H0fBZVnUu7+kbsvCO+3ED2M3JMc7p/5FiiqehivZ47yku8c+KeZ\nvWJmF4Z53dx9dXi/GugW3vcgKsty5eWaOH8FTbu801l+Ffuyu38ObDSzzhnKdz672MwWmtmU2K0S\nlWeKzKyQ6EptHjncP/MtUKhmPXXHuvvhwMnARWY2KL7Qo2tKlWcdqfzS4v+A/YB+wCrg5txmp2Ex\ns3ZEv/YvcffN8WXZ3j/zLVCsAHrFpntROSJK4O6rwt+1wONEt+1Wm1l3gHDZuSZ8PLFc9yUq1xXh\nfXz+iszmPK+lo/yWx9bpHdLaA+jo7qn3A9MIuPsaD4C/EO2joPKskZk1JwoS97l7eSdOOds/8y1Q\nvALsb2aFZtaCqJLlyRznKe+YWRszax/etwWGAm8SldW54WPnAuU72JPAd8yshZntB+wPzHf3j4BN\nZjbAzAwYHVunKUpH+U2rIq0zgBnZ+AL5JJzMyn2LaB8FlWdS4btPAf7j7n+ILcrd/pnrGv4qavxP\nJqrlXwJcnev85OOL6HJ+QXgtKi8noDPwT+BdYDrQKbbO2FCmbwPDYvOPIDqAlwC35/q7ZbEMpxL1\nDPAZ0b3a76ez/ICWwCPAe8DLQGGuv3OWy/MHRJWnbwALw0mtm8ozpbI8DigLx/fr4TU8l/unHrgT\nEZGk8u3Wk4iI5BkFChERSUqBQkREklKgEBGRpBQoREQkKQUKERFJSoFCGiwz25KBNPuY2XerWVYY\n70Y7E8xsbDa3J5IKBQppyDLxENB+wDkZSDdVV+dw2yJVUqCQBs/Mis1slpk9amZvmdn9sWXLzOwm\niwZ5mmdmRWH+3WZ2euxz5Z2u/QYYFAbauSTF7R8Rtv+KmT0T649nlpn9Jmz3HTM7LsxvY2aPhIFp\n/hYGjjnCzH4DtA7bvo8oEDYzs0lhAJtnzaxVWgpNpBYUKKSx6AdcQjSIy5fMbGCY78AGd/8q8Efg\nD7H5VbkSeMHdD3f3Gkf8C523TQROd/cjgbuA62PbaObuA4BLiQbygWjQmE/c/SvANUTdLLi7XwV8\nGrY9mmgsh/2BP7r7IcAGoCK4iWTLHrnOgEiazHf3lQBmtoBopK+5YdnU8Pch4NYa0qlqoJ1kDgS+\nQjQ2CESjNK6MLf9b+PtayBPAsYSA5e6LzeyNJOkvdffy5a/G0hDJGgUKaSx2xN7vovp9u/xK4nPC\nFbWZFQAt6rHtxe4+sJpl5flKzFOqASnxe7WuZd5E6k23nqQpODv2t/wqYxnRLR+IhoVsHt5vBtrX\nIu13ga5mdjREt6LM7OAa1nkROCt8/mDg0NiynWF8AJG8oUAhDZlX8z7Rnma2ELgY+GmYNxkYEm5T\nHQ2UN7VdCOwyswXVVGYfaGYflr+AbxD1539TSOt14Jga8vu/RMFlMfBrYDGwMSybBLwRq8xO/F7q\n7lmyTt2MS6NmZkuBIzyPRkMLt7qau/uO0ArrOeAAj8YuFsk7usSVxi4ffwm1BWaGFlMG/LeChOQz\nXVGIiEhSqqMQEZGkFChERCQpBQoREUlKgUJERJJSoBARkaQUKEREJKn/D0bed0EjBcfaAAAAAElF\nTkSuQmCC\n", | |
"text/plain": [ | |
"<matplotlib.figure.Figure at 0x9abfc50>" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
} | |
], | |
"source": [ | |
"# Plot insertion sort\n", | |
"line1, = plt.plot([x[0] for x in worst_time_insertion], [x[1] for x in worst_time_insertion], 'ro', label='Worst Case')\n", | |
"line2, = plt.plot([x[0] for x in best_time_insertion], [x[1] for x in best_time_insertion], 'co', label='Best Case')\n", | |
"\n", | |
"plt.legend(handles=[line1, line2], loc=1)\n", | |
"plt.xlabel(\"Input Length\")\n", | |
"plt.ylabel(\"Sorting Time (s)\")\n", | |
"plt.title(\"Worst/Best Case Time Complexity for Insertion Sort\")\n", | |
"plt.show()" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 28, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [], | |
"source": [ | |
"# Merge sort, inplace sort.\n", | |
"# Worst case: all input, O(nlgn)\n", | |
"# Best case: all input, O(nlgn)\n", | |
"# For natural merge sort, a variant of merge sort, the bese case is O(n)\n", | |
"\n", | |
"merge_input = copy.deepcopy(input_list)\n", | |
"\n", | |
"worst_time_merge = []\n", | |
"best_time_merge = []\n", | |
"\n", | |
"for length in merge_input:\n", | |
" # Worst case.\n", | |
" start = time.time()\n", | |
" merge_sort(merge_input[length], 0, length)\n", | |
" duration = time.time() - start\n", | |
" worst_time_merge.append([length, duration])\n", | |
" # Best case.\n", | |
" start = time.time()\n", | |
" merge_sort(merge_input[length], 0, length)\n", | |
" duration = time.time() - start\n", | |
" best_time_merge.append([length, duration])" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 29, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAZQAAAEZCAYAAACw69OmAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xt8FNXd+PHPNzEQkECIIAgCkYCIvSDVAqKGeAMUBVqt\nVIFWW4H+qgm2tiKgBfqISh9vgM9TgeKtoKj1EaixQksaASlQVLAigkRRbiJKuEowkO/vjzlZN8vu\nZpPsZjfJ9/167Ss7Z2bOnD2Zne/OzDlzRFUxxhhjaiop3gUwxhhTP1hAMcYYExUWUIwxxkSFBRRj\njDFRYQHFGGNMVFhAMcYYExUWUEy9ICKXiMgH8S5HbRORbSJyeQ3ziGrdicgPRGS7iBwSkR7Rytck\nPgsoAURkvIi8FpD2YYi0G6K43UwRKRORk/4nIjJLREaJyM0icsJ9UQ+JSJGI/CIK275ZRFZEsNwA\nEVkuIgdF5HMRKRSRa2u6/QjLONzvc3/l6qp8+qCqrlDVc2qjLK48N4nIOrf9XSLymohcVFvb96Pu\nVf0MAurOBanLapDlQ8AvVTVNVTfUpGyuPIXu//3dgPRXXHp2TbdRUyKSLiJPishu9/3YLCLjapBf\noYj8PJplrA0WUE72BtBXRARARM4ATgHOKz/Yu7QsYHlVMhaR5EgWC5I2EMh37990X9Q04DrgDyJy\nXlXKUR0icj3wIvA00F5VTwd+B9RKQFHV+X6f+ypgZ/m0qjavjTKUE5FfA48C9wGnAx2A/wEG12Y5\nYkgJvh9Wyn1vOgLvV3P9YMckBTYDP/Fb7jTgQuDzam7nlOqsF8ajQFPgHLc/Dga2VqNc4uqgbvY4\nV1V7+b2ARsARoKebvgF4EigEvueX9qF73w5YDHwJfAjc6pfXZOAvwJ+BA8DPgF7AOjf9GfCQW/ZT\noAw45F69Xfp3gQ3u/c3AioDyrgF+7DfdB1gFFAPrgX5+824GioCDwEfATcA5QAlw3G13X5A6EVe+\nO8PUWxZQAHwB7AXmAS385o8DdrhtfwBc5pf33Xhfvi+AF4CWlfyPcoDt4dKAbcBvgHfd55oLtAH+\n5ur+70B6JPUWsJ0WLr/rwpSvMfAYsNO9HgUa+ZVzB/BbvIPhLmAocDWwxe1HdwfZhxa4unsL+K7f\n/I8jqUvgj8Bf/NabBvwjsO7w9tUTwFfuc/4WeBW4PeAzvgsMCfK5D+Ptx4f55jvSHe/7Uwy8B1zr\nt87TrmyvuXUuC1Kf/wTuBbYD4tJuB/7XpWVH8PkzXbl+BnziypMEPIy3v37k8iwDkvz+13Pd/2gH\n8F/l84KU8T+B9REwvy/wb2A/sBa40G9eId6Pk5Wu3ufhfR+Puv/BjHgfFyN9xb0AifjCOzDe4d4/\nDtzi/uH+aX9y75e76UZAD7yDxKVu3mTga2Cwm04F/gUMd9NN+SZwdPLfmf3Kcjcw1b2/Gb+Aghec\nioEubrq9+yINdNNXuOnTgFPxDqRd3bw2wLnu/U8JCFQBZTjHla1TmGWygMuBFKAV3pneo25eN7yA\n1NZNdwQ6u/dj8Q7k7dy6TwDPVfL/yaHygPKxy7e1y3sP8Lb7HzUGlgG/q6TeWgXZ9kCgNPD/FLDM\n7922W7nXm8Dv/cpZCtwDJAO3um3Nd/+jc/EOKp0C9qEfuuXvxDv4Jft9zssqq0ugCd6v/J8Cl+Ad\nRNuFqbvL/KZ/BKz2m+7hynxKiM9f5vf/TcE7wN+Nd6Z/KV5gPNvNfxrvIHuhm24cJL9/Aj8Hlvj9\nj9bg/QjwDyjhPn+mK9fTri5SgV8AG93y6cA/8IJpeUB5BS/YNcHbj9YAo0N85jl4wfJm3HfMb14G\n3vd0OF4Q+zGwj2+CXSHeD6Dubv4p7jP/LN7Hwqq+4l6ARHwBk4D/c+/X4x0sB/ilbQBG4l3qOA6c\n6rfu/cBT7v1koDAg7zdcequA9PIdPjCgLAcucu9vxjsYFbsvZRkw3W/ZccCzAeu/jnepoKlb74dA\nk4BlbiZ8QLnIbatRFepwKPC2e98F74B+OZASsNz7VDx4nYF3AA13wM4hsoByo9/0X4D/8Zu+HXil\nsnoLsu3hwO5KPvtW3IHPTfcHPvYr51d880s7zdXt9/2WX8c3P0ImA6v85gneL+aL/D5neUAJW5d4\nP0D24R28hlVSd/75pLr1stz0Q8DjYT6/f0C5JLC+gOeASe7908DTldRneUAZ7tY9B9js5vkHlJCf\nn2++X5l+8wuAUX7Tl7tlkvB+cJUAqX7zbwQKQpQxFRjv/ndf412tKA9+I/ELyC5tFfBTv883Odhn\njvT7ligvu4cS3HLgYhFpCbRW1SK8M4u+Lu1bbpl2eJeIjvit+yneL95yOwLy/jlwNrBJRNaKyKBQ\nhRCRdLwvzyq/5NWq2lK967RtgW+LyP1uXifgRyJSXP7CCwZtVfUrYBjer7JdIvKqiHSLsD6+dH/P\nCFPWNiKyQER2iMgBvEsnpwGo6lbgDryD4x4Red7dhwLvi/6KX3nfxwvSbSIsWzh7/N4fDZguAZq5\n9yHrLUieXwKtQlzrL9cO77JKuU9dmi8PdUcNV65gZW3mN+3bh9x6OwLyK5dJmLpU1bV4ZzcAL4Up\nfwWqWoJ3/2yku0fyY7z/byTa4R30/X3iV34NMj9oMYD/Ay4DbgOeDbJMJpXvS/7bOiNg2v+72gnv\nLGe3X35P4J2pnFw41RJVfUBVL8Db718EXnLHi3Z4+4A//zoILJcv22DbSmQWUIJbjXf9dBTe5QpU\n9SDeL8PRwC5V/cRNZ4iI/5e/IxV3zAo7hapuVdWbVLU13nXsv4hIk8DlnAHAMr+DTwWq+jnel6z8\nxvinwJ9dwCl/panqH9zyS1W1P96B8gO80/STyhjEZrwd/vowy9yPd7ng26raAu9XmW//UtXnVfUS\nvC+qus9eXuaBAWVuqqq7KylTdYS60Ry23gL8CzgG/CDMdnbhHdzKdXRp1dWh/I0LZGeGyC9sXYrI\nbXiXZncBd4XZXrD94Rm8M4QrgK9UdU2EZd8FdChv5OJ0wru3VCWqehTvHtgvCB7QItmX/D/bbvzq\nNuD9drz/82l+ebVQ1e9EUM5DwAN4lzAz8T5rp4DFAusgsM7rXDABCyhBuR13HfBrKrbkWunS3nDL\nbcc7e3hARBq7Zo0/w7upFpSIjBCR8l85B/B2nDK8a9pleJfXyl3NN627guV1Gt6B7T2XNA+4VkT6\ni0iyiKSKSI6ItBeR00VkiIicinfZ7AheAADv1/GZIpISoj7Ufe57XRPj5iKSJCIXi8gst1gzl+dB\nEWmPdzO3vJxni8hlItIY70ta4rftJ4D7RaSjW7a1iNR2a6mQ9Ra4oKoewGvd9j+uPpuKSIqIXCUi\n5UHyeeAeEWklIq3c8pH+og/mfPH6dpyCd6ZXgvejJ1DIuhSRs/FuKg/HuwR6l4TuI7KHivshqvov\nvH31IYKfHYSyGu8S312unnKAa/AaGUDVW5NNwGswEfiLH6q+L70IjBWRdu5qwDjcgdwFoaXAIyKS\n5vb3rFBNlEXkXhG5QEQaiUgq3v2cYrwfY38DzhaRG0XkFBEZhnfl4VX/LAKyPOl/UBdYQAntDbzT\n25V+aSvwbrL6B5kb8X6F7MI7W/idqha4ecrJvzQGAO+JyCG81j8/VtVj7pLUVOBNEdknIn3wrr2/\n7reuAheK63+Bd0q/B8gFUNUdwBC8L93nuJZZeDtrEvArvF9FX+Jd2/5/Lt9leDcnPxORoM0wVfVl\nvEtmP3N5fIZ383mhW2QK8D28IPlX4GW/z94Y7xfbXrxfha3wrjcDTMdrJbdURA7inQH0ClaGwCJF\nmBZqvu9/E6begn4/VPURvAB7j9/yv8S7iQteA451eC2h3nXv7wtTznDlVmARXt3vwwsIP1TVE0GW\nDVqXrrn6n4EHVfU/7hLkBODPfj8i/MvwAF5ALHZNpMs9C3yHMD+YAvNS1VK8M+ir8P7/jwMjVXWL\n37IR/xpX1d2quirE7Mr2pcDtzMELGu/itZ7LB06oapmb/xO8M7r38er+JYJfBgXvx+BTeJ9xJ979\nmEGq+pWqfokXRO/Ea8zwG+AaVd0XpmzTgevdseCxENtMOOU3BmO3AZGBeE0ok/FaRk0LmH8O3j+i\nJzBRVR926R3wduDT8Sp7tqrOiGlhE4iI9MJrLtgn3mUx8SMik/Ba8Y1MgLKMxLuJHfeOhLEgIlcB\nf1TVzHiXpa6K6RmK+2X0OF5Ty3OBG0Wke8BiX+L9wn4oIL0U+JWqfguveeBtQdatzxSvtZlp2KrV\nwTDaRKQp3s3w2fEuS7S4S5tXu8tQ7XGtO+Ndrros1pe8egFbVXWbO/VdgHdpwUdV96rqOrwA4p/+\nmaqud+8PA5sI3rKlXlLVf6vqkniXw8RdlS4JxYKIDMC7tLcbr9lufSF4LQ/34fVR2oh3v8tUU7Qf\nPxCoPSc3y+td1UxEJBPvklikLUuMqRdUdUoClGEJFZsx1wuu8U0k9+tMhGJ9hlLjX1auSe5fgLHu\nTMUYY0wCivUZyk5Obucd2NEvJNcC5WVgnqouDDK/TrbVNsaYeFPVqN+fi/UZyjqgq3iPZm+E1/Rx\ncYhlK3w41xFqLvC+qoZsNlfTRwXY65vXpEmT4l6G+vSy+rS6TNRXrMT0DEVVj4vI7XgPdUsG5qrq\nJhEZ4+bPEpG2eE/hbA6UichYvBZh5wEjgHdF5B2X5XhVff2kDRljjIm7WF/yQlX/htdT1D9tlt/7\nz6h4WazcSqzjpTHG1Bl2wDY+OTk58S5CvWL1GT1Wl3VDzHvKx5KIaF0uvzHGxIOIoDG4KR/zS17G\nmLqv4sOCTV1Smz+6LaAYYyJiVwPqntr+IWD3UIwxxkSFBRRjjDFRYQHFGGNMVFhAMcYYExUWUIwx\nddYDDzzA1VdfXSGta9euQdNefPHFqG1327ZtJCUlUVZWFna5LVu28KMf/YjWrVuTnp5Ojx49ePTR\nRytdr66ygGKMqbbl+fncM2AAk3NyuGfAAJbn59dqHv369WPVqlW+Fmi7d+/m+PHjrF+/3nfQ3r17\nN0VFRWRnV22gyRMngo2yXFG4lm9FRUX07t2bTp068d5777F//35eeukl3nrrLQ4dOlSlstQZ8X5I\nWQ0fcKbGmNgL9l1749VXdUJWlir4XhOysvSNV1+NON+a5nHs2DFt2rSpvv3226qq+sILL+gtt9yi\n/fr107feesuX1qVLF1VV3blzp1577bWakZGhXbp00Tlz5vjymjRpkl533XU6YsQIbd68uc6dO1fX\nrFmj559/vjZv3lzbtGmjd955p6qqdujQQUVEmzVrps2aNdPVq1efVLbhw4frNddcE7b8119/vbZt\n21ZbtGih2dnZunHjRt+8/Px8PffcczUtLU3bt2+vDz30kG/eX//6V+3Ro4emp6dr37599d133w2a\nf6hjpEuP/jE5FpnW1ssCijG1I9h3bWL//hUCQfnrngEDIs43Gnlceuml+uijj6qq6m233aZPPvmk\nTpw4sULaz3/+c1VVveSSS/S2227TY8eO6fr167V169ZaUFCgql5ASUlJ0UWLFqmq6tGjR7VPnz46\nb948VVU9cuSIL3Bs27ZNRURPnDgRslxt27bVp59+OmzZn3rqKT18+LB+/fXXescdd+h5551XYf2V\nK1eqqur+/ft9QfPtt9/W008/XdeuXatlZWX6zDPPaGZmph47duyk/Gs7oNglL2NMtZxy7FjQ9OSS\nklrNo1+/fixfvhyAlStXkp2dzSWXXOJLW7FiBf369WP79u2sWrWKadOm0ahRI3r06MGtt97Ks88+\n68urb9++DB48GIDU1FQaNWrEhx9+yBdffEHTpk3p3dsbcNY7Jof35ZdfcsYZZ4Rd5uabb+bUU08l\nJSWFSZMmsWHDBt/lsEaNGrFx40YOHjxIixYt6NmzJwCzZ89mzJgxfP/730dE+MlPfkLjxo1ZvXp1\nxHUWKxZQjDHVcrxx46DpJ1JTazWP7OxsVq5cSXFxMXv37iUrK4sLL7yQVatWUVxczMaNG8nOzmbX\nrl1kZGRw6qmn+tbt2LEjO3fu9E2feeaZFfKeO3cuW7ZsoXv37vTq1Yv8KtzfOe2009i1a1fI+WVl\nZdx999106dKFFi1acNZZZyEifPHFFwC8/PLLvPbaa2RmZpKTk+MLGJ988gkPP/wwLVu29L127NjB\n7t27Iy5brFhAMcZUS/+8PCZmZVVIm5CVxZW5ubWaR58+fThw4ABz5szhoosuAqB58+a0a9eO2bNn\n065dOzp16kS7du3Yt28fhw9/M5L4p59+WiGIBD6qpEuXLjz33HPs3buXcePGcf3113P06NGIHmly\nxRVX8PLLL4ecP3/+fBYvXsyyZcs4cOAAH3/8sf/lfC644AIWLlzI3r17GTp0KDfccAPgBcGJEydS\nXFzsex0+fJhhw4ZFXGexYgHFGFMt2YMGMWD6dO4dMIDJ/fpx74ABDJw+nexBg2o1jyZNmnDBBRfw\nyCOPVGjJdfHFF/PII4/Qr18/ADp06EDfvn0ZP348x44d49133+XJJ59kxIgRIfOeN28ee/fuBaBF\nixaICElJSbRu3ZqkpCSKiopCrjtlyhRWrVrFXXfdxZ49ewDYunUrI0eO5MCBAxw+fJjGjRuTkZHB\nkSNHmDBhgm/d0tJS5s+fz4EDB0hOTiYtLY3k5GQARo0axRNPPMHatWtRVY4cOUJ+fn6FQBk3sbgx\nU1sv7Ka8MbUi0b9r48eP16SkJH3nnXd8aS+++KImJSXp7NmzfWk7duzQa665RjMyMjQrK0tnzZrl\nmzd58mQdOXJkhXxHjBihp59+ujZr1ky//e1v+27Yq6r+7ne/09atW2t6erquWbMmaLk2b96sP/rR\nj/S0007TFi1aaI8ePXT69Ol64sQJPXz4sA4ZMkTT0tI0MzNTn332WU1KStKioiL9+uuvdeDAgdqy\nZUtt3ry59urVS998801fvq+//rp+//vf1/T0dD3jjDP0hhtu0EOHDp20/VD/N2J0U97GQzHGVMqN\nnxHvYpgqCvV/i9V4KHbJyxhjTFRYQDHGGBMVFlCMMcZEhQUUY4wxUWEBxRhjTFRYQDHGGBMVFlCM\nMcZEhQUUY4wxUWEBxRhjTFRYQDHG1GmZmZk0bdqUtLQ0MjIyuOaaa9ixY0dU8i0oKAi7zMGDB7nj\njjvo1KkTaWlpdOnShV/96ld8+eWXNd5+XRTTgCIiA0XkAxH5UETGBZl/joj8S0RKROTOqqxrjIm/\n/IICBuTlkTN2LAPy8siv5AAcizxEhFdffZVDhw6xe/du2rRpQ24VnlYcLt9wj5v5+uuvufzyy9m0\naRNLlizh0KFD/Otf/6JVq1asXbu2xtuvk2LxgDD3T0gGtgKZQAqwHugesExr4ALgPuDOqqyr9nBI\nY2pNsO/aq8uWadattyr//KfvlXXrrfrqsmUR5xuNPDIzM3WZ3/L5+fl69tln+6ZLSkr0zjvv1I4d\nO2qbNm30F7/4hR49elRVVffu3auDBg3S9PR0zcjI0EsuuUTLysp0xIgRmpSUpE2aNNFmzZrpf//3\nf5+03Tlz5mibNm30yJEjIcv2wAMPaFZWlqalpem5556rr7zyim/ehx9+qNnZ2dqiRQtt1aqVDhs2\nzDdv06ZNesUVV2hGRoZ269ZNX3zxxYjrw1+oYyR1cMTGXsBWVd2mqqXAAmBIQDDbq6rrgNKqrmuM\nia8ZCxdSNHx4hbSi4cOZuWhRreYB34yg+NVXX/HCCy9w4YUX+ubdfffdbN26lQ0bNrB161Z27tzJ\n73//ewAefvhhOnTowBdffMHnn3/OAw88gIjw5z//mY4dO/rOfH7zm9+ctM1//OMfXHXVVTRt2jRk\nubp06cLKlSs5ePAgkyZNYsSIEb5H2d97770MHDiQ/fv3s3PnTvLy8gA4cuQIV155JSNGjGDv3r0s\nWLCAX/7yl2zatKlKdRLM8vx87hkwoMb5hBLLgNIe2O43vcOlxXpdY0wtOBZikKnIB++NTh6qytCh\nQ2nZsiXp6eksW7bMFwBUlTlz5vDII4+Qnp5Os2bNGD9+PAsWLAC8YXZ3797Ntm3bSE5O9g3QFYl9\n+/ZVOsTv9ddfT9u2bQG44YYb6Nq1q+9yWKNGjdi2bRs7d+6kUaNG9O3bF4BXX32Vs846i5/+9Kck\nJSVx3nnn8cMf/pCXXnqpCrVysuX5+SwZO5b7li6tUT7hxDKg1ORZ1/acbGMSXOMQ9xciH7w3OnmI\nCIsWLaK4uJhjx44xc+ZM+vXrx+eff87evXv56quvOP/8833D5V511VW+YXZ/+9vf0qVLF/r3709W\nVhbTpk2LeLuVDfEL8Oyzz9KzZ0/ftt977z3ftv/whz+gqvTq1Ytvf/vbPPXUU4A3xO+aNWsqDPH7\n3HPP+c5sqmvpjBlMDTMgWDScEsO8dwId/KY74J1pRHXdyZMn+97n5OSQk5NTlTIaY6opb+hQiubP\nr3DJKmvePHJvuqlW8/AnIvzgBz9gzJgxrFy5kqFDh9KkSRPef//9oGcTzZo146GHHuKhhx5i48aN\nXHbZZfTq1YtLL7200mF+r7jiCu655x6++uqroJe9PvnkE0aPHk1BQQEXXnghIkLPnj19l+fatGnD\n7NmzAXjzzTe54ooryM7OpmPHjvTr14+lUTyTKCwsZOXmzUyOWo7BxTKgrAO6ikgmsAsYBtwYYtnA\n/1zE6/oHFGNM7Rl02WUAzHzlFUrwzipyb7rJl15becA391BUlcWLF1NcXEz37t1JSkpi1KhR3HHH\nHTz++OO0bt2anTt3snHjRvr3709+fj7dunUjKyuL5s2bk5ycTFKSd+GmTZs2FBUVcVmIsowcOZJZ\ns2Zx3XXX8dhjj9G1a1eKi4uZNWsWPXv2pFOnTogIrVq1oqysjGeffZb33nvPt/5LL73EhRdeyJln\nnkl6ejoiQnJyMtdccw1333038+bN840Tv379etLS0jjnnHOqVC/lcnJyuLhbNyZ/8gkAU6qVSwRi\ncae//AVcBWzGa7E13qWNAca4923x7pUcAIqBT4FmodYNkn+VWjwYY6onkb9rmZmZvtZYaWlp+p3v\nfEefe+453/ySkhKdMGGCdu7cWZs3b67du3fXmTNnqqrqo48+qpmZmXrqqafqmWeeqffdd59vvUWL\nFmnHjh01PT1dH3744aDbPnDggN5xxx3aoUMHbdasmWZlZemdd96p+/btU1XViRMnakZGhrZq1Up/\n/etfa05Ojs6dO1dVVe+66y5t3769b705c+b48t28ebMOGjRIW7duraeddppefvnlumHDhirXjf//\n7Y1XX9Ufde6s/bt1syGAg7EhgI2pHTYEcN3k/3/LLyhg9J/+xK7Ro+HSS20IYGOMMdUzY+FCL5jE\nkAUUY4xpAEI10Y4mCyjGGNMAhGqiHU0WUIwxpgHIGzqUrPnzY7qNWDYbNsYYkyD8m2gvidE2rJWX\nMaZS1sqrbgr1f3PpUb+pYmcoxpiIVNZz3Bi7h2KMqVQsOsHZK/LXgw8+SPqVV8I//+l7pV95JQ8+\n+GCl69Ymu+RljDEJrvNFF/Hx1Kknp0+cSNGbb1Y5v1hd8rIzFGOMSXBlKSlB00+ESI8XCyjGGJPg\nkkoDxyD0JIdIjxcLKMYYk+DGDB5M+v33V0hLnzqV0YMHx6lEwdk9FGOMqQOmTZvG7MWLOZGSQnJp\nKaMHD2bcuHHVyitW91AsoBhjTANjN+WNMcYkNAsoxhhjosICijHGmKiwR68YY0wtWJ6fz9IZMzjl\n2DGON25M/7w8sgcNinexosoCijHGxNjy/HyWjB3L1KIiX9pE974+BRW75GWMMTG2dMYM+u7axYBu\n3cjp0YMB3brRd9cu/j5zZryLFlV2hmKMMTH2UXExC3r3pmjSJF9a0ZQp9Nq3L46lij47QzHGmBhb\nnZJSIZgAFE2axJoEexZXTVlAMcaYGGveuXPQ9LQQ6XWVBRRjjImxNi1bBk1vm5FRyyWJLbuHYowx\nlcgvKGDGwoUcE6GxKnlDh/rGaI9E3tChFM2fT9Hw4b60rHnzyL3pplgUN24soBhjTBj5BQWMff75\nCsGgaP58gIiDSvlyM195hRIgFci96aYqBaW6wB4OaYwxYQzIy2PpD394cvorr/D69OlxKFHN2cMh\njTEmDvYUFwdN/6yeNfmNBgsoxhgTxsGPPgqafihEekMW04AiIgNF5AMR+VBEgo4EIyIz3PwNItLT\nL328iGwUkf+IyHMi0jiWZTXGmGD6lJaSNWVKhbSsKVPonWDD7yaCmN2UF5Fk4HHgCmAn8G8RWayq\nm/yWuRrooqpdRaQ38Eegj4hkAqOA7qp6TEReAH4MPBOr8hpjTDCdW7Zk+IoVzBwzhpImTUg9epTc\n7dtZnZ0d76IlnFi28uoFbFXVbQAisgAYAmzyW2YwLkio6hoRSReRNsBBoBRoKiIngKZ4QckYY2pV\n/7w8lhQV8fqWLb60CVlZDMzNjWOpElPYgCIiKUB/IBvIBBT4BFgOLFHV42FWbw9s95veAfSOYJn2\nqvq2iDwMfAocddv6R6Wfxhhjoqz8acD3zpxJckkJJ1JTGZibW6+eEhwtIQOKiNwLXAf8C1gLFODd\nczkDuBaYKiJ/UdX7QmQRaXvek5quiUgWcAdeEDsAvCQiw1V1fuCykydP9r3PyckhJycnws0aY0xk\nsgcNqtMBpLCwkMLCwphvJ2Q/FBEZDPw1VEcPEUkCrlHVxSHm9wEmq+pANz0eKFPVaX7LPAEUquoC\nN/0B0A/IAa5U1Vtd+kigj6reFrAN64dijDFVVOv9UFR1ceDRWkSSRKS5m18WKpg464CuIpIpIo2A\nYUDg8ouBn7i8+wD7VXUPsBnv5nwTERG8G/vvV/GzGWOMqUWV3pQXkeeBMcAJ4N9ACxGZrqp/CLee\nqh4XkduBJUAyMFdVN4nIGDd/lqq+JiJXi8hW4Ahwi5u3XkSexQtKZcDbwOxqf0pjTIPVEIbeTRSV\nPnpFRDaoag8RGQ58D7gbeFtVv1MbBQzHLnkZY8JZnp/P43l5HEhJ4VhqKo1LSmhRWsrtM2Y06KAS\nq0tekQRn6WFXAAAY30lEQVSUjcB5wHPA/6hqoYi8q6rfjXZhqsoCijEmnGEXX8xbAYNbZU2ZwgWl\npSxYuTKOJYuveD7LaxawDWgGLHedDg9EuyDGGBNt606cCDpS4rqysjiVqH6rNKCo6gxVba+qV6lq\nGV4/lPr1zGVjTL10PDU1aHppiHRTMyEDiojcLCIn3bRXT6mINBKRW2JbPGOMqb42bdsGTW8bIt3U\nTLhWXs3wnr/1AV5rq914nRDbAhcA5wBzYl5CY4yppkmjRjF69mx2jR7tS2s3axa/GzUqjqWqv8Le\nlHd9QC4CLgY6uuRPgJXAqnjfEbeb8saYyuQXFDBz0aJvRkocMqTejZRYVXFr5ZXILKAYY0zVxSqg\n2JjyxpiElV9QwIyFCzkmQmNV8oYObfBnF4nMAooxJiHlFxQw9vnnKRo+3JdWNN97PqwFlcRkQwAb\nYxLSjIULKwQTgKLhw5m5aFGcSmQqU2lAEZG2IjJXRF530+eKyM9jXzRjTEO2p7g4aPpn+/bVcklM\npCI5Q3kaWAq0c9MfAr+KVYGMMQbg4EcfBU0/FCLdxF8kAaWVqr6A97RhVLUUCDdSozHG1Fif0lKy\npkypkJY1ZQq9S0vjVCJTmUhuyh8WkdPKJ9y4JfYsL2NMTHVu2ZLhK1Ywc8wYSpo0IfXoUXK3b2d1\ndna8i2ZCiCSg3An8FegsIquA1sD1MS2VMaZeqMlYJP3z8lhSVMTrW7b40iZkZTEwNzdWxTU1VGlA\nUdW3RKQfcDbeo1c2u8texhgT0vL8fJaMHcvUoiJf2kT3PpKgUr7MvTNnklxSwonUVAbm5jbocUwS\nXSTjoZwCDAIy+SYAqao+EtuiVc56yhuTuO4ZMIALV6xgRseOvsGt8j79lNXZ2fzX66/Hu3gNWjx7\nyv8VOAr8B284XmOMqdRHxcUs6N27wngkRVOm0Mua/dZbkQSU9okwOqMxpm5ZnZLCx0EGt9KJE+NU\nIhNrkTQbXioiA2JeEmNMvdK8c+eg6Wkh0k3dF8kZyirgFRFJAspvxquqNo9dsYwxdV2bli2DprfN\nyKjlkpjaEskZyiNAH6Cpqqa5lwUTY0xYeUOHkuUe5lgua948cocMiVOJTKxFcobyKbDRjSdvjDER\nKX8i8MxXXvlmcKubbrInBddjkTQbfgY4C/gb8LVLtmbDxhhTR8Wz2fDH7tXIvQSwo7gxxpgKbAhg\nY0xQ06ZNY9bixZSlpJBUWsqYwYMZN25cvItloqDWz1BEZLqqjhWRvwaZrao6ONqFMcYkhmnTpvHg\nsmXsnzrVl/bg/fcDWFAxIYU8QxGR76vqv0UkJ8hsVdU3YlqyCNgZijGx0fmii/jYL5j40idOpOjN\nN+NQIhNNsTpDCddseDaAqhYGeUUUTERkoIh8ICIfikjQnzUiMsPN3yAiPf3S00XkLyKySUTed4/N\nN8bUgrKUlKDpJ0KkGwMxHFNeRJKBx4GBwLnAjSLSPWCZq4EuqtoVGA380W/2dOA1Ve0OfBfYFKuy\nGmMqSgoxiFWyDW5lwgjXyqu1iPwar1VXoEiaDfcCtqrqNgARWQAMoWJgGAw84zJc485K2gAlwCWq\n+lM37zg2qJcxtWbM4ME8eP/97J8wwZeWPnUqowfbrVMTWriAkgyk1SDv9sB2v+kdQO8IljkTb7jh\nvSLyFNADeAsYq6pf1aA8xpgIld94nz1xIidSUkguLWW0tfIylQgXUD5T1Slh5lcm0rvlgWdAileu\n7wG3u4YBjwF3A78LXHny5Mm+9zk5OeTk5FSnrMaYAOPGjbMAUk8UFhZSWFgY8+2Ea+X1jqr2DDoz\nkoy9m+iTVXWgmx4PlKnqNL9lngAKVXWBm/4A6IcXZP6lqme59IuBu1X1moBtWCsvY4LILyhgxsKF\nHBOhsSp5Q4faI0+MTzx6yl9Rw7zXAV1FJBPYBQwDbgxYZjFwO7DABaD9qroHQES2i8jZqrrFlWVj\nDctjTIOQX1DA2Oefp2j4cF9akXtIowUVE0shW3mp6pc1ydjdSL8dWAK8D7ygqptEZIyIjHHLvAZ8\nJCJbgVnAL/2yyAXmi8gGvFZe99ekPMY0FDMWLqwQTACKhg9n5qJFcSqRaSgieZZXtanq3/AeKumf\nNitg+vYQ624Avh+70hlTP+0pLg6a/pkNvWtiLGb9UIwx8XHwo4+Cph8KkW5MtFQaUETkUJDXDhF5\nRURsLE9jEkyf0lKyplRsoJk1ZQq9rVOiibFILnlNx+sr8ryb/jGQBbwDPAnkxKRkxphq6dyyJcNX\nrGDmmDGUNGlC6tGj5G7fzurs7HgXzdRzkQSUwar6Xb/p2SKyXlXHuabAxpgE0j8vjyVFRby+ZYsv\nbUJWFgNzc+NYKtMQRBJQvhKRYcBLbvp6vEejgA20ZUzCyR40CIB7Z84kuaSEE6mpDMzN9aUbEyuR\nDAGchXfZq/xpv6uBO4CdwPmqujKmJQxfNuvYaIwxVRSrjo02YqMxxjQwcRtTXkROB0YBmX7Lq6r+\nLNqFMcbY0Lum7orkHsoiYDnwd6DMpdlpgTExYEPvmrosknso61X1vFoqT5XYJS9T39jQu6Y2xGMI\n4HKviog1DzGmFtjQu6YuiySg3AH8VURK/HrKH4x1wYxpiGzoXVOXVRpQVLWZqiapaqqqprlX89oo\nnDENzZjBg0m/v+KDtW3oXVNXhBtgq7t73Pz3gs1X1bdjWrII2D0UUx9NmzaN2YsX29C7JmZqvR+K\niMxR1VEiUkiQVl2qemm0C1NVFlCMMabq4taxUURSVbWksrR4sIBiEtHy/HyWzpjBKceOcbxxY/rn\n5dljT0xCiVvHRmAVEHjZK1iaMQ3e8vx8Hs/L40BKCsdSU2lcUsKWvDwACyqm3gt3yesMoB0wH7gJ\nELxLX82BJ1T1nNoqZCh2hmISzbCLL+atlBSKJk3ypWVNmcIFpaUsWBm3x94ZU0E8zlD6AzcD7YGH\n/dIPAROiXRBj6oN1J07w0X33VUgrmjQJJthXxtR/IQOKqj4jIvOAH6vq/FoskzF11vHU1KDppSHS\njalPwvZDUdUTwK9rqSzG1Hlt2rYNmt42RLox9UkkPeX/LiK/EZEOIpJR/op5yYypgyaNGkW72bMr\npLWbNYvf3XprnEpkTO2JpNnwNk7uh6Kq2jlWhYqU3ZQ3iSi/oICZixZRAqQCuUOGMOiyy+JdLGN8\nbICtICygGGNM1cVzgK1GwP8DsvHOVN7AazZsT6szxhjjE8klr7l4gecZvL4oI4Hjqhr3i8J2hmKM\nMVUXz0evvKuq360sLR4soJhos+F3TUMQz0evHBeRLqq61RUkCzge7YIYE282/K4xNRPJGcrlwFPA\nxy4pE7hFVQsqzVxkIPAYkAz8SVWnBVlmBnAV8BVws6q+4zcvGVgH7FDVa4Osa2coJmps+F3TUMTt\nDEVVl4nI2UA3vJvym1X1WGXruWDwOHAFsBP4t4gsVtVNfstcDXRR1a4i0hv4I9DHL5uxwPtAWhU+\nkzHVYsPvGlMzITs2ikgv94BI3KPqzwPuA/47wo6NvYCtqrrNtQhbAAwJWGYw3s1+VHUNkC4ibdz2\nzwSuBv6E1xjAmJiy4XeNqZlwPeVnAccARCQbeBDv4H8QmB1mvXLtge1+0ztcWqTLPAr8FiiLYFvG\n1JgNv2tMzYS75JWkqvvc+2HALFV9GXhZRDZEkHekNzcCzz5ERK4BPlfVd0QkJ9zKkydP9r3Pyckh\nJyfs4saEVH7jffbEiTb8rqlXCgsLKSwsjPl2wo2H8h7QU1VLRWQzMFpV33DzNqrqt8JmLNIHmKyq\nA930eKDM/8a8iDwBFKrqAjf9AZAD5OH6u+A9vaI58LKq/iRgG3ZT3hhjqihWN+XDXfJ6HnhDRBbj\ntcBa4QrSFdgfQd7rgK4ikul62w8DFgcssxj4icu3D7BfVT9T1Qmq2kFVzwJ+DBQEBhNjjDGJJdx4\nKFNFpABoCyxV1fJ7GQLkVpaxqh4XkduBJXjNhueq6iYRGePmz1LV10TkahHZChwBbgmVXeQfyTRU\nNpa7MfFlD4c09cLy/HyWjB3L1KIiX9rErCwGTJ9uQcWYAPG45GVMnbF0xgz67trFgG7dyOnRgwHd\nutF31y7+PnNmvItmTIMRyaNXjEl4HxUXs6B3b2/8dqdoyhR67dsXZi1jTDTZGYqpF1anpFQIJgBF\nkyaxxnq5G1NrLKCYeqF55+ADiKaFSDfGRJ8FFFMvtGnZMmh624xInhJkjIkGCyimXsgbOpSs+fMr\npGXNm0fukMDHxxljYsWaDZt6I7+ggJmLFlGC93iF3CFDGHTZZfEuljEJJ24jNiYyCyj1i42WaEzt\niOeIjcbEnI2WaEzdZ2coJiHYaInG1B7rKW/qNRst0Zi6zwKKSQg2WqIxdZ8FFJMQbLREY+o+u4di\nEsa0adOYvXixjZZoTIxZs+EgLKAYY0zVWbNhk9DyCwqYsXAhx0RorEre0KHWqdCYBsYCiqmx/IIC\nxj7/PEXDh/vSitxjUCyoGNNw2E15U2MzFi6sEEwAioYPZ+aiRXEqkTEmHiygmBrbU1wcNP0zG9zK\nmAbFAoqpsYMffRQ0/VCIdGNM/WQBxdRYn9JSsqZMqZCWNWUKva1TojENit2UNzXWuWVLhq9Ywcwx\nYyhp0oTUo0fJ3b6d1dnZ8S6aMaYWWUAxNdY/L48lRUW8vmWLL21CVhYDc3PjWCpjTG2zjo0mKpbn\n5/P3mTNJLinhRGoqV+bmkj1oULyLZYwJwnrKB2EBJTqsU6IxDYv1lDcxYZ0SjTHRYq28GjjrlGiM\niRYLKA2cdUo0xkRLzAOKiAwUkQ9E5EMRCfoschGZ4eZvEJGeLq2DiPxTRDaKyHsikhfrsjZE1inR\nGBMtMQ0oIpIMPA4MBM4FbhSR7gHLXA10UdWuwGjgj25WKfArVf0W0Ae4LXBdU3PWKdEYEy2xvinf\nC9iqqtsARGQBMATY5LfMYOAZAFVdIyLpItJGVT8DPnPph0VkE9AuYF1TQ9Yp0RgTLbEOKO2B7X7T\nO4DeESxzJrCnPEFEMoGewJpYFLIhs06JxphoiXVAibSTSGB7aN96ItIM+AswVlUPR6tgxlPe+fBe\nv06JA61TojGmGmIdUHYCHfymO+CdgYRb5kyXhoikAC8D81R1YbANTJ482fc+JyeHnJycmpa5TolG\np8TsQYMsgBhTjxUWFlJYWBjz7cS0p7yInAJsBi4HdgFrgRtVdZPfMlcDt6vq1SLSB3hMVfuIiODd\nW/lSVX8VIv8G3VM+WKfErPnzmX7jjdYp0RgTUqx6yse0lZeqHgduB5YA7wMvqOomERkjImPcMq8B\nH4nIVmAW8Eu3+kXACOBSEXnHvQbGsrx1jXVKNMYkkpg/ekVV/wb8LSBtVsD07UHWW4l1vAzLOiUa\nYxKJHbDrMOuUaIxJJBZQ6jDrlGiMSST2tOE6zDolGmMSiQWUOsw6JRpjEokNsBVnNe1HYiMlGmOq\nykZsDKKuBxTrR2KMiYc62Q/FhGf9SIwx9YkFlDiyfiTGmPrEAkocWT8SY0x9YgEljqwfiTGmPrFm\nw3Fk/UiMMfWJBZQ4sn4kxpj6xJoNx5n1IzHG1DbrhxJEvAPK8vx8ls6YwSnHjnG8cWP65+VZMDDG\nJLxYBRS75FVNy/PzWTJ2LFOLinxpE917CyrGmIbIWnlV09IZM+i7axcDunUjp0cPBnTrRt9du/j7\nzJnxLpoxxsSFnaFU00fFxSzo3ZuiSZN8aUVTptDLOiUaYxooO0OpptUpKRWCCUDRpEmsSUmJU4mM\nMSa+LKBUU/POnYOmp4VIN8aY+s4CSjW1adkyaHrbjIxaLokxxiQGCyjVlDd0KFnz51dIy5o3j9wh\nQ+JUImOMiS/rh1ID+QUFzFy0iBIgFcgdMsTGMTHGJDzr2BhETQLKtGnTmLV4MWUpKSSVljJm8GDG\njRsX5RIaY0zisY6NUTRt2jQeXLaM/VOn+tIevP9+AAsqxhhTTQ3yDKXzRRfxsV8w8aVPnEjRm29G\no2jGGJOwbAjgKCoL0VfkhPUhMcaYamuQASUpxABWyTawlTHGVFuDDChjBg8m3d0zKZc+dSqjBw+O\nU4mMMabui+k9FBEZCDwGJAN/UtVpQZaZAVwFfAXcrKrvVGHdGrXymr14MSdSUkguLWW0tfIyxjQQ\nda7ZsIgkA5uBK4CdwL+BG1V1k98yVwO3q+rVItIbmK6qfSJZ161f5wfYSiSFhYXk5OTEuxj1htVn\n9FhdRlddvCnfC9iqqttUtRRYAAR2Ix8MPAOgqmuAdBFpG+G6JsoKCwvjXYR6xeozeqwu64ZYBpT2\nwHa/6R0uLZJl2kWwrjHGmAQSy4AS6bWoqJ92GWOMqX2xvIfSB5isqgPd9HigzP/muog8ARSq6gI3\n/QHQDzirsnVdut1AMcaYaqhrj15ZB3QVkUxgFzAMuDFgmcXA7cACF4D2q+oeEfkygnVjUiHGGGOq\nJ2YBRVWPi8jtwBK8pr9zVXWTiIxx82ep6msicrWIbAWOALeEWzdWZTXGGFNzdfpZXsYYYxJHne0p\nLyIDReQDEflQRKxHYggisk1E3hWRd0RkrUvLEJG/i8gWEVkqIul+y493dfqBiPT3Sz9fRP7j5k2P\nx2eJBxF5UkT2iMh//NKiVn8i0lhEXnDpq0WkU+19utoVoi4ni8gOt3++IyJX+c2zugxDRDqIyD9F\nZKOIvCcieS49fvunqta5F95lsK1AJpACrAe6x7tcifgCPgYyAtL+ANzl3o8DHnTvz3V1meLqdivf\nnMWuBXq5968BA+P92Wqp/i4BegL/iUX9Ab8E/te9HwYsiPdnruW6nAT8OsiyVpeV12db4Dz3vhle\nZ/Du8dw/6+oZinV8rJrAxgu+DqXu71D3fgjwvKqWquo2vB2ut4icAaSp6lq33LN+69RrqroCKA5I\njmb9+ef1MnB51D9EgghRlxC864DVZSVU9TNVXe/eHwY24fXXi9v+WVcDSiSdJo1HgX+IyDoRGeXS\n2qjqHvd+D9DGvW+HV5fl/Dua+qfvpGHXdzTrz7cvq+px4ICIZMSo3IkqV0Q2iMhcv8szVpdV4FrE\n9gTWEMf9s64GFGtJELmLVLUn3gM4bxORS/xnqncua/VZTVZ/NfZHvH5n5wG7gYfjW5y6R0Sa4Z09\njFXVQ/7zanv/rKsBZSfQwW+6AxUjrHFUdbf7uxd4Be9y4R73zDTc6e7nbvHAej0Tr153uvf+6Ttj\nW/KEFo362+G3TkeX1ylAC1XdF7uiJxZV/Vwd4E94+ydYXUZERFLwgsmfVXWhS47b/llXA4qv06SI\nNMK7WbQ4zmVKOCLSVETS3PtTgf7Af/Dq6qdusZ8C5TviYuDHItJIRM4CugJrVfUz4KCI9BYRAUb6\nrdMQRaP+FgXJ63pgWW18gEThDnjlfoC3f4LVZaXc558LvK+qj/nNit/+Ge+WCjVo4XAVXquGrcD4\neJcnEV94lxLWu9d75fUEZAD/ALYAS4F0v3UmuDr9ABjgl34+3pd9KzAj3p+tFuvwebynNXyNdy35\nlmjWH9AYeBH4EFgNZMb7M9diXf4M7wbwu8AGd+BrY3UZcX1eDJS57/c77jUwnvundWw0xhgTFXX1\nkpcxxpgEYwHFGGNMVFhAMcYYExUWUIwxxkSFBRRjjDFRYQHFGGNMVFhAMfWaiByOQZ6dROSkEUTd\nvEz/x7PHgohMqM3tGRMpCyimvotFR6uzgJtikG+kxsdx28aEZAHFNAgikiMihSLykohsEpF5fvO2\nicg08QYiWyMiWS79aRG5zm+58gfvPQhc4gaEGhvh9s93218nIq/7PWupUEQedNvdLCIXu/SmIvKi\nGzzp/9zgRueLyINAE7ftP+MFzGQRme0GWVoiIqlRqTRjqsgCimlIzgPG4g001FlE+rp0Bfar6neB\nx4HH/NKDGQesUNWeqlrp6JXuAX4zgetU9QLgKWCq3zaSVbU3cAfegFPgDWz0pap+C7gX79EYqqp3\nA0fdtkfijSXSFXhcVb8N7Ad8QdCY2nRKvAtgTC1aq6q7AERkPd6odavcvOfd3wXAo5XkE2xAqHC6\nAd/CG5cGvBFHd/nN/z/3921XJoCLcIFNVTeKyLth8v9YVcvnv+WXhzG1ygKKaUiO+b0/Qej9v/zM\n5DjuLF5EkoBGNdj2RlXtG2JeebkCyxRp4Ar8XE2qWDZjosIueRnjGeb3t/ysZRvepSbwhkJNce8P\nAWlVyHsL0FpE+oB3CUxEzq1knTeBG9zy5wLf8ZtX6samMCahWEAx9Z2GeB+opYhsAHKBX7m0OUA/\nd3msD1DeBHkDcEJE1oe4Kd9NRLaXv4Br8caSmObyege4sJLy/i9eENoI/BewETjg5s0G3vW7KR/4\nuewR4iYu7PH1psETkY+B8zWBRvdzl9hSVPWYa3X2d+Bs9cb1NiYh2WmzMYn5i/5UoMC1EBPg/1kw\nMYnOzlCMMcZEhd1DMcYYExUWUIwxxkSFBRRjjDFRYQHFGGNMVFhAMcYYExUWUIwxxkTF/wcoWeoW\nW26FWwAAAABJRU5ErkJggg==\n", | |
"text/plain": [ | |
"<matplotlib.figure.Figure at 0x99e68b0>" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
} | |
], | |
"source": [ | |
"# Plot merge sort\n", | |
"line1, = plt.plot([x[0] for x in worst_time_merge], [x[1] for x in worst_time_merge], 'ro', label='Worst Case')\n", | |
"line2, = plt.plot([x[0] for x in best_time_merge], [x[1] for x in best_time_merge], 'co', label='Best Case')\n", | |
"\n", | |
"plt.legend(handles=[line1, line2], loc=1)\n", | |
"plt.xlabel(\"Input Length\")\n", | |
"plt.ylabel(\"Sorting Time (s)\")\n", | |
"plt.title(\"Worst/Best Case Time Complexity for Merge Sort\")\n", | |
"plt.show()" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 23, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [ | |
"# Quicksort, inplace sort.\n", | |
"# Worst case: unbalanced input, e.g. small range of numbers, O(n^2)\n", | |
"# Best case: random input, O(nlgn)\n", | |
"\n", | |
"import sys\n", | |
"sys.setrecursionlimit(10000)\n", | |
"\n", | |
"quick_input_best = copy.deepcopy(input_list)\n", | |
"# Worst case: few unique numbers.\n", | |
"quick_input_worst = {}\n", | |
"for i in range(1000, 21000, 1000):\n", | |
" values = [random.randint(0, 10) for x in range(i)]\n", | |
" quick_input_worst[i] = values\n", | |
"\n", | |
"worst_time_quick = []\n", | |
"best_time_quick = []\n", | |
"\n", | |
"for length in quick_input_worst:\n", | |
" # Worst case.\n", | |
" start = time.time()\n", | |
" quicksort(quick_input_worst[length], 0, length)\n", | |
" duration = time.time() - start\n", | |
" worst_time_quick.append([length, duration])\n", | |
" # Best case.\n", | |
" start = time.time()\n", | |
" quicksort(quick_input_best[length], 0, length)\n", | |
" duration = time.time() - start\n", | |
" best_time_quick.append([length, duration])" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 27, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAEZCAYAAACXRVJOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8VNX9//HXJwhBZBNBEARig1qtFawWFQXiRlBQ+dat\nVWht1W/7qxWtWxW0YKtS26pFbL8q4gqutbilVSw0IqLiBgpVlFRUliKyg4JAPr8/7km8CZNkQmYy\nk+T9fDzmkTt3OefMyZ37mXvPufeYuyMiIpKT6QKIiEh2UEAQERFAAUFERAIFBBERARQQREQkUEAQ\nERFAAUGyjJn1N7P3M12O+mZmi83suDqmkdK6M7P/MbNPzWyDmfVOVbp1YWZ/N7MRSaxX5/psihpt\nQDCzq83s75XmfVjFvDNTmG+emZWa2Q51a2Z3mtkFZnaumW0PX7QNZlZiZj9LQd7nmtlLSaxXaGYz\nzWy9mX1mZsVmdnJd80+yjOfEPvcXoa7K3q9395fc/Zv1UZZQnrPN7I2Q/7JwwDmqvvKP8fDa+QQq\n1V04KB5bhyT/CPzc3du4+7y6lC1WpqFmNsfMNprZ52Y22cy6Jbu9u5/k7g8msypJ1qeZnWpmc81s\nnZmtNLPpZpaXbJkqpVVgZp/uzLbZoNEGBOBFoJ+ZGYCZ7QXsAvQpO1iHefnAzNokbGbNklktwbzB\nQFGYfjl80doApwG/N7M+tSnHzjCz04HHgPuAbu6+J/BroF4CgrtPiX3uE4GlZe/dvW19lKGMmV0K\n3ApcD+wJdAf+DJxSn+VIIyfxflij8L3pAfx7J7dP9IPodGAKcAuwB/AtYAswy8za70w+dWVmvYD7\ngV+6eztgH6J9YPtOpLVLiotX/9y9Ub6AFsAm4JDw/kzgHqAY+E5s3odhuivwNLAK+BA4P5bWWOCv\nwIPAOuAnQF/gjfD+v8Afw7qfAKXAhvA6PMw/GJgXps8FXqpU3teA78feHwHMBtYAc4GBsWXnAiXA\neuA/wNnAN4HNwLaQ7+oEdWKhfJdVU2/5wAzgc2AlMBloF1v+K2BJyPt94NhY2lcBi8K2jwK71/A/\nKgA+rW4esBi4HHgnfK5JQGfgH6HuXwDaJ1NvlfJpF9I7rZry5QJ/ApaG161Ai1g5lwBXAJ8By4Bh\nwEnAB2E/uirBPvRIqLs3gYNjyz9Kpi6B/wP+GtvuJuCfleuOaF/dDnwRPucVwLPALyp9xneAUxN8\n7o1E+/FGvv6OHED0/VkDzAdOjm1zXyjb38M2xybY9z4GLk8w/13gulg9PRhbnhfKkRPeFwPnxZZf\nQBS01gMLgD4J6vMAou/JWQn+x6cDb9dxH7gSWE70Q+uLUO8bQpm61Pexry6vjBcgrR8uOrBdEqZv\nB35M9GswPu/uMD0zvG8B9Cb6kh8T20m/Ak4J71sCrwDnhPet+PrA3zO+A8fKchVwQ5g+l1hAIAou\na4Be4X03ogPB4PD++PB+D2A3ogPhvmFZZ+DAMP0jKgWaSmX4Zihbz2rWyQeOA5oDHYnOtG4Ny/Yn\nCihdwvsewDfC9MVEB+KuYds7gIdq+P8UUHNA+Cik2ymkvQJ4K/yPcoHpwK9rqLeOCfIeDGyt/H+q\ntM5vQt4dw+tl4Dexcm4FrgGaAeeHvKaE/9GBRAeHnpX2oe+F9S8jOkg1i33OY2uqS2BXYGH4X/cn\nCtpdq6m7Y2PvzwBejb3vHcq8SxWfvzT2/21OFKCuIjrTPobogLdfWH4fsBY4MrzPTXbfC3Xzcmy6\nuoDwL+Ansc+zBDg0tu/2iH924DtEgeikKj7jPsCXRGctBUDrndgHxoX6aQkMpNI+3ZBeGS9AWj8c\njAH+Fqbnhh2mMDZvHjCC6FLBNmC32LY3AvfGdtLiSmm/GOZ3rDS/wg4cmz8TOCpMnxt2pDXhS1UK\njI+t+yvggUrbPwf8kCj4rCE6sOxaaZ1zqT4gHBXyalGLOhwGvBWmexEdkI8Dmlda799UPPjsRXQA\nrO6AW1D5y1N5Xvhi/yD2/q/An2PvfwFMraneEuR9DrC8hs++iBBcwvtBwEexcn4BWHjfJtTtd2Pr\nv8HXPyLGArNjy4zorOKo2OcsCwjV1iXRD4jVRGdPZ8XWS1R38XRahu3yw/s/ArdX8/njAaF/5foC\nHgLGhOn7gPuqSevoqvY94GfAwlg9JRsQngcuqiK/j4DrgE+BATX8nw8nOgv7jCg43Es4FiSxD2yJ\nf6bK/4OG9mrMbQgQHYSPNrPdgU7uXkL0y75fmPetsE5Xokssm2LbfkL0i7PMkkppnwfsB7wXGsmG\nVFWIcH30m0S/NMq86u67e3TdvAtwkJndGJb1BM4wszVlL6KDeRd3/wI4i+hLtMzMnjWz/ZOsj1Xh\n717VlLWzmT1iZkvMbB3RpYc9ANx9EXAJ0Zd2hZk9HNphIPriTo2V999EQbZzkmWrzorY9JeV3m8G\nWofpKustQZqrgI6JrnXHdCX6dVnmkzCvPA0PR4FQrkRlbR17X74Phe2WVEqvTB7V1KW7zyE6uwB4\nvJryV+Dum4kua4wIbQTfJ/r/JqMr0cE17uNY+T3B8rjPw99E+95eRJdda2tvokuniRjwU6Izj2rb\nCN39NXc/y6P2tP7AAGB0WFzTPrDS3b/aibJnpcYeEF4lulZ8AdGpHu6+nuiX2f8Cy9z94/C+g5nF\nv7w9qBgEnPgb90Xufra7dyK6jvtXM9u18npBITA9dvCowN0/A/7G1w27nxD9Sto99mrj7r8P609z\n90FEB7r3gYmJypjAQqIv7enVrHMj0TXQgzxqZBtBbD9x94fdvT/RwdfDZy8r8+BKZW7l7strKNPO\nqKqhtNp6q+QVol93/1NNPsuIDs5leoR5O6t72UQIRHtXkV61dWlmFxJd2lxGdP26Kon2h/uJzo6O\nB75w99eSLPsyoHtZJ42gJ9F19WQsJPo+VejRF+rhNGBamLWR6Cy4TKJgXuZTorPWRJwoIPQ0s1uS\nLCPu/gYwlejHItS8D1Su45q+g1mtUQcEd/+S6LT9Uir2JJoV5r0Y1vuU6Nf7ODPLNbODiRqOJ1eV\ntpkNN7NO4e06oh2hlOiabinR5akyJ/F176JEae1BdGCaH2ZNBk42s0Fm1szMWobubN3MbM/QTW43\nostOm/i6R8QKYG8za15FfXj43NeGLqptzSzHzI42szvDaq1DmutDd8ArYuXcz8yONbNcooPp5lje\ndwA3mlmPsG4nM6vv3jpV1lvlFd19HVHvqj+H+mxlZs3N7EQzKwtyDwPXmFlHM+sY1k/2F3Uih1rU\nt38XojOtzUQ/Wiqrsi7NbD/gt0QH9R8CV1rV9wisoOJ+iLu/QrSv/hF4oBZlf5XoEtmVoZ4KgKFE\njeRQQ2+msO9dTlSfPwj/my7A3URtQbeHVecCA8ysu5m1A66uJtm7gcvN7DsW6VVWZ8EGoraiAWY2\nLlECZnaUmZ1f9l02s28S/TAr+7/Udh9YAexhZvXaYy5lMn3NKt0vvv7F2yc274ww74LYvG7AM0SX\nEhYB/xtbNoYdr00/SPTP30DUS+KU2LLriK5Hribq9bKcWFsDUYNgWW+gDSGdKZXW6UvUo2JVSOsZ\nol+UXcL8tURtCTOAb4ZtmhP1JFkFfFZNnRQSBcgNIe0ZwIlh2YFEQXQDUePtpcAnYdm3iXpDrQ95\nPM3XDcwG/JLojGV9qMPra/jfFJSlXdU8drwO/iChETm8Pw+YVkO9da+mDGcDrxP9Ml0e1j8iLMsF\nxhP9IlxG1NukRRXl3CXsUz1i814Czo7tQ49TsZdRn0Sfs6q6JGqMfg24Mrbdz4h6CjVPUKZTiC53\nrAEujc2/huhHS14N/5/thDaE2L5RTLTvzSfWO4nouvtvkvg+ngLMIfrRURqmu1Ra5/ZQ5g+IGuu3\nk6ANIbz/aainDaEeeieoz92JAs11CcrzLaL9+L8hjY+IGonLGvuT3gdiaU4iukS2uvJny/ZXWYNY\n2pjZYqKdejuw1d37pjXDLGNmfYHb3P2ITJdFMsfMxhD1IqvxLtt6KMsIoh9DAzJcjhOIOgmc4FG7\niGRYfdxI4UCBu6+uh7yykRP9OpSmbaduEEs1M2sFXMjXl2gyxt1fMLNziLqGKiBkgfq6sy4rvgyZ\n4O6vZ7oMkhWcDDc4mlkh8ATRzXwPZbIsZdz92UyXQb5WH5eM/kPU6LoduNPdJ9awiYiIZEB9nCEc\n5e7LQyv+C2b2vrvX+AA2ERGpX2kPCB76Trv7SjObStQL5CUAM2vQfXZFRDLF3VN+KT6t9yGEvt1t\nwvRuRLd9vxtfJ9PdrBrTa8yYMRkvQ2N6qT5Vn9n6Spd0nyF0JroFvyyvKe4+rfpNREQkE9IaENz9\nIyDtz/gXEZG6a9SPrmhqCgoKMl2ERkX1mVqqz+yX9m6n1WZu5pnMX0SkITIzPA2Nyg1/yDcRqVHF\nh5RKQ1KfP5oVEESaCJ2NNzz1HcjVhiAiIoACgoiIBAoIIiINxMyiIq4pLExb+uplJNIEhF4pmS6G\n1FL8/zazqIjnL76YG0pKMBrgoytERKozbtw4TjrppArz9t1334TzHnvssZTlu3jxYnJycigtLa12\nvQ8++IAzzjiDTp060b59e3r37s2tt95a43bpMO2227ihpCSteSggiDRhZZcgxhYUcE1hITOLqhz6\nOy1pDBw4kNmzZ5f/Cl6+fDnbtm1j7ty55Qfd5cuXU1JSwoABtRvgbfv27TWuU91ZU0lJCYcffjg9\ne/Zk/vz5rF27lscff5w333yTDRs21KosqbDLli3pzyTDD2hyEUm/RN+1F5991kfl57tD+WtUfr6/\n+OyzSadb1zS2bNnirVq18rfeesvd3R999FH/8Y9/7AMHDvQ333yzfF6vXr3c3X3p0qV+8skne4cO\nHbxXr14+ceLE8rTGjBnjp512mg8fPtzbtm3rkyZN8tdee80PPfRQb9u2rXfu3Nkvu+wyd3fv3r27\nm5m3bt3aW7du7a+++uoOZTvnnHN86NCh1Zb/9NNP9y5duni7du18wIABvmDBgvJlRUVFfuCBB3qb\nNm28W7du/sc//rF82TPPPOO9e/f29u3be79+/fydd95JmH78/zZ60KDyOg7zU39MTkeiSWeugCBS\nLxJ91+IHmPjrmsLCpNNNRRrHHHOM33rrre7ufuGFF/o999zjo0ePrjDvvPPOc3f3/v37+4UXXuhb\ntmzxuXPneqdOnXzGjBnuHgWE5s2b+1NPPeXu7l9++aUfccQRPnnyZHd337RpU/mBf/HixW5mvn37\n9irL1aVLF7/vvvuqLfu9997rGzdu9K+++sovueQS79OnT4XtZ82a5e7ua9euLQ96b731lu+5554+\nZ84cLy0t9fvvv9/z8vJ8y5YtO6Qf/7/Fg2+6AoIuGYk0UVVdgmi2eXO9pjFw4EBmzpwJwKxZsxgw\nYAD9+/cvn/fSSy8xcOBAPv30U2bPns1NN91EixYt6N27N+effz4PPPBAeVr9+vXjlFNOAaBly5a0\naNGCDz/8kM8//5xWrVpx+OGHA8ndpLdq1Sr22muvatc599xz2W233WjevDljxoxh3rx55ZeTWrRo\nwYIFC1i/fj3t2rXjkEMOAeCuu+7ipz/9Kd/97ncxM374wx+Sm5vLq6++Wm1eA4YMoXD8eK5NYy8j\nBQSRJmpbbm7C+dtbtqzXNAYMGMCsWbNYs2YNK1euJD8/nyOPPJLZs2ezZs0aFixYwIABA1i2bBkd\nOnRgt912K9+2R48eLF26tPz93nvvXSHtSZMm8cEHH3DAAQfQt29fimrRvrHHHnuwbNmyKpeXlpZy\n1VVX0atXL9q1a8c+++yDmfH5558D8MQTT/D3v/+dvLw8CgoKyg/4H3/8MTfffDO77757+WvJkiUs\nX7685roaMoTfPvdc0p+hthQQRJqoQSNHMjo/v8K8Ufn5nHDRRfWaxhFHHMG6deuYOHEiRx11FABt\n27ala9eu3HXXXXTt2pWePXvStWtXVq9ezcaNG8u3/eSTTyoEgcqPeujVqxcPPfQQK1eu5Fe/+hWn\nn346X375ZVKPhDj++ON54oknqlw+ZcoUnn76aaZPn866dev46KOP4pfDOeyww3jyySdZuXIlw4YN\n48wzzwSiIDZ69GjWrFlT/tq4cSNnnXVW0nWWLgoIIk1U/BLE2IEDubawkMHjxzNgyJB6TWPXXXfl\nsMMO45ZbbqnQk+joo4/mlltuYeDAgQB0796dfv36cfXVV7Nlyxbeeecd7rnnHoYPH15l2pMnT2bl\nypUAtGvXDjMjJyeHTp06kZOTQ0k13Tivu+46Zs+ezZVXXsmKFSsAWLRoESNGjGDdunVs3LiR3Nxc\nOnTowKZNmxg1alT5tlu3bmXKlCmsW7eOZs2a0aZNG5o1awbABRdcwB133MGcOXNwdzZt2kRRUVGF\nQJcx6WiYSPaFGpVF6kW2f9euvvpqz8nJ8bfffrt83mOPPeY5OTl+1113lc9bsmSJDx061Dt06OD5\n+fl+5513li8bO3asjxgxokK6w4cP9z333NNbt27tBx10UHmDs7v7r3/9a+/UqZO3b9/eX3vttYTl\nWrhwoZ9xxhm+xx57eLt27bx3794+fvx43759u2/cuNFPPfVUb9Omjefl5fkDDzzgOTk5XlJS4l99\n9ZUPHjzYd999d2/btq337dvXX3755fJ0n3vuOf/ud7/r7du397322svPPPNM37Bhww75V/V/I02N\nyrpTWaQJ0J3KDVNV/7d0jYegS0YiIgIoIIiISKCAICIigAKCiIgECggiIgIoIIiISKCAICIigAKC\niIgECggiIgIoIIhIhuXl5dGqVSvatGlDhw4dGDp0KEuWLElJujNmzKh2nfXr13PJJZfQs2dP2rRp\nQ69evfjlL3/JqlWr6px/Q6SAINKEFc2YQeHIkRRcfDGFI0dSVMMBNB1pmBnPPvssGzZsYPny5XTu\n3JmLavG01OrSre5xHV999RXHHXcc7733Hs8//zwbNmzglVdeoWPHjsyZM6fO+TdI6XhAUrIvsvyB\nWyKNRaLv2rPTp3v++ec7//pX+Sv//PP92enTk043FWnk5eX59Nj6RUVFvt9++5W/37x5s1922WXe\no0cP79y5s//sZz/zL7/80t3dV65c6UOGDPH27dt7hw4dvH///l5aWurDhw/3nJwc33XXXb1169b+\nhz/8YYd8J06c6J07d/ZNmzZVWbZx48Z5fn6+t2nTxg888ECfOnVq+bIPP/zQBwwY4O3atfOOHTv6\nWWedVb7svffe8+OPP947dOjg+++/vz/22GNJ10dcVcdINGKaiKTSbU8+Sck551SYV3LOOUx46ql6\nTQO+HsHsiy++4NFHH+XII48sX3bVVVexaNEi5s2bx6JFi1i6dCm/+c1vALj55pvp3r07n3/+OZ99\n9hnjxo3DzHjwwQfp0aNH+ZnH5ZdfvkOe//znPznxxBNp1apVleXq1asXs2bNYv369YwZM4bhw4eX\nPwr72muvZfDgwaxdu5alS5cycuRIADZt2sQJJ5zA8OHDWblyJY888gg///nPee+992pVJ5mggCDS\nRG2pYpCY5Ae/TE0a7s6wYcPYfffdad++PdOnTy8/gLs7EydO5JZbbqF9+/a0bt2aq6++mkceeQSI\nhqlcvnw5ixcvplmzZuUD7CRj9erVNQ6Refrpp9OlSxcAzjzzTPbdd9/yy0ktWrRg8eLFLF26lBYt\nWtCvXz8Ann32WfbZZx9+9KMfkZOTQ58+ffje977H448/XotayQwFBJEmKreK6+vJD36ZmjTMjKee\neoo1a9awZcsWJkyYwMCBA/nss89YuXIlX3zxBYceemj5cJMnnnhi+TCVV1xxBb169WLQoEHk5+dz\n0003JZ1vTUNkAjzwwAMccsgh5XnPnz+/PO/f//73uDt9+/bloIMO4t577wWiITJfe+21CkNkPvTQ\nQ+VnFlktHdehkn2hNgSRepHou5bw+v9559W9DaGWaVRuQ3B379Spkz/xxBO+fft2b9WqlS9btqzG\ndObPn+977rmnz5gxw93d99lnnx3Sjbv77ru9S5cuVbYhLF682HNzc/3ll1/20tJSd3fv06ePT5o0\naYd1Z82a5S1btvRFixb5ww8/7CeccEKN5U1GVcdI1IYgIqk05NhjGf+DH1A4dSoDp06lcOpUxp99\nNkOOPbZe04Cv2xDcvfxs4YADDiAnJ4cLLriASy65pHwozKVLlzJt2jQAioqKWLRoEe5O27Ztadas\nGTk50WGtc+fO1Q6ROWLECLp3785pp53GwoULKS0tZdWqVdx444384x//YNOmTZgZHTt2pLS0lHvv\nvZf58+eXb//444+Xd49t3749ZkazZs0YOnQoH3zwAZMnT2br1q1s3bqV119/nffff79WdZIR6Ygy\nyb7QGYJIvcjm71peXl55b6A2bdr4t7/9bX/ooYfKl2/evNlHjRrl3/jGN7xt27Z+wAEH+IQJE9zd\n/dZbb/W8vDzfbbfdfO+99/brr7++fLunnnrKe/To4e3bt/ebb745Yd7r1q3zSy65xLt37+6tW7f2\n/Px8v+yyy3z16tXu7j569Gjv0KGDd+zY0S+99FIvKCgoP0O48sorvVu3buXbTZw4sTzdhQsX+pAh\nQ7xTp06+xx57+HHHHefz5s2rdd1U9X+joQ6haWbNgDeAJe5+cqVlnu78RURDaDZUjXEIzYuBfwPa\nG0VEslhaA4KZ7Q2cBNwNpDyaiYhI6qT7DOFW4AqgNM35iIhIHe2SroTNbCjwmbu/bWYFVa03duzY\n8umCggIKCqpcVUSkSSouLqa4uDjt+aStUdnMbgRGANuI7lNpCzzh7j+MraNGZZF6oEblhqm+G5XT\n3ssIwMwGAperl5FIZiggNEz1HRDSdskoAe2NIhlkVTx3SKRMvZwhVJm5zhBEpIGYWVTEtNtuY5ct\nW9iWm8ugkSMZMGRIRsrSGM4QREQapJlFRTx/8cXcEHsUxugwnamgkA56lpGISA2m3XZbhWAAcENJ\nCS9MmJChEqWHAoKISA122bIl4fxmm2sz8kP2U0AQEanBttzchPO3t6zNyA/ZTwFBRKQGg0aOZHR+\nfoV5o/LzOeGiizJUovRQLyMRkSTMLCrihQkTaLZ5M9tbtuSEiy5qdL2MFBBERBqYhvz4axERaQAU\nEEREBFBAEBGRQAFBREQABQQREQkUEEREBFBAEBGRQAFBREQABQQREQkUEEREBFBAEBGRQAFBREQA\nDaEpIk1ANo2HnM0UEESkUWsq4yGngi4ZiUij1lTGQ04FBQQRadSaynjIqaCAICKNWlMZDzkVqm1D\nMLPmwCBgAJAHOPAxMBN43t23pbuAIiJ1MWjkSEaXlFS4bDQqP5/BjWw85FSocghNM7sWOA14BZgD\nLCM6o9gL6AscAfzV3a/f6cw1hKaI1INsGg85Fep9TGUzOwV4pqojtpnlAEPd/emdzlwBQUSk1uo9\nIFRRiBygtbuvT0nmCggiIrWWroBQY6OymT1sZm3NbDdgPvCemV2Z6oKIiEhmJdPL6MBwRjAM+AdR\n4/KIdBZKRETqXzIBYZfQ22gYUZvCVqLeRiIi0ogkExDuBBYDrYGZZpYHrEtfkUREJBNq1agMYGYG\n7BLOFOqWuRqVRURqrd4blc3sXDPb4cY1j2w1sxZm9uNUF0hERDKjujuVWwOvm9n7wBvAcsCALsBh\nwDeBiWkvoYiI1ItqLxmFy0NHAUcDPcLsj4FZwOyarveYWUvgRSAXaAE85e5Xx5brkpGISC1lxY1p\nO5WBWSt3/yJcfpoFXO7us8IyBQQRqZYGt9lRugJC2gfIcfcvwmQLoBmwOt15ikjjoMFt6lfaH39t\nZjlmNhdYAfzL3f+d7jxFpHHQ4Db1K+0Bwd1L3b0PsDcwwMwK0p2niDQOGtymftV4ycjMugA3AN3c\nfbCZHQgc6e6TapORu68zsyKiHkrFZfPHjh1bvk5BQQEFBQW1SVZEGjENbhMpLi6muLg47fnU2Khs\nZs8B9wKj3f3g8BiLt939oBoTN+sIbHP3tWa2K/A8cJ27Tw/L1agsIlVK1IYwKj+fwePHN+k2hEw2\nKnd090fN7CqAcFNasiOl7QXcHx6bnQM8WBYMRERqUnbQvzY2uM3gBj64TTZL5gyhmGjktH+6+yFm\ndgRwk7sPrHPmOkMQEam1TJ4hXAY8A3zDzGYDnYDTU10QERHJrKRuTAvtBvsRPbpiYSoebBfS1RmC\niEgtZexO5XCH8RCigXHKzijc3W+pc+YKCCIitZbJS0bPAF8C7wKlqS6AiIhkh2QCQjd3PzjtJRER\nkYxK5k7laWZWmPaSiIhIRiVzhjAbmBruJShrTHZ3b5u+YomISH1LplF5MXAKMN/dU9qGoEZlEZHa\ny2Sj8ifAglQHAxFpGjSeQcORTED4CPiXmf0D+CrMS0m3UxFp3DSeQcOSTKPyR8AMogFuWgNtwktE\npFoaz6BhqfEMwd3H1kM5RKQR0ngGDUuVAcHMxrv7xWb2TILF7u6npLFcItIIaDyDhqW6M4TJ4e/N\nCZapa5CI1GjQyJGMLinZcTyDiy7KYKmkKlV2OzWzt939kLRmrm6nIo3ezKIiXoiNZ3CCxjOos3p/\nuJ0CgohIdsrEfQidzOxSokdeV6ZupyIijUx1AaEZ6l4qItJk6JKRiEgDk65LRsncmCYiIk1AdWcI\ne7j7qrRmrjMEEZFay9gQmumkgCAiUnu6ZCQiImmlgCAiIkASD7czsw0JZq8DXgcuc/f/pLxUIpIV\nNJZB05LMeAjjgU+Bh8P77wP5wNvAPUBBWkomIhmlsQyanmSG0HzH3Q+uNG+uu/cxs3nu3nunM1ej\nskjWuqawkOunTdth/rWFhfz2uecyUCIpk8lG5S/M7CwzywmvM4Gyh5nraC7SSGksg6YnmYBwDjAC\n+Cy8fggMN7NdgV+ksWwikkEay6DpqTEguHuJuw91947hNdTdF7n7l+4+qz4KKSL1b9DIkYzOz68w\nb1R+PidoLINGK5k2hD2BC4A8vm6Ednf/SZ0zVxuCSFbTWAbZKWN3KpvZK8BM4E2gNMx2d3+izpkr\nIIiI1Fon22KoAAAOdklEQVQmA8Jcd++T6oxD2goIIiK1lMleRs+amc4RRUQauWTOEDYCrYCvgK1h\ntrt72zpnrjMEEZFay8QQmgC4e+tUZyoiItmnyoBgZge4+3tm9p1Ey939rZoSN7PuwAPAnkQ3sd3l\n7rftbGFFRCR9qhsgZ6K7X2BmxSS4I9ndj6kxcbMuQBd3n2tmrYl6Kg1z9/fCcl0yEhGppUz2Mmrp\n7ptrmpdUZmZPAhPcfXp4r4AgkiZ6UmnjlbE2BGA2UPmyUaJ51TKzPOAQ4LXabCcitacnlcrOqLLb\nqZntZWaHAq3M7Dtmdmj4W0DU6yhp4XLRX4GL3X1jnUosIjWadtttFYIBwA0lJbwwYUKGSiQNQXVn\nCIOAc4FuwM2x+RuAUclmYGbNgSeAye7+ZOXlY8eOLZ8uKCigoKAg2aRFpAp6UmnjUlxcTHFxcdrz\nqbYNwcyaAd939yk7lbiZAfcDq9z9lwmWqw1BJA00lkHjlpE7ld19O3BpHdI/ChgOHGNmb4fX4Dqk\nJyJJ0JNKZWck08vod8DnwKPAprL57r66zpnrDEEkbfSk0sYrk91OF7PjfQju7t+oc+YKCCIitZax\ngJBOCggiIrWXsfsQzKwF8P+AAURnCi8Cd7j71mo3FBGRBiWZS0aTiALH/YARja+8zd3Pr3PmOkMQ\nEam1TLYhvOPuB9c0b6cyV0AQSUiPnZDqZPLRFdvMrJe7LwoFyQe2pbogIhLRYyckU5IZMe0KYIaZ\nvWhmLwIzgMvTWyyRpkuPnZBMSWaAnOlmth+wP1Gj8kJ3T3xfvIjUmR47IZlS3cPt+prZXgDhUdd9\ngOuBP5hZh3oqn0iTsy03N+H87S1b1nNJpKmp7pLRncAWADMbAPyOqKfReuCu9BdNpGnSYyckU6ob\nMW2eu/cO038GVrr72MrL6pS5ehmJJKTHTkh16r3bqZnNBw5x961mthD4X3d/MSxb4O7fqnPmCggi\nIrWWiW6nDwMvmtnnwBfAS6Eg+wJrU10QERHJrJrGQzgS6AJMc/dNYd5+QGt3f6vOmesMQUSk1vRw\nOxERATI0QI6IiDQdCggiIgIoIIiISJDMw+1EpJb0tFJpiBQQRFJMTyuVhkqXjERSTE8rlYZKAUEk\nxfS0UmmoFBBEUkxPK5WGSgFBJMX0tFJpqHSnskga6Gmlkk56dIWIiAB6dIWIiKSZAoKIiAC6MU1k\nB7rLWJoqBQSRGN1lLE2ZLhmJxOguY2nKFBBEYnSXsTRlCggiMbrLWJoyBQSRGN1lLE2ZbkwTqUR3\nGUu2053KIiICNNA7lc3sHjNbYWbvpjMfERGpu3S3IdwLDE5zHiIikgJpDQju/hKwJp15iIhIauhO\nZWlU9NgJkZ2X8YAwduzY8umCggIKCgoyVhZp2PTYCWmsiouLKS4uTns+ae9lZGZ5wDPu/u0Ey9TL\nSFLmmsJCrp82bYf51xYW8tvnnstAiUTSo0H2MhKpT3rshEjdpLvb6cPAbGA/M/vUzH6czvykadNj\nJ0TqJt29jH7g7l3dPdfdu7v7venMT5o2PXZCpG50p7I0KnrshDQFenSFiIgAalQWEZE0y/h9CCJl\ndFOZSGYpIEhW0E1lIpmnS0aSFTSWsUjmKSBIVtBNZSKZp4AgWUE3lYlkngKCZAXdVCaSeboPQbKG\nbioTSY5uTBMRESB9AUHdTiVldB+BSMOmgCApofsIRBo+NSpLSug+ApGGTwFBUkL3EYg0fAoIkhK6\nj0Ck4VNAkJTQfQQiDZ+6nQqQmh5Cuo9ApH7oPgRJm4Q9hPLzKRw/Xgd0kSykAXIkbdRDSERAAUFQ\nDyERiSggiHoIiQiggCCoh5CIRNSo3Aioh5BI06JeRpKQegiJND3qZSQJqYeQiKSKAkIDpx5CIpIq\nCggNnHoIiUiqKCBk2MyiIq4pLGRsQQHXFBYys6ioVturh5CIpIoGyMmgVAwqU7betbEeQoPVQ0hE\ndoJ6GWXQNYWFXD9t2g7zry0s5LfPPZeBEolIQ6BeRo2QGoRFJJvoklEd1eWmMDUIi0g2UUCog7q2\nAQwaOZLRJSUVth+Vn89gNQiLpFTRjBnc9uSTbDEj152Rw4Yx5NhjG1waZduniwJCHVR1U9i1EyYk\nFRDUICxVyYaDT7akkYrtL374YUrOOad8XsmUKQBJp5MNaVTYPk03nqY1IJjZYOBPQDPgbne/KZ35\n1VZdnwGUijaAAUOGKAAE2XDwyYY0suHgky1ppKIMtz35ZIXtAUrOOYcJU6c2qDQSbZ9qaQsIZtYM\nuB04HlgKvG5mT7v7e6lIv64H85lFRdw+ciTrmjdnS8uW5G7ezAcjRwLJd/nclptL0a67cluPHuVp\njPzkk1q1AaTy4LNi6VI6d+umg2Cq0pg7F/r0qfdyZMPBJy1plNVnHQ+CtS3DFkvcGac2XTeyIY2q\ntk+ldJ4h9AUWuftiADN7BDgVqHNASMXB/M/jxvFWjx6UjBlTPi//uuv4y7hxSafR5thjGe7O2lGj\nyufNufFGrjrmmKS2T/kB7L774Hvfy/yBdCfSaCwHsFSUIxsOPmlJI9RnbdJIRRlyq+jaXpuuG9mQ\nRlXbp1I6u512Az6NvV8S5tVZ2cF82h138OKf/sS0O+7grR49+Mu4cUmn8cb27RWCAUDJmDG8UVqa\ndBozli6tEAwA1o4axb+WLUtq+yoPHE89lXQZGksaWXkAy1Aa2XDwyZY0UlGGkcOGkR9+nJTJnzyZ\ni049tUGlkWj7VEvnGULawtkb27fzn+uvrzCvZMwYqHRwrs62Ki7rbK3F5Z50nQI2tANYKtLIhoNP\ntqQxctgwSqZMqRBg8ydP5qKzz066DI0ljVSUoeysbMLUqWwm+j9cdPbZtbokmg1pxLd/Pulcaydt\ndyqb2RHAWHcfHN5fDZTGG5bNrOnepiwiUgcNaoAcM9sFWAgcBywD5gA/SFWjsoiIpFbaLhm5+zYz\n+wXwPFG300kKBiIi2SujD7cTEZHskbGH25nZYDN738w+NLNfZaoc2c7MFpvZO2b2tpnNCfM6mNkL\nZvaBmU0zs/ax9a8Odfq+mQ2KzT/UzN4Ny8Zn4rNkgpndY2YrzOzd2LyU1Z+Z5ZrZo2H+q2bWs/4+\nXf2roj7HmtmSsI++bWYnxpapPqtgZt3N7F9mtsDM5pvZyDA/c/unu9f7i+gS0iIgD2gOzAUOyERZ\nsv0FfAR0qDTv98CVYfpXwO/C9IGhLpuHul3E12eBc4C+YfrvwOBMf7Z6qr/+wCHAu+moP+DnwF/C\n9FnAI5n+zBmozzHApQnWVX1WX5ddgD5hujVRm+sBmdw/M3WGUH7TmrtvBcpuWpPEKvcmOAW4P0zf\nDwwL06cCD7v7Vo9uCFwEHG5mewFt3H1OWO+B2DaNmru/BKypNDuV9RdP6wmiThSNVhX1CTvuo6D6\nrJa7/9fd54bpjUQ37XYjg/tnpgJC2m5aa4Qc+KeZvWFmF4R5nd19RZheAXQO012J6rJMWb1Wnr+U\npl3fqay/8n3Z3bcB68ysQ5rKnc0uMrN5ZjYpdolD9ZkkM8sjOvN6jQzun5kKCGrJTt5R7n4IcCJw\noZn1jy/06FxQ9bmTVH8p8X/APkAfYDlwc2aL07CYWWuiX+8Xu/uG+LL63j8zFRCWAt1j77tTMcJJ\n4O7Lw9+VwFSiy20rzKwLQDhd/CysXrle9yaq16VhOj5/aXpLntVSUX9LYtv0CGntArRz99XpK3r2\ncffPPADuJtpHQfVZIzNrThQMHnT3soEOMrZ/ZiogvAHsa2Z5ZtaCqLHj6QyVJWuZWSszaxOmdwMG\nAe8S1dWPwmo/Asp2pKeB75tZCzPbB9gXmOPu/wXWm9nhZmbAiNg2TVEq6u+pBGmdDkyvjw+QTcJB\nq8z/EO2joPqsVvjsk4B/u/ufYosyt39msIX9RKJW9UXA1Zlu8c/GF9Fp+Nzwml9WT0AH4J/AB8A0\noH1sm1GhTt8HCmPzDyX6oi4Cbsv0Z6vHOnyY6E75r4iupf44lfUH5AKPAR8CrwJ5mf7M9VyfPyFq\nxHwHmBcOXp1Vn0nV5dFAafh+vx1egzO5f+rGNBERATJ4Y5qIiGQXBQQREQEUEEREJFBAEBERQAFB\nREQCBQQREQEUEKQBMLONaUizp5n9oIplefHHO6eDmY2KTac9P5FkKCBIQ5COm2X2AZIfqT31rs5g\n3iIJKSBIg2FmBWZWbGaPm9l7ZjY5tmyxmd1k0WBCr5lZfph/n5mdFluv7OFhvwP6hwFdLk4y/0ND\n/m+Y2XOx580Um9nvQr4LzezoML+VmT0WBkD5Wxig5FAz+x2wa8j7QaKA18zM7goDpTxvZi1TUmki\ntaCAIA1NH+BiosFCvmFm/cJ8B9a6+8HA7cCfYvMT+RXwkrsf4u41jiAXHkI2ATjN3Q8D7gVuiOXR\nzN0PBy4hGjAGosFJVrn7t4BriR4v4O5+FfBlyHsE0VgC+wK3u/tBwFqgPIiJ1JddMl0AkVqa4+7L\nAMxsLtHIUbPDsofD30eAW2tIJ9GALtXZH/gW0dgUEI36tyy2/G/h71uhTABHEQKTuy8ws3eqSf8j\ndy9b/mYsDZF6o4AgDc2W2PR2qt6Hy84MthHOhM0sB2hRh7wXuHu/KpaVlatymZINPJU/1661LJtI\nnemSkTQmZ8X+lp01LCa6VAPRcILNw/QGoE0t0v4A6GRmR0B0CcnMDqxhm5eBM8P6BwLfji3bGp5P\nL5I1FBCkIfAqpivb3czmARcBvwzzJgIDw+WlI4CyLqzzgO1mNreKRuX9zezTshdwMtHz5G8Kab0N\nHFlDef9CFEQWAL8FFgDrwrK7gHdijcqVP5ceQyz1To+/lkbBzD4CDvUsGl0rXKJq7u5bQq+nF4D9\nPBrbViTr6JRVGots/GWzGzAj9FAy4P8pGEg20xmCiIgAakMQEZFAAUFERAAFBBERCRQQREQEUEAQ\nEZFAAUFERAD4/xtu33vXpHWkAAAAAElFTkSuQmCC\n", | |
"text/plain": [ | |
"<matplotlib.figure.Figure at 0x9c86f90>" | |
] | |
}, | |
"metadata": {}, | |
"output_type": "display_data" | |
} | |
], | |
"source": [ | |
"# Plot merge sort\n", | |
"line1, = plt.plot([x[0] for x in worst_time_quick], [x[1] for x in worst_time_quick], 'ro', label='Worst Case')\n", | |
"line2, = plt.plot([x[0] for x in best_time_quick], [x[1] for x in best_time_quick], 'co', label='Best Case')\n", | |
"\n", | |
"plt.axis([0, 20000, 0, 0.1])\n", | |
"\n", | |
"plt.legend(handles=[line1, line2], loc=1)\n", | |
"plt.xlabel(\"Input Length\")\n", | |
"plt.ylabel(\"Sorting Time (s)\")\n", | |
"plt.title(\"Worst/Best Case Time Complexity for Quick Sort\")\n", | |
"plt.show()" | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 2", | |
"language": "python", | |
"name": "python2" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 2 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython2", | |
"version": "2.7.10" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 0 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment