CS110 1.2 - Insertion Sort

cs110_pcw_1_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 = \"Tiago Flora\"\n",
    "COLLABORATORS = [\"Ara Mkhoyan\", \"Chloe Gabrielle\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "947eded9ca5fab593f017a71dd26277b",
     "grade": false,
     "grade_id": "cell-b46066345313bea6",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 1.2\n",
    "\n",
    "\n",
    "\n",
    "## Question 1\n",
    "The following pseudocode has been extracted from Cormen et al. You should analyze the lines of the pseudocode trying to understand what every line in the pseudocode does and how many times is that line executed. \n",
    "![Insertion sort pseudo-code](insertionsort_pseudo.png)\n",
    "\n",
    "Answer the following questions: What does line 7 do? Why is it necessary?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "104f443d240e2139d778711f6bc0a766",
     "grade": true,
     "grade_id": "cell-3bac59ff24b11a27",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "Line 7 guarantees two things that are fundamental for insertion sort. It decreases the value of the index i in every iteration of the while loop. That means it is a vital line to meet the termination condition of the while loop, which is executed when i is positive, otherwise it would be executed until a runtime error shows up or your computer crashes. The other result of this is to 'move' the elements A[i] along the array, to leave space for A[j] to be inserted in the correct slot."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "7872c2d656a6cb3aaeff2b4fa41eb204",
     "grade": false,
     "grade_id": "cell-0ca65d04b209f37f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2\n",
    "The following Python code is an attempt to implement the Insertion-Sort pseudocode above. However, this code has a bug. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8e004cd5b12aee0ecf19786bc1a71d81",
     "grade": false,
     "grade_id": "cell-348fe9383ed7e0c7",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def insertionSort(A):\n",
    "    for j in range(len(A)):\n",
    "        key = A[j]\n",
    "        i= j-1\n",
    "        while i >= 0 and A[i]>key:\n",
    "            A[i+1] = A[i]\n",
    "            i -= 1\n",
    "            A[i+1] = key\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "19a9183b993f6180d79385fed5dd07ee",
     "grade": false,
     "grade_id": "cell-16653cdc16be28b9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Copy and paste the code in the cell below. Identify and correct the bug. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "7c22d14f97eaad956abf7dae17c7317f",
     "grade": false,
     "grade_id": "cell-1b7488e89cb501c5",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def insertionSort(A):\n",
    "    for j in range(len(A)):\n",
    "        key = A[j]\n",
    "        i= j-1\n",
    "        while i >= 0 and A[i]>key:\n",
    "            A[i+1] = A[i]\n",
    "            i -= 1\n",
    "        A[i+1] = key\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4ff6145033c64da48f2a44f040b2c1b7",
     "grade": true,
     "grade_id": "cell-3432ce8ae2493fa6",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert(insertionSort([0]) == [0])\n",
    "assert(insertionSort([-1,1]) == [-1,1])\n",
    "assert(insertionSort([1,-1]) == [-1,1])\n",
    "assert(insertionSort([1,6,3,6]) == [1,3,6,6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a25900fe2fba8d1695b31865625ec1eb",
     "grade": false,
     "grade_id": "cell-1399c3a86cc2dd7c",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "How do you know this code works as intended now?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "4ff5af35daed9a5442ba229263bdde33",
     "grade": true,
     "grade_id": "cell-442998d5fdd8b561",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "If we run the cell with all the 'assert' statements, we see that it does nothing and there is no output. Before, as the assert conditions evaluated to false, we had four AssertionError instances. If we check the comparisons between the function's outpupt and the sorted arrays we input into it, we find they're all true, as expected. <br>\n",
    "Another way to know the code works as intended now is that removing the indentation from 'A[i+1]=key' guarantees the maintenance of the 'while' loop invariant, which in this case is that every element of A[1..i] is smaller than A[j]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(insertionSort([0]) == [0])\n",
    "print(insertionSort([-1,1]) == [-1,1])\n",
    "print(insertionSort([1,-1]) == [-1,1])\n",
    "print(insertionSort([1,6,3,6,4]) == [1,3,4,6,6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9d7a3b260b0fef93382fb52aa393f963",
     "grade": false,
     "grade_id": "cell-0ac1c20b43acb363",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3 \n",
    "Implement the bubble sort algorithm in the cell below. First, look up the corresponding pseudocode in Cormen et al. (page 40), and write a Python implementation for the bubble sort.  Like in the `insertionSort`,  your new Python function, `bubbleSort`, takes a list of elements as an argument and returns the sorted list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "16ff8874250907a794fdd3fa6c13bbec",
     "grade": false,
     "grade_id": "cell-b709733c96d8b615",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def bubbleSort(A):\n",
    "    for i in range(len(A)):\n",
    "        # j must start at len(A)-1, and  move backwards\n",
    "        for j in range(len(A)-1, 0, -1):\n",
    "            # If an element is larger than the preceding number, they swap orders\n",
    "            if A[j] < A[j-1]:\n",
    "                A[j], A[j-1] = A[j-1], A[j]\n",
    "            j -= 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e7dc1709a92c6bcac7df39da1771e649",
     "grade": true,
     "grade_id": "cell-ffc9b251ea0047ba",
     "locked": true,
     "points": 2,
     "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": "eae899834db5b5ff1b2b1d67d8ef5929",
     "grade": false,
     "grade_id": "cell-60a96a427cd3e94e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Is your program bug-free? Think of three different [“test cases”](https://www.hiredintech.com/classrooms/algorithm-design/lesson/83) to check the correctness of your code. If a code passes the tests you have just outlined, is this an unambiguous proof that the code is correct? Give your answer in the cell below. Feel free to use additional cells (Markdown or Code) as you wish."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "eb02c9951e19ee43d128fa93dd53eaad",
     "grade": true,
     "grade_id": "cell-5ecb51404140cb2f",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "Given the definition of the sorting problem, the program seems to be bug-free. Testing a few edge cases, we can further strenghten the point. We tested the program with negative numbers, repeated numbers, a single-element list, a sorted list, and even strings. All the numerical tests return correctly sorted lists, and the strings are returned in alphabetical order (with upper-case letters having priority over lower-case letters). <br>\n",
    "It's not unambiguous proof the code is correct. We'd need "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-4, -3, -2, 1, 2, 3, 4, 5, 8, 10] [0, 0, 0, 0, 1, 2, 2] [1] [4, 5, 9, 100] ['Amazing', 'This', 'absolutely', 'is']\n"
     ]
    }
   ],
   "source": [
    "print(bubbleSort([3,2,-3,1,5,4,-4,-2,10,8]), \n",
    "      bubbleSort([0,1,0,2,0,2,0]),\n",
    "      bubbleSort([1]),\n",
    "      bubbleSort([4,5,9,100]),\n",
    "      bubbleSort([\"This\", \"is\", \"absolutely\", \"Amazing\"]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "cb0b8b9c4b153530d47b437baa24098d",
     "grade": false,
     "grade_id": "cell-b22dce6b32afe1a9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4\n",
    "The following pseudocode corresponds to a third sorting algorithm to be covered in Lesson 1.2, the selection sort.  Like in the previous step, write a Python implementation of the algorithm and make sure that your program is bug-free. `selectionSort` should take a list of elements as an argument and return the sorted list.\n",
    "\n",
    "![Selection sort pseudo-code](selectionsort_pseudo.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "2f4365879ed0fd5b360bc25f4795c113",
     "grade": false,
     "grade_id": "cell-e04f94e5d418923c",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# Following the pseudo-code provided in Cormen, we get:\n",
    "def selectionSort(A):\n",
    "    # Iterate over the whole array and assume an element is the smallest for comparison\n",
    "    for i in range(len(A)):\n",
    "        minidx = i\n",
    "        for j in range(len(A)):\n",
    "            # For every next element, compare it to the current one\n",
    "            if A[j] > A[minidx]:\n",
    "                # If any element is smaller, the minimum element is now assumed to be it\n",
    "                minidx = j\n",
    "            # Swap the positions of the original element being compared (A[i]) and the new minimum\n",
    "            A[i], A[minidx] = A[minidx], A[i]\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-4, -2, 1, 3, 3, 5, 6, 10]\n"
     ]
    }
   ],
   "source": [
    "print(selectionSort([-2,1,5,3,-4,6,3,10]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "352859ddf81204abd5eb3d91570919c7",
     "grade": true,
     "grade_id": "cell-ffe912ac7922de70",
     "locked": true,
     "points": 1,
     "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": "2305488ea190bf7b0347891f06164775",
     "grade": false,
     "grade_id": "cell-7ff8930bd7d30706",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Please make sure you try your best to code insertion sort, selection sort and bubble sort, and bring these programs to class. You will need them for a class activity.**"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}