cs110_pcw_2_1.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": "4394bdd5d17d8ce7ce4e758066ee0266",
     "grade": false,
     "grade_id": "cell-9e44910e5a73668d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 2.1\n",
    "\n",
    "## Question 1.\n",
    "\n",
    "First, please read carefully [this note](https://drive.google.com/open?id=1SfrRTKWDb6szsJENgvNF7-u2B96ecaF2) which reviews the MERGE operation in Cormen et al.\n",
    "\n",
    "After reviewing the example above (Cormen et. al., Figure 2.3),  you need to manually create similar illustrations as in the example above but this time for the input array:\n",
    "\n",
    "![array](array.png)\n",
    "\n",
    "For this exercise, assume that the call to the algorithm is MERGE(A, 1, 3, 6) and draw different resulting stages of the arrays A, L, and R as the merge algorithm is executed.  You can hand-draw or use any drawing tool to produce panel illustrations as in the example above.  Include your final drawings in the cell below. Feel free to use additional cells (Markdown or Code) for this question.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "b4d0caf51fb6b587f68db4e806af35d0",
     "grade": true,
     "grade_id": "cell-badbff7790708987",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "\n",
    "![part1](part1.png)\n",
    "![part2](part2.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "7c9608898d23ecbe07c084ca6d6da655",
     "grade": false,
     "grade_id": "cell-6dd1317d1ea8ab9f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2.\n",
    "Now using your understanding of Part I of the merge algorithm, can you think of an efficient way to implement this part in Python? (hint: using Python list). Give your answer in prose in the cell below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9bf35550640c33f366c5cffad7fdf33a",
     "grade": true,
     "grade_id": "cell-4f961721620a6645",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "Use list comprehension to copy the elements of the array into two sub arrays:\n",
    "\n",
    "-list comprehension improves the performance of the code and makes the execution time faster (compared to the appending method)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "010584ea3a4f00fba43b52bb04cd0ed2",
     "grade": false,
     "grade_id": "cell-84932c7c0c20b750",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3.\n",
    "\n",
    "Write a Python implementation of the merge pseudocode (both parts), your Python function must take the same four input arguments as described in the $MERGE(A,p,q,r)$. Test your code by running the example in problem 1 and 2 of this pre-class work. Feel free to come up with additional cases to check if your code is working properly. Your code should return A "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "43760e27d0b385c30476353b3d546a79",
     "grade": false,
     "grade_id": "cell-a67719d65c1ac9f3",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def merge(A, p, q, r):\n",
    "    n1= q-p+1 #computes the length of the first subarray\n",
    "    n2= r-q #computes the length of the second subarray\n",
    "   \n",
    "    L = [0] * n1 #create temporary array with certain size of n1\n",
    "    R = [0] *n2 #create temporary array with certain size of n2\n",
    "    \n",
    "    for i in range(0,n1): #copy data from main array to temporay array L \n",
    "        L[i]=A[p+i]\n",
    "    for j in range(0,n2):#copy data from main array to temporary array R\n",
    "        R[j]=A[q+j]\n",
    "    i=0 #intializing the variable to use it as a pointer for the index in L[]\n",
    "    j=0 #intializing the variable to use it as a pointer for the index R[]\n",
    "    \n",
    "    for k in A:\n",
    "        while i<n1 and j<n2: #make sure we reach only the last element in the arrays (sentinel card)\n",
    "            if L[i] <= R[j]: #comparing between two elements\n",
    "                A[k] = L[i] #copying the smaller element to the main array\n",
    "                i+=1 #increament the index by one\n",
    "            else:\n",
    "                A[k] = R[j]\n",
    "                j+=1 #increament the index of by one\n",
    "                 \n",
    "    return(A)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "699908274975a6bff4f9fb021e666ce4",
     "grade": true,
     "grade_id": "cell-e98759fe14428af0",
     "locked": true,
     "points": 0,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Please ignore this cell. This cell is for us to implement the tests \n",
    "# to see if your code works properly. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "35e241fec3dd026733d04a51fa2972fe",
     "grade": false,
     "grade_id": "cell-49f3f61ee6d72bb9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2\n",
    "Suppose that your Python implementation of the merge algorithm is already working. Inspect the code for merge sort below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "53611abb1448334a346783091382fb12",
     "grade": false,
     "grade_id": "cell-073a21c6aac8225e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def merge_sort(A,p,r):\n",
    "    if p < r:\n",
    "        q = (p+r)/2\n",
    "        merge_sort(A,p,q)\n",
    "        merge_sort(A,q+1,r)\n",
    "        merge(A,p,q,r)\n",
    "    return(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b708edb1e6e70731f3ec68d1d11c2890",
     "grade": false,
     "grade_id": "cell-c19a4320995e15b2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Copy and paste the code above to the cell below and fix the bug in it. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "d52aee435812fe91886c6dcdfc4e3f6d",
     "grade": false,
     "grade_id": "cell-311695db35c06d65",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def merge_sort(A,p,r):\n",
    "    if p < r:\n",
    "        q = (p+r)//2 #make sure the division results in an integer number (not float)\n",
    "        merge_sort(A,p,q)\n",
    "        merge_sort(A,q+1,r)\n",
    "        merge(A,p,q,r)\n",
    "    return(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "35fbb3c437b3ba39ede0d87d6719223b",
     "grade": true,
     "grade_id": "cell-a3a71f67390c1f82",
     "locked": true,
     "points": 0,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Please ignore this cell. This cell is for us to implement the tests \n",
    "# to see if your code works properly. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "61cfba995efe3c9c37092a650047fdf3",
     "grade": false,
     "grade_id": "cell-5b296f793fefdbfe",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Question 5.\n",
    "As in the previous Lesson, count the number of steps and time your merge_sort() function with the following input: `list_k = [i for i in range(100*k, 0, -1)] `, where $k= 1, 2, 3, …, 15 $. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "cc3f59157e795d05422e849f3e7cc03a",
     "grade": true,
     "grade_id": "cell-8a4233ab58d3d0bb",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "count_steps =0\n",
    "\n",
    "def merge(A, p, q, r):\n",
    "    n1= q-p+1 #computes the length of the first subarray\n",
    "    n2= r-q #computes the length of the second subarray\n",
    "   \n",
    "    L = [0] * n1 #create temporary array with certain size of n1\n",
    "    R = [0] *n2 #create temporary array with certain size of n2\n",
    "    \n",
    "    for i in range(0,n1): #copy data from main array to temporay array L \n",
    "        L[i]=A[p+i]\n",
    "    for j in range(0,n2):#copy data from main array to temporary array R\n",
    "        R[j]=A[q+j]\n",
    "    i=0 #intializing the variable to use it as a pointer for the index in L[]\n",
    "    j=0 #intializing the variable to use it as a pointer for the index R[]\n",
    "    \n",
    "    for k in A:\n",
    "        while i<n1 and j<n2: #make sure we reach only the last element in the arrays (sentinel card)\n",
    "            if L[i] <= R[j]: #comparing between two elements\n",
    "                A[k] = L[i] #copying the smaller element to the main array\n",
    "                i+=1 #increament the index by one\n",
    "                count_step+=1\n",
    "            else:\n",
    "                A[k] = R[j]\n",
    "                j+=1 #increament the index of by one\n",
    "                count_step+=1\n",
    "def merge_sort(A,p,r):\n",
    "    begin=time.time\n",
    "    if p < r:\n",
    "        count_step+=1\n",
    "        q = (p+r)//2 #make sure the division results in integer number (not float)\n",
    "        merge_sort(A,p,q)\n",
    "        merge_sort(A,q+1,r)\n",
    "        merge(A,p,q,r)\n",
    "    end=time.time\n",
    "    total_time= end - begin\n",
    "    count_step_merge\n",
    "    return(A)\n",
    "    return(count_Step_merge)\n",
    "    return(total_time)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 6. \n",
    "Use the code you wrote for Lesson 1.2 (i.e., selection sort, bubble sort, insertion sort). Plot the following graphs:\n",
    "* **Graph 1**: 4 lines for **the number of steps** of each of the 4 sorting algorithms (i.e., selection sort, bubble sort, insertion sort, merge sort). Which algorithm performs best? Why? \n",
    "* **Graph 2**: 4 lines for **the timing** of each of the 4 sorting algorithms (i.e., selection sort, bubble sort, insertion sort, merge sort). Which algorithm performs best? Why?\n",
    "\n",
    "Using as many cells as you wish (code cells or markdown cells alike) to complete this question.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "0561f29260f91795736500d62066a4c7",
     "grade": true,
     "grade_id": "cell-d09efb7c7fe55e69",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-8-b336fbd4fd81>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-8-b336fbd4fd81>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    import selectionSort() from first #importing functions from another first.py script\u001b[0m\n\u001b[0m                        ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "import selectionSort() from first #importing functions from another first.py script\n",
    "import bubbleSort() from first\n",
    "import insertionSort() from first\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "y=count_step_merge # the steps counted from the merge sort function\n",
    "\n",
    "z=count_step_insertion #the steps counted from the insertion sort in another .py file\n",
    "\n",
    "L=count_step_bubble # the steps counted from the bubble sort in another .py file\n",
    "\n",
    "M= count_step_selection #the steps counted from the selection sort in another .py file\n",
    "alist= [33,100,55,666,100,2,3,4,1,0,-1]\n",
    "x= len(alist)\n",
    "plt.scatter(x,y)\n",
    "plt.scatter(x,z)\n",
    "plt.scatter(x,L)\n",
    "plt.scatter(x,M)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code has bugs so it didn't run. I expect that the merge and bubble sort will demonstrate the highest number of steps. The merge sort divides the array until it reach arrays with one item only, then it solves the problem and merge everything back in one array. Thus, I predict it will take a lot of steps to do that particularly with large array size. Also, the bubble sort swaps all the elements until it reaches the correct order. If we have a list that is reversed(descending order) and we want it to be in ascedning order, that will take many steps as it represents the worst case scenario as all items will be swaped. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import selectionSort() from file #importing functions from another .py script\n",
    "import bubbleSort() from file\n",
    "import insertionSort() from file\n",
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "a= time.time()\n",
    "mylist= [44,100,1,2,4, 500]\n",
    "merge_sort(mylist,0,5)\n",
    "b=time.time\n",
    "y=b-a #running time for merge_sort\n",
    "\n",
    "a= time.time()\n",
    "mylist= [44,100,1,2,4, 500]\n",
    "selectionSort(mylist,0,5)\n",
    "b=time.time\n",
    "z=b-a #running time for selectoionSort\n",
    "\n",
    "a= time.time()\n",
    "mylist= [44,100,1,2,4, 500]\n",
    "bubbleSort(mylist,0,5)\n",
    "b=time.time\n",
    "L=b-a #running time for bubble sort\n",
    "\n",
    "\n",
    "a= time.time()\n",
    "mylist= [44,100,1,2,4, 500]\n",
    "bubbleSort(mylist,0,5)\n",
    "b=time.time\n",
    "M=b-a #running time for insertion sort\n",
    "\n",
    "x= len(mylist)\n",
    "\n",
    "plt.scatter(x,y)\n",
    "plt.scatter(x,z)\n",
    "plt.scatter(x,L)\n",
    "plt.scatter(x,M)\n",
    "\n",
    "plt.show()\n",
    "#this code plots the number of items in array against the time taken\n",
    "#the code has a bug as it only plots one list (which appears one list on the graph)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I couldn't see the results of the graph as the code has bugs that I coultn't figure out yet. But I predict that the faster is merge_sort as the input size of the array increases (its running time is nlogn compared to On2). However, if the size of the array is smaller, one of the other sort algorithm will result in faster running time. "
   ]
  }
 ],
 "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
}

