cs110_pcw_6_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Verina Armanyous\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "499babfdbdc05aec285e42abdf82edd4",
     "grade": false,
     "grade_id": "cell-f534ec91df9dff5f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 6.2\n",
    "\n",
    "## Part A. Median-of-3 partitioning quicksort \n",
    "\n",
    "## Question 1.\n",
    "\n",
    "Read through the following Python code. What does each function (i.e., median, qsort, randomized_qsort, test_qsort) do? Comment in details each function. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.06071015499999988\n"
     ]
    }
   ],
   "source": [
    "import timeit #module to measure the time to excute certain code\n",
    "import random #module to use randomization\n",
    "\n",
    "eps = 1e-16  \n",
    "N = 10000\n",
    "locations = [0.0, 0.5, 1.0 - eps]\n",
    "\n",
    "\n",
    "def median(x1, x2, x3): #this function determines the median of three inputs \n",
    "    if (x1 < x2 < x3) or (x3 < x2 < x1): #if x2 is the middle value amongst the inputs \n",
    "        return x2 #then x2 is the median\n",
    "    elif (x1 < x3 < x2) or (x2 < x3 < x1): #if X3 is the middle value amongst the inputs\n",
    "        return x3 #then x3 is the median \n",
    "    else:\n",
    "        return x1 #otherwise X1 is the median\n",
    "\n",
    "def qsort(lst): #this function sorts lists\n",
    "    indices = [(0, len(lst))] #store the value of 0 & the size of the list as a tuple in a list\n",
    "    \n",
    "    while indices:\n",
    "        (frm, to) = indices.pop() #assign 0 to \"frm\" & len(lst) to \"to\"\n",
    "        if frm == to: \n",
    "            continue\n",
    "\n",
    "        # Find the partition:\n",
    "        N = to - frm\n",
    "        inds = [frm + int(N * n) for n in locations]\n",
    "        values = [lst[ind] for ind in inds]\n",
    "        partition = median(*values)\n",
    "\n",
    "        # Split into lists:\n",
    "        lower = [a for a in lst[frm:to] if a < partition] #put all elements that are less than the partition\n",
    "        # in\"lower\" list\n",
    "        upper = [a for a in lst[frm:to] if a > partition] #put all elements that are larger than the partition \n",
    "        #value in \"upper\" list\n",
    "        counts = sum([1 for a in lst[frm:to] if a == partition]) # if there is another element in the list that \n",
    "        #equal to the partition value(pivot), count 1 and sum all of them\n",
    "\n",
    "        ind1 = frm + len(lower) # assign the value of the index that separates between lower and partition\n",
    "        ind2 = ind1 + counts #assign the value of the index that separates between partition and upper\n",
    "\n",
    "        # Push back into correct place:\n",
    "        #put all elements in the correct position for a sorted list\n",
    "        lst[frm:ind1] = lower \n",
    "        lst[ind1:ind2] = [partition] * counts\n",
    "        lst[ind2:to] = upper\n",
    "\n",
    "        # Enqueue other locations\n",
    "        #update the value of indices\n",
    "        indices.append((frm, ind1)) \n",
    "        indices.append((ind2, to))\n",
    "    return lst\n",
    "\n",
    "\n",
    "def randomized_quicksort(): #this function randomly shuffles the list and then call the qsort function to sort\n",
    "    #the list\n",
    "    lst = [i for i in range(N)]\n",
    "    random.shuffle(lst)\n",
    "    return qsort(lst)\n",
    "\n",
    "\n",
    "def test_quicksort(): # test whether the randomized list is sorted by comparing it to the sorted list of N size\n",
    "    lst = randomized_quicksort()\n",
    "    assert (lst == [i for i in range(N)])\n",
    "# Is our algorithm correct\n",
    "test_quicksort()\n",
    "\n",
    "# How fast is our algorithm\n",
    "print(timeit.timeit(randomized_quicksort, number=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "61fb11bff1434e4b7276c7443b0267c6",
     "grade": false,
     "grade_id": "cell-a2b2429aa4e81403",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2.\n",
    "\n",
    "What are the main differences between the `randomized_quicksort` in the code and $RANDOMIZED-QUICKSORT$ in Cormen et al., besides that the partition of `randomized_quicksort` uses a median of 3 as a pivot?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "8915b75d94bc194ba0f4e52e475063b4",
     "grade": true,
     "grade_id": "cell-4a3cd727ccac7404",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "- RANDOMIZED_QUICKSORT in Cormen et al. picks a random element from the given array and swaps it with the last element in the array, then the partition is done in the usual way. Thus, the pivot is chosen randomly from the list whose index is now the last element in the list. \n",
    "- randomized_quicksort in the code shuffles the entire list before calling the qsort. Then the partition is done based on chosoing the pivot from the median of three values."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "5853f10cab01212736d0e92ce408fa97",
     "grade": false,
     "grade_id": "cell-49bff57d4018e133",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3.\n",
    "What is the time complexity of this `randomized_qsort`? Time the algorithm on lists of various lengths, each list being a list of the first $n$ consecutive positive integers. Produce a graph with list lengths on the x axis and running time on the y axis. As always, don’t forget to time the algorithm several times for each list’s length and then average the results. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "a321a7fcecb9c9cce252ea2c6030d4ce",
     "grade": true,
     "grade_id": "cell-e0e1dac71ac7feb6",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "#I defined the randomized_quicksort function again to take an input instead of the N list \n",
    "def randomized_quicksort(lst): \n",
    "    random.shuffle(lst)\n",
    "    return qsort(lst)\n",
    "\n",
    "def average_time(lst):# to calculate the average running time for each list\n",
    "    total=0 #intialize the variable \n",
    "    for i in range(100): #iterate 100 for each list\n",
    "        t1= time.time() # the starting time\n",
    "        randomized_quicksort(lst)\n",
    "        t2 = time.time() #the ending time\n",
    "        t3 = t2 - t1 #the execution time\n",
    "        total += t3 # increment total \n",
    "    return (total/100) #divide to get the average\n",
    "lst = [list(range(10)), list(range(30)), list(range(50)),list(range(70)), list(range(90))] \n",
    "n= [10,30,50,70,90] #the input size \n",
    "t = [average_time(lst[0]), average_time(lst[1]),average_time(lst[2]),average_time(lst[3]),average_time(lst[4])] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Text(0.5, 0, 'Input Size')"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZ4AAAEKCAYAAAAiizNaAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3XecFdX5x/HPw4IgSJEmAq6LslJEELiCJXaNYCNGjGiiYlDUQNAYYyTxlxhjCjHRmGBXLERYFDWuii0SSxCFpUp3QZCV3jtseX5/zJBc1y0X5N65u/t9v173tXPPnDnzzN3y7MycM8fcHRERkVSpFXUAIiJSsyjxiIhISinxiIhISinxiIhISinxiIhISinxiIhISinxiIhISinxiIhISinxiIhIStWOOoB01Lx5c8/Kyoo6DBGRKmXatGnr3L1FZfWUeMqQlZVFXl5e1GGIiFQpZrYskXq61CYiIimlxCMiIimlxCMiIimlxCMiIimlxCMiIimlxCMiIimlxCMiIimlxCMiIuwuKuaR9xczbdnGpO9LA0hFRGowd+eNOav4wxvzWb5hJzeefjQ9jzw0qftU4hERqaE+LdjMb1+bx5SlG+hwWEP+Mag338punvT9KvGIiNQwq7fs4k9vLuSlGQU0rX8Qv7ukC5fHjqB2RmruvijxiIjUEDv3FPP4h0t4+L3FFJc4g087iiFntqdRvTopjUOJR0SkmispcXJnrWDEmwtYuXkXfbu0YnjfTmQ2qx9JPEo8IiLV2LRlG/nta/OYuXwTXdo04q+XH0/vo5pFGpMSj4hINVSwcQcj3lzIq7NW0LJhXe7t35VLe7SlVi2LOjQlHhGR6mT77iIefm8xj3+4BIBhZ7XnhtOPpkHd9Plzn9QuDGbWx8wWmlm+md1Rxvq6ZjYuXP+JmWXFrRseli80s/P2oc2/m9m2RPYhIlJdlJQ4z+ct54w/v8fIf+fTp0srJt52Brd+u0NaJR1I4hmPmWUADwLnAgXAVDPLdfd5cdUGARvdvb2ZDQBGAJebWWdgAHAs0Br4l5kdE25TbptmFgOalAqlzH0k4ZBFRCLx8ZL1/Pa1ecxdsYXumU149Kqe9MhM7iDQbyKZabAXkO/uSwDMLAfoB8Qnnn7AXeHyeGCkmVlYnuPuu4HPzSw/bI/y2gwT3b3AlcAlle3D3f0AHquISMotW7+dP0xYwJtzV9G6cT0eGHA8F3drTfBnNH0lM/G0AZbHvS8AepdXx92LzGwz0Cws/7jUtm3C5fLaHArkuvvKUh96eftYt3+HJSISrS27Chk5MZ+nJy2ldobx03OP4frTjqJenYyoQ0tIMhNPWSm39FlGeXXKKy/rnpSbWWvgMuCM/YwDMxsMDAbIzMwsYxMRkWgVFZeQM3U597+ziA079tC/R1tuO68DhzWqF3Vo+ySZiacAOCLufVtgRTl1CsysNtAY2FDJtmWVdwfaA/nh2U59M8t39/YV7OMr3P0x4DGAWCymy3AiklY+WLSWe16fx6LV2+jVrinPXNiZLm0aRx3Wfklm4pkKZJtZO+BLgs4CV5aqkwtcA0wG+gMT3d3NLBcYY2b3EXQuyAamEJy9fK1Nd58LtNrbqJltC5NOuftIxgGLiBxo+Wu28fsJ85m4YA2ZTevzyA96cN6xrdL+Pk5FkpZ4wvspQ4G3gAxglLvPNbO7gTx3zwWeBEaHnQc2ECQSwnrPE3REKAKGuHsxQFltVhJKmfsQEUlnG7fv4YF3P+MfHy/j4DoZDO/bkYGnZFG3dtW4j1MR0z//XxeLxTwvLy/qMESkBiosLmH05GU88O5nbN1VyBW9MvnJucfQ/JC6UYdWKTOb5u6xyuql16giEZEayt15d/4afj9hPkvWbefU7Ob88oJOdGzVKOrQDjglHhGRiM1fuYV7Xp/HpPz1HNWiAaMGxjizQ8sqfR+nIko8IiIRWbdtN395exHjpn5Bw3p1+PVFnfnBiUdSJ0UTskVFiUdEJMV2FxXz1KSljJyYz67CYq4+KYtbzsmmSf2Dog4tJZR4RERSxN15Y84q/vDGfJZv2MnZHVvyiws6cXSLQ6IOLaWUeEREUuDTgs389rV5TFm6gQ6HNWT0oF6cmt0i6rAiocQjIpJEq7fs4k9vLuSlGQU0rX8Qv7ukC5fHjqB2Nb+PUxElHhGRJNi5p5jHP1zCw+8tprjEGXzaUQw5sz2N6tWJOrTIKfGIiBxAJSVO7qwVjHhzASs376Jvl1YM79uJzGb1ow4tbSjxiIgcINOWbeS3r81j5vJNdGnTiL9efjy9j2oWdVhpR4lHROQbKti4gxFvLuTVWSto2bAu9/bvyqU92lKrVvUcAPpNKfGIiOyn7buLePi9xTz+4RIAhp3VnhtOP5oGdfWntSL6dERE9lFJiTN+egH3vrWQtVt30+/41tzepyNtmhwcdWhVghKPiMg++HjJen772jzmrthC98wmPHpVT3pkHhp1WFWKEo+ISAKWrd/OHyYs4M25q2jduB4PDDiei7u1rrYP8kwmJR4RkQps2VXIyIn5PD1pKbUzjJ+eewzXn3YU9epU/QnZoqLEIyJShqLiEnKmLuf+dxaxYcce+vdoy23ndeCwRvWiDq3KU+IRESnlg0Vruef1eSxavY1e7ZryzIWd6dKmcdRhVRtJfViQmfUxs4Vmlm9md5Sxvq6ZjQvXf2JmWXHrhoflC83svMraNLMnzWyWmc02s/FmdkhYPtDM1prZzPB1XTKPWUSqrvw12/jh01O5etQUdhWW8MgPejBu8IlKOgdY0s54zCwDeBA4FygApppZrrvPi6s2CNjo7u3NbAAwArjczDoDA4BjgdbAv8zsmHCb8tr8ibtvCfd9HzAU+GO4zTh3H5qsYxWRqm3j9j088O5n/OPjZRxcJ4PhfTsy8JQs6tbWfZxkSOaltl5AvrsvATCzHKAfEJ94+gF3hcvjgZEWdBHpB+S4+27gczPLD9ujvDbjko4BBwOexGMTkWqgsLiE0ZOX8cC7n7F1VyFX9MrkJ+ceQ/ND6kYdWrWWzMTTBlge974A6F1eHXcvMrPNQLOw/ONS27YJl8tt08yeAs4nSG4/jat3qZmdBiwiODOKb2PvtoOBwQCZmZmJHaGIVEnuzsQFa/jd6/NZsm47p2Y355cXdKJjq0ZRh1YjJPMeT1md20ufhZRXZ1/LgwX3awkuzc0HLg+LXwWy3L0r8C/gmbKCdffH3D3m7rEWLWrm5EwiNcGCVVu46skpDHomDwxGDYzx7A97KemkUDLPeAqAI+LetwVWlFOnwMxqA42BDZVsW2Gb7l5sZuOAnwFPufv6uNWPE9xHEpEaZt223dz3ziJypnxBw3p1+PVFnfnBiUdSpwZPyBaVZCaeqUC2mbUDviToLHBlqTq5wDXAZKA/MNHd3cxygTFhJ4HWQDYwheCM52tthvd1jnb3/HD5ImABgJkd7u4rw/1dTHA2JCI1xO6iYp6atJQHJ+azs7CYq0/K4pZzsmlS/6CoQ6uxkpZ4wns2Q4G3gAxglLvPNbO7gTx3zwWeBEaHnQc2ECQSwnrPE9yrKQKGuHsxQDlt1gKeMbNGBMlpFnBTGMowM7s4bGcDMDBZxywi6eXNOav4/YT5fLFhB2d3bMkvLujE0S0OiTqsGs/c1fmrtFgs5nl5eVGHISL7aceeIn71ylzGTyugw2ENufPCTpyarXu3yWZm09w9Vlk9PblARKqVBau2MOS56SxZt51hZ7Vn2NnZ1NZ9nLSixCMi1YK7kzN1OXflzqXRwXX4x6DenNK+edRhSRmUeESkytu6q5BfvDyHV2et4NTs5tz3veNp0VCDQNOVEo+IVGmfFmxm6NjpFGzcyc/O68BNpx9NrVqaIyedKfGISJXk7jz90VJ+P2E+zQ+pS87gEzkhq2nUYUkClHhEpMrZtGMPt4+fzdvzVnN2x5b8+bJuHNpA43KqCiUeEalSpi3byLCxM1izdRd3XtCJQd9qp+mnqxglHhGpEkpKnMc+XMK9by2kdZN6vHDjyRx/RJOow5L9oMQjImlv/bbd3Pr8LN5ftJbzj2vFHy/tSqN6daIOS/aTEo+IpLWPl6zn5pwZbNxRyD3f6cL3e2fq0loVp8QjImmpuMQZOTGfB95dRFazBjw1sBedW2vqgupAiUdE0s6aLbu4OWcmk5es55LubbjnO11oUFd/rqoLfSdFJK28v2gtt46byY49xdzbvyv9e7bVpbVqRolHRNJCYXEJ972ziIffW0yHwxoy8sruZB/WMOqwJAmUeEQkcl9u2smwsTOYtmwjV/Q6gl9deCwHH5QRdViSJEo8IhKpd+at5rYXZlFUXMIDA46n3/Ftog5JkkyJR0QisaeohD++sYBRkz7n2NaNGHllD9o1bxB1WJICSZ0dycz6mNlCM8s3szvKWF/XzMaF6z8xs6y4dcPD8oVmdl5lbZrZk2Y2y8xmm9l4Mzuksn2ISDSWrd9O/0c+YtSkzxl4chYv/ehkJZ0aJGmJx8wygAeBvkBn4Aoz61yq2iBgo7u3B+4HRoTbdgYGAMcCfYCHzCyjkjZ/4u7d3L0r8AUwtKJ9iEg0Xpu9ggv/9h+WrtvOIz/oyV0XH0vd2rqfU5Mk84ynF5Dv7kvcfQ+QA/QrVacf8Ey4PB4424J+k/2AHHff7e6fA/lhe+W26e5bAMLtDwa8kn2ISArtKizmly9/ytAxM2h/2CG8PuxU+nRpFXVYEoFk3uNpAyyPe18A9C6vjrsXmdlmoFlY/nGpbffecSy3TTN7CjgfmAf8tJJ9rNvfAxORfZO/ZhtDx0xnwaqt3HD6Udz27Q7UyUjqlX5JY8n8zpd1VuEJ1tnX8mDB/VqgNTAfuHwf4sDMBptZnpnlrV27toxNRGR/vDS9gItH/oc1W3fz1LUnMLxvJyWdGi6Z3/0C4Ii4922BFeXVMbPaQGNgQwXbVtqmuxcD44BLK9kHpbZ7zN1j7h5r0aJFwgcpImXbsaeI216Yxa3Pz6JLm8ZMGHYqZ3ZoGXVYkgaSmXimAtlm1s7MDiLoLJBbqk4ucE243B+Y6O4elg8Ie6S1A7KBKeW1aYH28N97PBcBCyrZh4gkyYJVW7jo7//hxekFDDs7mzHX9aZV43pRhyVpImn3eML7KUOBt4AMYJS7zzWzu4E8d88FngRGm1k+wVnIgHDbuWb2PMG9miJgSHgmQzlt1gKeMbNGBJfWZgE3haGUuQ8ROfDcnZypy7krdy6NDq7Dc4N6c3L75lGHJWnG9M//18ViMc/Ly4s6DJEqZeuuQn7x8hxenbWCU7Obc9/3jqdFw7pRhyUpZGbT3D1WWT09uUBEvrFPCzYzdOx0Cjbu5PY+HbjxtKOpVUujFqRsSjwist/cnac/WsrvJ8yn+SF1GTf4RGJZTaMOS9JcQoknfGLAYfH13f2LZAUlIulv0449/Gz8bN6Zt5pzOrXk3v7dOLTBQVGHJVVApYnHzH4M/BpYDZSExQ50TWJcIpLGpi3byLCxM1izdRf/d2FnfnhKliZrk4QlcsZzM9DB3dcnOxgRSW8lJc6jHyzhz28vpHWTeoy/8WS6HdEk6rCkikkk8SwHNic7EBFJb+u27ebW52fxwaK1nH9cK/54aVca1asTdVhSBSWSeJYA75nZ68DuvYXufl/SohKRtDJ58XpuzpnBpp2F3POdLny/d6Yurcl+SyTxfBG+DgpfIlJDFJc4f5/4GX979zOymjfg6Wt70bl1o6jDkiqu0sTj7r8BMLMG7r49+SGJSDpYvWUXt+TMZPKS9Xy3ext++50uNKirERjyzSXSq+0kgsfOHAJkmlk34AZ3/1GygxORaLy/aC23jpvJjj3F/PmybvTv2TbqkKQaSeTfl78C5xE+4NPdZ5nZaUmNSkQiUVhcwn3vLOLh9xbT4bCGPPj97rRv2TDqsKSaSei82d2Xl7qRWJyccEQkKl9u2smwsTOYtmwjV/TK5NcXdaZeHU1JLQdeQt2pzexkwMOpCIYRTLQmItXEO/NWc9sLsygucf52RXcu7tY66pCkGksk8dwIPEAwhXQB8DYwJJlBiUhq7C4q5o9vLOCpSUvp0qYRI6/oQVbzBlGHJdVcIomnxN2/H18QTs6mJxmIVGHL1m9n6JgZfPrlZgaenMXw8ztSt7YurUnyJZJ4XjWzvu6+BcDMOgEvAF2SGpmIJM1rs1dwx4ufUsvg0at6ct6xraIOSWqQRBLP7wmSzwVAB+BZ4PsVbyIi6WhXYTF3vzaPMZ98QffMJvz9iu60PbR+1GFJDVOrsgru/jpwP8G9naeB77j7zEQaN7M+ZrbQzPLN7I4y1tc1s3Hh+k/MLCtu3fCwfKGZnVdZm2b2XFg+x8xGmVmdsPwMM9tsZjPD168SiV2kuslfs43vPDiJMZ98wQ2nH8XzN5ykpCORKPeMx8z+TjD9wV6NCJ7b9mMzw92HVdRwOIfPg8C5BJ0SpppZrrvPi6s2CNjo7u3NbAAwArjczDoDA4BjgdbAv8zsmHCb8tp8DvhBWGcMcB3wcPj+Q3e/sKJ4RaqzF6cVcOc/53DwQRk8de0JnNmhZdQhSQ1W0aW2vFLvp+1j272AfHdfAmBmOUA/ID7x9APuCpfHAyMtGDDUD8hx993A52aWH7ZHeW26+4S9jZrZFEBDraXG2767iF+9MpcXpxfQu11THhjQnVaN60UdltRw5SYed3/mG7bdhmBKhb0KgN7l1XH3IjPbDDQLyz8utW2bcLnCNsNLbFcRzCO010lmNgtYAdzm7nP354BEqpL5K7cwdMx0lqzbzs1nZzPs7GwyaumJ0hK9RJ7Vlg38AegM/PdfJXc/qrJNyyjzBOuUV17WPanSbT4EfODuH4bvpwNHuvs2Mzsf+CeQ/bVgzQYDgwEyMzPL2I1I1eDujJ2ynN+8OpdGB9fhuUG9Obl986jDEvmvSjsXAE8R3CspAs4k6NU2OoHtCoAj4t63JTjjKLOOmdUGGgMbKti2wjbN7NdAC+DWvWXuvsXdt4XLE4A6Zva130J3f8zdY+4ea9GiRQKHJ5J+tu4q5MdjZ/CLlz+lV7umvHHzqUo6knYSSTwHu/u7gLn7Mne/Czgrge2mAtlm1i581M4AwgeNxskFrgmX+wMT3d3D8gFhr7d2BGcoUypq08yuI3iY6RXuXrJ3B2bWKrxvhJn1Co9Zg1+l2vm0YDMX/v0/vDFnFbf36cAz1/ai+SF1ow5L5GsSGcezy8xqAZ+Z2VDgS6DSLjHhPZuhwFtABjDK3eea2d1AnrvnEky3MDrsPLCBIJEQ1nueoCNCETDE3YsBymoz3OUjwDJgcphnXnL3uwkS2k1mVgTsBAaEyU2kWnB3nv5oKb+fMJ8Wh9Rl3OATiWU1jToskXJZZX+DzewEgoeCNgF+S9Ct+k/u/knyw4tGLBbzvLzSnfpE0s+mHXv42fjZvDNvNed0asm9/btxaANNFCzRMLNp7h6rrF4iZzxZ7j4V2AZcGzZ+GVBtE49IVTBt2UaGjZ3Bmq27+L8LO/PDU7IoNX2JSFpK5B7P8ATLRCQFSkqch99bzPcenUxGLePFm05m0LfaKelIlVHRkwv6AucDbczsb3GrGhHcdxGRFFu3bTe3Pj+LDxat5YLjDucPlx5Ho3p1og5LZJ9UdKltBcHTCy7mq08t2Ar8JJlBichX7dhTRM6U5Tz03mK27Crkd5d04cpemTrLkSqpoicXzAJmmdkYdy9MYUwiEtq0Yw/PfLSMpz/6nI07CunVril3XXQsnVs3ijo0kf1WaecCJR2R1Fu1eRdPfLiEMVO+YMeeYs7p1JKbzjiankeqm7RUfYn0ahORFFmydhuPvr+El2YUUOJwcbfW3Hj60XRo1TDq0EQOmIQTj5k1cPftyQxGpKb6tGAzD7+fzxtzVnFQRi2u6JXJ9acexRFNNV+OVD+JPCT0ZOAJ4BAg08y6ATe4+4+SHZxIdebuTF68noffX8yHn62jYb3a/OiMo7n2lHZ61I1Ua4mc8dxP8Ay0XAg6HZjZaUmNSqQaKylx3p63moffX8ys5Zto0bAud/TtyPd7Z9JQXaOlBkjoUpu7Ly/VbbM4OeGIVF97ikp4ZeaXPPL+Yhav3U5m0/r87pIuXNqjLfXqZEQdnkjKJJJ4loeX2zx8IvQwgme3iUgC9o7BeeLDJazYvItOhzfib1d05/wuraidkcjDQ0Sql0QSz43AAwQzgBYAbwNDkhmUSHVQ1hic3333OM44poUGfkqNlsg4nnXA91MQi0i1oDE4IhVLpFdbO+DHQFZ8fXe/OHlhiVQ9ZY3BueH0o+jYSk8ZEImXyKW2fxJM2PYqUFJJXZEaR2NwRPZNQjOQuvvfKq8mUnNoDI7I/ksk8TxgZr8m6FSwe2+hu09PWlQiaUpjcES+uUQSz3HAVcBZ/O9Sm4fvK2RmfQh6xGUAT7j7H0utrws8C/QE1gOXu/vScN1wYBDBmKFh7v5WRW2a2XNADCgEphA8XaHQgu5DDxDMLbQDGKikKftKY3BEDpxEEs8lwFHuvmdfGjazDOBB4FyCbthTzSzX3efFVRsEbHT39mY2ABgBXG5mnYEBwLFAa+BfZnZMuE15bT4H/CCsMwa4DngY6Atkh6/eYVnvfTkWqbk0BkfkwEsk8cwCmgBr9rHtXkC+uy8BMLMcoB8Qn3j6AXeFy+OBkeEZSj8gx913A5+bWX7YHuW16e4T9jZqZlOAtnH7eNbdHfjYzJqY2eHuvnIfj0dqEI3BEUmeRBLPYcACM5vKV+/xVNadug2wPO59AV8/0/hvHXcvMrPNQLOw/ONS27YJlyts08zqEFwavLmCONoASjzyNRqDI5J8iSSeX+9n22X9W+gJ1imvvKxrG6XbfAj4wN0/3Ic4MLPBwGCAzMzMMjaR6kxjcERSJ5EnF7y/n20XAEfEvW8LrCinToGZ1QYaAxsq2bbcNsPedy2AG/YxDtz9MeAxgFgs9rXEJNWTxuCIpF65icfM/uPu3zKzrXz1DMEAd/fK/hWcCmSHTz74kqCzwJWl6uQC1wCTgf7ARHd3M8sFxpjZfQSdC7IJeqpZeW2a2XUE0zec7e4lpfYxNLwf1BvYrPs7NZu7M3nJeh5+T2NwRKJQ0RlPAwB33685d8N7NkOBtwi6Po9y97lmdjeQ5+65BE9EGB12HthAkEgI6z1P0BGhCBji7sUAZbUZ7vIRYBkwObz5+5K73w1MIOhKnU/Qnfra/TkeqfpKSpx35q/mofc0BkckShZ09ipjhdl0d++R4njSQiwW87y8vKjDkAOksLiEV2au4JH3F5O/ZhuZTetzw+lHaQyOyAFmZtPcPVZZvYrOeFqa2a3lrXT3+/YrMpEU2bGniHFTl/P4BxqDI5JOKko8GcAhlN0rTCRtbdqxh2cnL+OpSRqDI5KOKko8K8N7JCJVwqrNu3jyP0sY88kXbN9TzNkdW/KjMzUGRyTdVJR49K+hVAmlx+Bc1PVwbjzjaI3BEUlTFSWes1MWhch+0Bgckaqp3MTj7htSGYhIIsobgzPw5Ha0aKgxOCJVQSKPzBGJXOkxOM0PCcbgXNk7k0YagyNSpSjxSForawyO5sERqdqUeCQtaQyOSPWlxCNp5WtjcLI0BkekulHikbRQ1hicm844mliWxuCIVDdKPBIpjcERqXmUeCQS7s5jHyxhxJsLqKMxOCI1ihKPpNyuwmKGv/QpL8/4kguOO5y7Lj5WY3BEahAlHkmpVZt3ccPoPGYVbOa2bx/DkDPbq9OASA2jxCMpM+OLjdwwehrbdxfx2FU9+faxraIOSUQioMQjKfHitAKGv/wprRrVY/Sg3nRotV8T24pINZDUkXhm1sfMFppZvpndUcb6umY2Llz/iZllxa0bHpYvNLPzKmvTzIaGZW5mzePKzzCzzWY2M3z9KnlHLKUVFZdwz2vz+OkLs4gdeSivDDlFSUekhkvaGY+ZZQAPAucCBcBUM8t193lx1QYBG929vZkNAEYAl5tZZ2AAcCzQGviXmR0TblNem5OA14D3ygjnQ3e/8IAfpFRo845Cfpwzgw8WrWXgyVn88oJO1NFTB0RqvGReausF5Lv7EgAzywH6AfGJpx9wV7g8HhhpwZ3mfkCOu+8GPjez/LA9ymvT3WeEZUk8JElU/pptXP9sHgUbd/DH7x7HgF6ZUYckImkimf9+tgGWx70vCMvKrOPuRcBmoFkF2ybSZllOMrNZZvaGmR27Lwch++7fC9ZwyYOT2LqrkDHXn6ikIyJfkcwznrJOPTzBOuWVl5UoS7dZ2nTgSHffZmbnA/8EsktXMrPBwGCAzEz9odwf7s4j7y/hT28toPPhjXjs6hhtmhwcdVgikmaSecZTABwR974tsKK8OmZWG2gMbKhg20Ta/Ap33+Lu28LlCUCd+M4HcfUec/eYu8datGhR+dHJV+wqLOaWcTMZ8eYCzj/ucMbfeLKSjoiUKZmJZyqQbWbtzOwggs4CuaXq5ALXhMv9gYnu7mH5gLDXWzuCM5QpCbb5FWbWKrxvhJn1Ijjm9QfkCAWAlZt38r1HJ/PKzBX87LwOjLyiOwcfpLlyRKRsSbvU5u5FZjYUeAvIAEa5+1wzuxvIc/dc4ElgdNh5YANBIiGs9zxBR4QiYIi7F0PQbbp0m2H5MOB2oBUw28wmuPt1BAntJjMrAnYCA8LkJgfA9HBQ6I7dRTx+dYxzOx8WdUgikuZMf4O/LhaLeV5eXtRhpL0X8pbzy5fn0KpxPZ64JsYxh2l8jkhNZmbT3D1WWT09uUD2WVFxCX94YwFP/udzTj66GQ9e2YNDGxwUdVgiUkUo8cg+2byjkKFjp/PhZ+sYeHIWd17QSVNRi8g+UeKRhOWv2cp1z+Tx5aadjLj0OC4/Qd3ORWTfKfFIQiYuWM2wsTOpV6cWY68/UVNSi8h+U+KRCmlQqIgcaEo8Uq5dhcX8/MXZvDJzBRd2PZx7+3fT+BwR+caUeKRMKzfvZPCz05izYjM/O68DPzrjaD2AVUQOCCUe+Zppy4JBobsKi3n8qhjnaFCoiBxASjzyFc/nLefOl+dweJN6jL2+N9kaFCoiB5gSjwDBoNDfT1jAqEmf8632zRl5ZXea1NegUBE58JR4hE1dP+DLAAAOoklEQVQ79vDjsTP48LN1XHtKFr88X4NCRSR5lHhquPhBoX+6tCvfO+GIyjcSEfkGlHhqsHfnr+bmnJnUq5NBzuAT6XmkBoWKSPIp8dRA7s7D7y/m3rcW0qV1Yx69qietNShURFJEiaeG2bknGBSaO2sFF3VrzZ8u7apBoSKSUko8NUj8oNDb+3TgptM1KFREUk+Jp4aYtmwDN4yezq7CYp64OsbZnTQoVESiocRTAzw/dTl3/nMOrTUoVETSQFIHa5hZHzNbaGb5ZnZHGevrmtm4cP0nZpYVt254WL7QzM6rrE0zGxqWuZk1jys3M/tbuG62mfVI3hGnl6LiEn7z6lxuf3E2vdo15Z9DTlHSEZHIJS3xmFkG8CDQF+gMXGFmnUtVGwRsdPf2wP3AiHDbzsAA4FigD/CQmWVU0uYk4BxgWal99AWyw9dg4OEDeZzpatOOPQx8aipPTVrKD09px9PXnqAnEYhIWkjmpbZeQL67LwEwsxygHzAvrk4/4K5weTww0oK73f2AHHffDXxuZvlhe5TXprvPCMtKx9EPeNbdHfjYzJqY2eHuvvKAHm0a+Wz1Vq57No+Vm3bxp/5d+V5Mg0JFJH0k81JbG2B53PuCsKzMOu5eBGwGmlWwbSJt7k8cmNlgM8szs7y1a9dW0mT6+te81Vzy0Eds313M2MEnKumISNpJZuIpq5+uJ1hnX8u/aRy4+2PuHnP3WIsWLSppMv24Ow/+O5/rR+fRrnkDXv3xKfQ88tCowxIR+ZpkXmorAOL/3W4LrCinToGZ1QYaAxsq2bayNvcnjipt555ibn9xNq/OWsHF3Vrzp/5dqVdHg0JFJD0l84xnKpBtZu3M7CCCzgK5perkAteEy/2BieG9mFxgQNjrrR1Bx4ApCbZZWi5wddi77URgc3W6v7Ni004ue/QjXpu9gp/36cgDA45X0hGRtJa0Mx53LzKzocBbQAYwyt3nmtndQJ675wJPAqPDzgMbCBIJYb3nCToiFAFD3L0Ygm7TpdsMy4cBtwOtgNlmNsHdrwMmAOcD+cAO4NpkHXOqaVCoiFRFFpxgSLxYLOZ5eXlRh1GhcVO/4M5/zqFNk4N54poY7VtqfI6IRMvMprl7rLJ6enJBFVNUXMI9r8/n6Y+Wcmp2c0Ze0YPG9etEHZaISMKUeKqQjdv3MHTsdCblr2fQt9oxvG9HzRQqIlWOEk8VsWh1MFPoqs27uLd/Vy7T+BwRqaKUeKqAd+at5pacGdSvW5uxg0/U+BwRqdKUeNLY3kGhf3lnEV1aN+axq3tyeGPNFCoiVZsST5rauaeYn42fxWuzV9Lv+NaMuFSDQkWkelDiSUNfbtrJ4GfzmLdyC3f07cgNpx2lmUJFpNpQ4kkzU5du4KZ/TGN3YQlPXhPjrI4aFCoi1YsSTxrJmfIF//fKHNoeWp+cwTHatzwk6pBERA44JZ40UFhcwu/CQaGnHdOCvw/orkGhIlJtKfFEbOP2PQwZM52PFq/n+lPb8fM+GhQqItWbEk+EFq7ayvXPBoNC/3JZNy7t2TbqkEREkk6JJyJvz13FT8bNpH7d2uTccCI9MjUoVERqBiWeFNs7KPTPby+iW9vGPHpVjFaN60UdlohIyijxpNCOPUX8bPxsXp+9kku6t+EP3z1Og0JFpMZR4kmRLzft5Ppn8pi/agvD+3ZksAaFikgNpcSTAlOXbuDG0dPYU1TCqGtO4MyOLaMOSUQkMkntt2tmfcxsoZnlm9kdZayva2bjwvWfmFlW3LrhYflCMzuvsjbNrF3YxmdhmweF5QPNbK2ZzQxf1yXzmEsbO+ULrnz8YxofXIeXh5yipCMiNV7SEo+ZZQAPAn2BzsAVZta5VLVBwEZ3bw/cD4wIt+0MDACOBfoAD5lZRiVtjgDud/dsYGPY9l7j3P348PVEEg73awqLS/j1K3MY/tKnnHR0c14ecoqeRCAiQnLPeHoB+e6+xN33ADlAv1J1+gHPhMvjgbMtuPHRD8hx993u/jmQH7ZXZpvhNmeFbRC2+Z0kHluFNm7fw9VPTuGZycu4/tR2PDXwBBofrCcRiIhAchNPG2B53PuCsKzMOu5eBGwGmlWwbXnlzYBNYRtl7etSM5ttZuPNLKlTdy5ctZWLH/wP077YyF8u68YvL+hMRi11IhAR2SuZiaesv7aeYJ0DVQ7wKpDl7l2Bf/G/M6yvBmI22MzyzCxv7dq1ZVWp1AeL1vLdhyaxu7CEcYNP1JMIRETKkMzEUwDEn120BVaUV8fMagONgQ0VbFte+TqgSdjGV/bl7uvdfXdY/jjQs6xg3f0xd4+5e6xFixb7cJj/c0TT+vTMasqrP/4W3fUkAhGRMiUz8UwFssPeZgcRdBbILVUnF7gmXO4PTHR3D8sHhL3e2gHZwJTy2gy3+XfYBmGbrwCY2eFx+7sYmH+Aj/O/2jVvwLM/7MVhjfQkAhGR8iRtHI+7F5nZUOAtIAMY5e5zzexuIM/dc4EngdFmlk9wpjMg3HaumT0PzAOKgCHuXgxQVpvhLn8O5JjZPcCMsG2AYWZ2cdjOBmBgso5ZREQqZ8HJgsSLxWKel5cXdRgiIlWKmU1z91hl9TTxi4iIpJQSj4iIpJQSj4iIpJQSj4iIpJQSj4iIpJQSj4iIpJS6U5fBzNYCy/Zz8+YET1JIN+kaF6RvbIpr3yiufVMd4zrS3St99IsSzwFmZnmJ9GNPtXSNC9I3NsW1bxTXvqnJcelSm4iIpJQSj4iIpJQSz4H3WNQBlCNd44L0jU1x7RvFtW9qbFy6xyMiIimlMx4REUkpJZ5vwMxGmdkaM5sTV9bUzN4xs8/CrymfEc7MjjCzf5vZfDOba2Y3p0NsZlbPzKaY2awwrt+E5e3M7JMwrnHhXEspZ2YZZjbDzF5Ll7jMbKmZfWpmM80sLyxLh5+xJuFU8gvCn7OToo7LzDqEn9Pe1xYzuyXquMLYfhL+zM8xs7Hh70I6/HzdHMY018xuCcuS/nkp8XwzTwN9SpXdAbzr7tnAu+H7VCsCfurunYATgSFm1jkNYtsNnOXu3YDjgT5mdiIwArg/jGsjMCjFce11M1+dKDBd4jrT3Y+P6+Ia9fcR4AHgTXfvCHQj+NwijcvdF4af0/EEMw3vAF6OOi4zawMMA2Lu3oVgLrEBRPzzZWZdgOuBXgTfwwvNLJtUfF7urtc3eAFZwJy49wuBw8Plw4GFaRDjK8C56RQbUB+YDvQmGKxWOyw/CXgrgnjahr9kZwGvAZYmcS0Fmpcqi/T7CDQCPie8R5wucZWK5dvApHSIC2gDLAeaEky++RpwXtQ/X8BlwBNx7/8PuD0Vn5fOeA68w9x9JUD4tWWUwZhZFtAd+IQ0iC28nDUTWAO8AywGNrl7UVilgOAXNdX+SvBLVxK+b5YmcTnwtplNM7PBYVnU38ejgLXAU+GlySfMrEEaxBVvADA2XI40Lnf/Evgz8AWwEtgMTCP6n685wGlm1szM6gPnA0eQgs9LiacaM7NDgBeBW9x9S9TxALh7sQeXQtoSnOJ3KqtaKmMyswuBNe4+Lb64jKpRdAE9xd17AH0JLpmeFkEMpdUGegAPu3t3YDvRXO4rU3iv5GLghahjAQjvkfQD2gGtgQYE38/SUvrz5e7zCS73vQO8CcwiuEyfdEo8B95qMzscIPy6JoogzKwOQdJ5zt1fSqfYANx9E/AewT2oJmZWO1zVFliR4nBOAS42s6VADsHltr+mQVy4+4rw6xqC+xW9iP77WAAUuPsn4fvxBIko6rj26gtMd/fV4fuo4zoH+Nzd17p7IfAScDLp8fP1pLv3cPfTgA3AZ6Tg81LiOfBygWvC5WsI7q+klJkZ8CQw393vS5fYzKyFmTUJlw8m+IWcD/wb6B9VXO4+3N3bunsWwSWaie7+/ajjMrMGZtZw7zLBfYs5RPx9dPdVwHIz6xAWnQ3MizquOFfwv8tsEH1cXwAnmln98Hdz7+cV6c8XgJm1DL9mAt8l+NyS/3ml8mZWdXuF36SVQCHBf4GDCO4NvEvwn8O7QNMI4voWwWn7bGBm+Do/6tiArsCMMK45wK/C8qOAKUA+weWRuhF+T88AXkuHuML9zwpfc4FfhuXp8DN2PJAXfi//CRyaJnHVB9YDjePK0iGu3wALwp/70UDdqH++wrg+JEiCs4CzU/V56ckFIiKSUrrUJiIiKaXEIyIiKaXEIyIiKaXEIyIiKaXEIyIiKaXEI3KAmdm2JLSZZWZXlrOulpn9LXzK8KdmNtXM2oXrJuwdOyWSLmpXXkVE0kAWcCUwpox1lxM8iqWru5eYWVuCx9jg7uenLEKRBOmMRyRJzOwMM3svbt6a58KR63vn2RlhwfxEU8ysfVj+tJn1j2tj79nTH4FTw3lmflJqV4cDK929BMDdC9x9Y9x+mpvZjXHz1HxuZv8O13/bzCab2XQzeyF8vp9IUinxiCRXd+AWoDPBSPVT4tZtcfdewEiCZ8NV5A7gQw/mm7m/1LrngYvCpPIXM+teemN3f8SDh7OeQPCUjfvMrDlwJ3COBw8izQNu3fdDFNk3SjwiyTUlPAMpIXh0UVbcurFxX0/a3x24ewHQARhOMK3Du2Z2djnVHyB4Ft2rBA9o7QxMCqequAY4cn/jEEmU7vGIJNfuuOVivvo752UsFxH+QxhelktoOmR33w28AbxhZquB7xA8Z+u/zGwgQWIZurcIeMfdr0hkHyIHis54RKJzedzXyeHyUoJpmyGYw6VOuLwVaFhWI2bWw8xah8u1CB7GuqxUnZ7AbcAP9t4LAj4GTom7v1TfzI75hsckUimd8YhEp66ZfULwD+Des47HgVfMbArBGcv2sHw2UGRms4CnS93naQk8bmZ1w/dTCO4bxRtKMPXyv8P+DXnufl14FjQ2bts7gUUH6gBFyqKnU4tEIJx0Lubu66KORSTVdKlNRERSSmc8IiKSUjrjERGRlFLiERGRlFLiERGRlFLiERGRlFLiERGRlFLiERGRlPp/hUaPJXIfrvwAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "#plot the input size and the execution time for each list \n",
    "plt.plot(n, t)\n",
    "plt.ylabel('Time taken')\n",
    "plt.xlabel('Input Size')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b8751f930d9dc208113425646ea7fea8",
     "grade": false,
     "grade_id": "cell-1e8309c07c2f2908",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4.\n",
    "\n",
    "### Question 4a.\n",
    "\n",
    "Change the `qsort()` function in a way that you **don’t** separate the items that are equal to the partition. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "797888f53fa36bcf0f9d891c4819d8e9",
     "grade": false,
     "grade_id": "cell-a9d1f063c0340b14",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def qsort(lst): #this function sorts lists\n",
    "    indices = [(0, len(lst))] #store the value of 0 & the size of the list as a tuple in a list\n",
    "    \n",
    "    while indices:\n",
    "        (frm, to) = indices.pop() #assign 0 to \"frm\" & len(lst) to \"to\"\n",
    "        if frm == to: \n",
    "            continue\n",
    "\n",
    "        # Find the partition:\n",
    "        N = to - frm\n",
    "        inds = [frm + int(N * n) for n in locations]\n",
    "        values = [lst[ind] for ind in inds]\n",
    "        partition = median(*values)\n",
    "\n",
    "        # Split into lists:\n",
    "        lower = [a for a in lst[frm:to] if a <= partition] #put all elements that are less than the partition\n",
    "        # in\"lower\" list\n",
    "        upper = [a for a in lst[frm:to] if a > partition] #put all elements that are larger than the partition \n",
    "        #value in \"upper\" list\n",
    "        counts = sum([1 for a in lst[frm:to] if a == partition]) # if there is another element in the list that \n",
    "        #equal to the partition value(pivot), count 1 and sum all of them\n",
    "\n",
    "        ind1 = frm + len(lower) # assign the value of the index that separates between lower and partition\n",
    "        ind2 = ind1 + counts #assign the value of the index that separates between partition and upper\n",
    "\n",
    "        # Push back into correct place:\n",
    "        #put all elements in the correct position for a sorted list\n",
    "        lst[frm:ind1] = lower \n",
    "        lst[ind2:to] = upper\n",
    "\n",
    "        # Enqueue other locations\n",
    "        #update the value of indices\n",
    "        indices.append((frm, ind1)) \n",
    "        indices.append((ind2, to))\n",
    "    return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ce755b787f1b82629d627d2f8bea66a5",
     "grade": true,
     "grade_id": "cell-2c0cbd296d612f85",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert(qsort([4,2,1])==[1,2,4])\n",
    "assert(qsort([0])==[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At the beginning, I wasn't sure about the meaning of the questions, but then I tried a couple of times to remove the list where there are the duplicates of the pivot and it lead to infinite loop. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "3f5f9ca976fb636978e2bdfda98a5eeb",
     "grade": false,
     "grade_id": "cell-76883a453f020d72",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 4b.\n",
    "\n",
    "Now time the algorithm on the same inputs you have used in question 3, adding one more line in the previous graph you have produced. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "33188fb282e53d117dfe275067ad3567",
     "grade": true,
     "grade_id": "cell-31ee807cec9ce8bf",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "#I defined the randomized_quicksort function again to take an input instead of the N list \n",
    "def randomized_quicksort(lst): \n",
    "    random.shuffle(lst)\n",
    "    return qsort(lst)\n",
    "\n",
    "def average_time(lst):# to calculate the average running time for each list\n",
    "    total=0 #intialize the variable \n",
    "    for i in range(100): #iterate 100 for each list\n",
    "        t1= time.time() # the starting time\n",
    "        randomized_quicksort(lst)\n",
    "        t2 = time.time() #the ending time\n",
    "        t3 = t2 - t1 #the execution time\n",
    "        total += t3 # increment total \n",
    "    return (total/100) #divide to get the average\n",
    "lst = [list(range(10)), list(range(30)), list(range(50)),list(range(70)), list(range(90))] \n",
    "n= [10,30,50,70,90] #the input size \n",
    "t = [average_time(lst[0]), average_time(lst[1]),average_time(lst[2]),average_time(lst[3]),average_time(lst[4])] \n",
    "t_n= [qsort(lst[0]),qsort(lst[1]),qsort(lst[2]),qsort(lst[3]),qsort(lst[4])]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The graph didn't work since the new qsort didn't work either."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "991ee87c525d8fa29bd448aa80dbf243",
     "grade": false,
     "grade_id": "cell-b666e68e84dfce03",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 5.\n",
    "\n",
    "### Question 5a.\n",
    "\n",
    "Remove the median-of-3 partitioning, and just use the first element in the array. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "90dbb100f881a2c9a61720a0753ca401",
     "grade": false,
     "grade_id": "cell-4daf36021c15eaf0",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def qsort(lst): #this function sorts lists\n",
    "    indices = [(0, len(lst))] #store the value of the tuple inside the list indices \n",
    "    \n",
    "    while indices:\n",
    "        (frm, to) = indices.pop()\n",
    "        if frm == to:\n",
    "            continue\n",
    "\n",
    "        # Find the partition:\n",
    "        N = to - frm\n",
    "        inds = [frm + int(N * n) for n in locations]\n",
    "        values = [lst[ind] for ind in inds]\n",
    "        partition = lst[0] # the pivot is the first element in the array \n",
    "\n",
    "        # Split into lists:\n",
    "        lower = [a for a in lst[frm:to] if a < partition]\n",
    "        upper = [a for a in lst[frm:to] if a > partition]\n",
    "        counts = sum([1 for a in lst[frm:to] if a == partition])\n",
    "\n",
    "        ind1 = frm + len(lower)\n",
    "        ind2 = ind1 + counts\n",
    "\n",
    "        # Push back into correct place:\n",
    "        lst[frm:ind1] = lower\n",
    "        lst[ind1:ind2] = [partition] * counts\n",
    "        lst[ind2:to] = upper\n",
    "\n",
    "        # Enqueue other locations\n",
    "        indices.append((frm, ind1))\n",
    "        indices.append((ind2, to))\n",
    "    return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9d457eff304d19e031a8eabb4615ca3b",
     "grade": true,
     "grade_id": "cell-97473a9e0d12e745",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert(qsort([4,2,1])==[1,2,4])\n",
    "assert(qsort([0])==[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8f0166e7d0021886bb7176f35011a633",
     "grade": false,
     "grade_id": "cell-2ca71dd53b31262b",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 5b.\n",
    "\n",
    "Does this change the running time of your algorithm? Justify your response with a graph. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "bd863db414089f9ead9906b3c2c34a15",
     "grade": true,
     "grade_id": "cell-1f3a6df29d324853",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "def average_time(lst):# to calculate the running time for each list\n",
    "    total=0\n",
    "    for i in range(10):\n",
    "        t1= time.time()\n",
    "        qsort(lst)\n",
    "        t2 = time.time()\n",
    "        t3 = t2 - t1\n",
    "        total += t3        \n",
    "    return (total/10)\n",
    "lst = [[5,4,3,2,1], [10,9,8,7,6,5,4,3,2,1],[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1],[20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1],[25,24,23,22,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]]\n",
    "n= [5,10,15,20,25]\n",
    "t = [average_time(lst[0]), average_time(lst[1]),average_time(lst[2]),average_time(lst[3]),average_time(lst[4])]\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "plt.plot(n, t)\n",
    "plt.ylabel('Time taken')\n",
    "plt.xlabel('Input Size')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "51af6d987694ab6231a6f4aa19f39164",
     "grade": false,
     "grade_id": "cell-67512d1d42af415f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Part B. Recursive quicksort. \n",
    "\n",
    "One main difference between the quicksort algorithms in Cormen et al. and the implementation in the code above is that quick sort (in the code in this notebook) is not recursive, while $QUICKSORT$ in Cormen et al. is. Given the limitation of Python so that it can only make 500 recursive calls, estimate the maximum size of the list that can be sorted by Python if a recursive quicksort is to be used. Explicitly state all assumptions you make in getting to an answer.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "7be7bc411376ac8090621f3d68630c10",
     "grade": true,
     "grade_id": "cell-4af5aab4ad1a7225",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "- Assume that we follow the quicksort code in Corment et al. where we take the last element as a pivot and then recursively call the function on the two sublists surrounding the pivot.\n",
    "-  I think it depends on the distribution of the list. For instance, I used quicksort to sort randomized list of 7 elements and it did 10 recursive call. However, when I tried ordered and reverse ordered lists of 7 elements, there were 12 recursive call. So, I think it varies based on the distribution of the list and based on the pivot choice.\n",
    "- Based on the experimentation I did with quicksort code on various lists, if we have a list of random elements ( not in ascending or descending order, not identical elements) I think the maximum size of the list might lie between 300 - 450."
   ]
  }
 ],
 "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}