gistfile1.txt

{
 "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": "4394bdd5d17d8ce7ce4e758066ee0266",
     "grade": false,
     "grade_id": "cell-9e44910e5a73668d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 2.1\n",
    "\n",
    "## Question 1.\n",
    "\n",
    "First, please read carefully [this note](https://drive.google.com/open?id=1SfrRTKWDb6szsJENgvNF7-u2B96ecaF2) which reviews the MERGE operation in Cormen et al.\n",
    "\n",
    "After reviewing the example above (Cormen et. al., Figure 2.3),  you need to manually create similar illustrations as in the example above but this time for the input array:\n",
    "\n",
    "![array](array.png)\n",
    "\n",
    "For this exercise, assume that the call to the algorithm is MERGE(A, 1, 3, 6) and draw different resulting stages of the arrays A, L, and R as the merge algorithm is executed.  You can hand-draw or use any drawing tool to produce panel illustrations as in the example above.  Include your final drawings in the cell below. Feel free to use additional cells (Markdown or Code) for this question.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "b4d0caf51fb6b587f68db4e806af35d0",
     "grade": true,
     "grade_id": "cell-badbff7790708987",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "\n",
    "![part1](part1.png)\n",
    "![part2](part2.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "7c9608898d23ecbe07c084ca6d6da655",
     "grade": false,
     "grade_id": "cell-6dd1317d1ea8ab9f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2.\n",
    "Now using your understanding of Part I of the merge algorithm, can you think of an efficient way to implement this part in Python? (hint: using Python list). Give your answer in prose in the cell below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9bf35550640c33f366c5cffad7fdf33a",
     "grade": true,
     "grade_id": "cell-4f961721620a6645",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "Use list comprehension to copy the elements of the array into two sub arrays:\n",
    "\n",
    "-list comprehension improves the performance of the code and makes the execution time faster (compared to the appending method)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "010584ea3a4f00fba43b52bb04cd0ed2",
     "grade": false,
     "grade_id": "cell-84932c7c0c20b750",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3.\n",
    "\n",
    "Write a Python implementation of the merge pseudocode (both parts), your Python function must take the same four input arguments as described in the $MERGE(A,p,q,r)$. Test your code by running the example in problem 1 and 2 of this pre-class work. Feel free to come up with additional cases to check if your code is working properly. Your code should return A "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "43760e27d0b385c30476353b3d546a79",
     "grade": false,
     "grade_id": "cell-a67719d65c1ac9f3",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def merge(A, p, q, r):\n",
    "    n1= q-p+1 #computes the length of the first subarray\n",
    "    n2= r-q #computes the length of the second subarray\n",
    "   \n",
    "    L = [0] * n1 #create temporary array with certain size of n1\n",
    "    R = [0] *n2 #create temporary array with certain size of n2\n",
    "    \n",
    "    for i in range(0,n1): #copy data from main array to temporay array L \n",
    "        L[i]=A[p+i]\n",
    "    for j in range(0,n2):#copy data from main array to temporary array R\n",
    "        R[j]=A[q+j]\n",
    "    i=0 #intializing the variable to use it as a pointer for the index in L[]\n",
    "    j=0 #intializing the variable to use it as a pointer for the index R[]\n",
    "    \n",
    "    for k in A:\n",
    "        while i<n1 and j<n2: #make sure we reach only the last element in the arrays (sentinel card)\n",
    "            if L[i] <= R[j]: #comparing between two elements\n",
    "                A[k] = L[i] #copying the smaller element to the main array\n",
    "                i+=1 #increament the index by one\n",
    "            else:\n",
    "                A[k] = R[j]\n",
    "                j+=1 #increament the index of by one\n",
    "                 \n",
    "    return(A)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "699908274975a6bff4f9fb021e666ce4",
     "grade": true,
     "grade_id": "cell-e98759fe14428af0",
     "locked": true,
     "points": 0,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Please ignore this cell. This cell is for us to implement the tests \n",
    "# to see if your code works properly. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "35e241fec3dd026733d04a51fa2972fe",
     "grade": false,
     "grade_id": "cell-49f3f61ee6d72bb9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2\n",
    "Suppose that your Python implementation of the merge algorithm is already working. Inspect the code for merge sort below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "53611abb1448334a346783091382fb12",
     "grade": false,
     "grade_id": "cell-073a21c6aac8225e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def merge_sort(A,p,r):\n",
    "    if p < r:\n",
    "        q = (p+r)/2\n",
    "        merge_sort(A,p,q)\n",
    "        merge_sort(A,q+1,r)\n",
    "        merge(A,p,q,r)\n",
    "    return(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b708edb1e6e70731f3ec68d1d11c2890",
     "grade": false,
     "grade_id": "cell-c19a4320995e15b2",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Copy and paste the code above to the cell below and fix the bug in it. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "d52aee435812fe91886c6dcdfc4e3f6d",
     "grade": false,
     "grade_id": "cell-311695db35c06d65",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def merge_sort(A,p,r):\n",
    "    if p < r:\n",
    "        q = (p+r)//2 #make sure the division results in an integer number (not float)\n",
    "        merge_sort(A,p,q)\n",
    "        merge_sort(A,q+1,r)\n",
    "        merge(A,p,q,r)\n",
    "    return(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "35fbb3c437b3ba39ede0d87d6719223b",
     "grade": true,
     "grade_id": "cell-a3a71f67390c1f82",
     "locked": true,
     "points": 0,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Please ignore this cell. This cell is for us to implement the tests \n",
    "# to see if your code works properly. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "61cfba995efe3c9c37092a650047fdf3",
     "grade": false,
     "grade_id": "cell-5b296f793fefdbfe",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Question 5.\n",
    "As in the previous Lesson, count the number of steps and time your merge_sort() function with the following input: `list_k = [i for i in range(100*k, 0, -1)] `, where $k= 1, 2, 3, …, 15 $. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "cc3f59157e795d05422e849f3e7cc03a",
     "grade": true,
     "grade_id": "cell-8a4233ab58d3d0bb",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import time\n",
    "count_steps =0\n",
    "\n",
    "def merge(A, p, q, r):\n",
    "    n1= q-p+1 #computes the length of the first subarray\n",
    "    n2= r-q #computes the length of the second subarray\n",
    "   \n",
    "    L = [0] * n1 #create temporary array with certain size of n1\n",
    "    R = [0] *n2 #create temporary array with certain size of n2\n",
    "    \n",
    "    for i in range(0,n1): #copy data from main array to temporay array L \n",
    "        L[i]=A[p+i]\n",
    "    for j in range(0,n2):#copy data from main array to temporary array R\n",
    "        R[j]=A[q+j]\n",
    "    i=0 #intializing the variable to use it as a pointer for the index in L[]\n",
    "    j=0 #intializing the variable to use it as a pointer for the index R[]\n",
    "    \n",
    "    for k in A:\n",
    "        while i<n1 and j<n2: #make sure we reach only the last element in the arrays (sentinel card)\n",
    "            if L[i] <= R[j]: #comparing between two elements\n",
    "                A[k] = L[i] #copying the smaller element to the main array\n",
    "                i+=1 #increament the index by one\n",
    "                count_step+=1\n",
    "            else:\n",
    "                A[k] = R[j]\n",
    "                j+=1 #increament the index of by one\n",
    "                count_step+=1\n",
    "def merge_sort(A,p,r):\n",
    "    begin=time.time\n",
    "    if p < r:\n",
    "        count_step+=1\n",
    "        q = (p+r)//2 #make sure the division results in integer number (not float)\n",
    "        merge_sort(A,p,q)\n",
    "        merge_sort(A,q+1,r)\n",
    "        merge(A,p,q,r)\n",
    "    end=time.time\n",
    "    total_time= end - begin\n",
    "    count_step_merge\n",
    "    return(A)\n",
    "    return(count_Step_merge)\n",
    "    return(total_time)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 6. \n",
    "Use the code you wrote for Lesson 1.2 (i.e., selection sort, bubble sort, insertion sort). Plot the following graphs:\n",
    "* **Graph 1**: 4 lines for **the number of steps** of each of the 4 sorting algorithms (i.e., selection sort, bubble sort, insertion sort, merge sort). Which algorithm performs best? Why? \n",
    "* **Graph 2**: 4 lines for **the timing** of each of the 4 sorting algorithms (i.e., selection sort, bubble sort, insertion sort, merge sort). Which algorithm performs best? Why?\n",
    "\n",
    "Using as many cells as you wish (code cells or markdown cells alike) to complete this question.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "0561f29260f91795736500d62066a4c7",
     "grade": true,
     "grade_id": "cell-d09efb7c7fe55e69",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-8-b336fbd4fd81>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-8-b336fbd4fd81>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    import selectionSort() from first #importing functions from another first.py script\u001b[0m\n\u001b[0m                        ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "import selectionSort() from first #importing functions from another first.py script\n",
    "import bubbleSort() from first\n",
    "import insertionSort() from first\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "y=count_step_merge # the steps counted from the merge sort function\n",
    "\n",
    "z=count_step_insertion #the steps counted from the insertion sort in another .py file\n",
    "\n",
    "L=count_step_bubble # the steps counted from the bubble sort in another .py file\n",
    "\n",
    "M= count_step_selection #the steps counted from the selection sort in another .py file\n",
    "alist= [33,100,55,666,100,2,3,4,1,0,-1]\n",
    "x= len(alist)\n",
    "plt.scatter(x,y)\n",
    "plt.scatter(x,z)\n",
    "plt.scatter(x,L)\n",
    "plt.scatter(x,M)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code has bugs so it didn't run. I expect that the merge and bubble sort will demonstrate the highest number of steps. The merge sort divides the array until it reach arrays with one item only, then it solves the problem and merge everything back in one array. Thus, I predict it will take a lot of steps to do that particularly with large array size. Also, the bubble sort swaps all the elements until it reaches the correct order. If we have a list that is reversed(descending order) and we want it to be in ascedning order, that will take many steps as it represents the worst case scenario as all items will be swaped. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import selectionSort() from file #importing functions from another .py script\n",
    "import bubbleSort() from file\n",
    "import insertionSort() from file\n",
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "a= time.time()\n",
    "mylist= [44,100,1,2,4, 500]\n",
    "merge_sort(mylist,0,5)\n",
    "b=time.time\n",
    "y=b-a #running time for merge_sort\n",
    "\n",
    "a= time.time()\n",
    "mylist= [44,100,1,2,4, 500]\n",
    "selectionSort(mylist,0,5)\n",
    "b=time.time\n",
    "z=b-a #running time for selectoionSort\n",
    "\n",
    "a= time.time()\n",
    "mylist= [44,100,1,2,4, 500]\n",
    "bubbleSort(mylist,0,5)\n",
    "b=time.time\n",
    "L=b-a #running time for bubble sort\n",
    "\n",
    "\n",
    "a= time.time()\n",
    "mylist= [44,100,1,2,4, 500]\n",
    "bubbleSort(mylist,0,5)\n",
    "b=time.time\n",
    "M=b-a #running time for insertion sort\n",
    "\n",
    "x= len(mylist)\n",
    "\n",
    "plt.scatter(x,y)\n",
    "plt.scatter(x,z)\n",
    "plt.scatter(x,L)\n",
    "plt.scatter(x,M)\n",
    "\n",
    "plt.show()\n",
    "#this code plots the number of items in array against the time taken\n",
    "#the code has a bug as it only plots one list (which appears one list on the graph)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I couldn't see the results of the graph as the code has bugs that I coultn't figure out yet. But I predict that the faster is merge_sort as the input size of the array increases (its running time is nlogn compared to On2). However, if the size of the array is smaller, one of the other sort algorithm will result in faster running time. "
   ]
  }
 ],
 "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
}