examples/insertion-sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "458b84d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pybryt\n",
    "from lecture import pybryt_reference"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1031e72e",
   "metadata": {},
   "source": [
    "# Exercise 1.1: Insertion sort\n",
    "\n",
    "One of the well known sorting algortithm is **insertion sort**. To understand how it works, watch the following [YouTube video](https://www.youtube.com/watch?v=JU767SDMDvA).\n",
    "\n",
    "Now, let us see if you understood how insertion sort works. Please write a Python function `insertion_sort(x)`, which takes list `x` as an argument, performs **insertion sort** and returns a sorted list.\n",
    "\n",
    "Happy coding!\n",
    "\n",
    "### Correct Solution - students implements the algorithm correctly"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d73a4c64",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(x):\n",
    "    for i in range(1, len(x)):\n",
    "        # We are going to look for the value of current\n",
    "        # to determine if the outer loop is correct\n",
    "        current = x[i]\n",
    "        \n",
    "        # By looking for the values of j,\n",
    "        # we determine if the inner loop is right.\n",
    "        j = i - 1\n",
    "        while j >=0 and current < x[j] :\n",
    "            x[j+1] = x[j]\n",
    "            j -= 1\n",
    "            \n",
    "        x[j+1] = current\n",
    "        # We will monitor list x to see if it evolves correctly.\n",
    "        \n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed09ba9d",
   "metadata": {},
   "source": [
    "Now, let us look at two different testing/feedback methods:\n",
    "* **Unit-test-like \"feedback\"** is the testing method we have used before PyBryt. This method only tells us whether the final solution is correct or wrong. However, no information about what is wrong in the function source is given.\n",
    "* **PyBryt feedback**: PyBryt radically changes how the code is tested. It is not only the final solution that is being examined, but also the implementation itself. This way, a detailed feedback is generated pointing the student to where the mistake is.\n",
    "\n",
    "Let us have a look at the difference between these two testing/feedback approaches.\n",
    "\n",
    "#### Unit-test-like \"feedback\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d1d7d4f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [55, 111, -33, 65, 1001, -362, 451]\n",
    "assert insertion_sort(x) == list(sorted(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "120a572e",
   "metadata": {},
   "source": [
    "From this feedback, both the student and the lecturer can only see if the final solution is correct. However, we cannot determine what sorting algorithm was used. Maybe the student wrote `return list(sorted(x))`?! The only way for us to check the implementation is to look at the source code and analyse it.\n",
    "\n",
    "#### PyBryt feedback"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a4878d74",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "REFERENCE: exercise-1_1\n",
      "SATISFIED: True\n",
      "MESSAGES:\n",
      "  - SUCCESS: Wow! Your algorithm updates the list as it should.\n",
      "  - SUCCESS: Your outer loop iterates from the second element to the last. Well done!\n",
      "  - SUCCESS: Great! Your inner loop iterates towards left.\n",
      "  - SUCCESS: Amazing! Your function returns the correct solution.\n"
     ]
    }
   ],
   "source": [
    "with pybryt.check(pybryt_reference(1, 1)):\n",
    "    insertion_sort([55, 111, -33, 65, 1001, -362, 451])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8fa78040",
   "metadata": {},
   "source": [
    "PyBryt gives a much more detailed feedback emphasising all the points student's function does right. This way, we can ensure the function performs insertion sort and not some other sorting algorithm. For lecturers, this speeds up marking substantially. On the other hand, the student can see all the steps she did right, which helps with the learning experience and it is more encouraging.\n",
    "\n",
    "### Wrong solution\n",
    "\n",
    "Let us say the student made a mistake... student's outer loop does not iterate all the way to the end (`len(x)-1` instead of `len(x)`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8b8b8ed4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(x):\n",
    "    for i in range(1, len(x)-1):  # MISTAKE: len(x)-1 instead of len(x)\n",
    "        current = x[i]\n",
    "        \n",
    "        j = i - 1\n",
    "        while j >=0 and current < x[j] :\n",
    "            x[j+1] = x[j]\n",
    "            j -= 1\n",
    "            \n",
    "        x[j+1] = current\n",
    "        \n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98d63c9a",
   "metadata": {},
   "source": [
    "#### Unit-test-like \"feedback\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5f6c20b7",
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-ad50795e9ab5>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mx\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;36m55\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m111\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m-\u001b[0m\u001b[0;36m33\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m65\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1001\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m-\u001b[0m\u001b[0;36m362\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m451\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0minsertion_sort\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mlist\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msorted\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "# NBVAL_SKIP\n",
    "x = [55, 111, -33, 65, 1001, -362, 451]\n",
    "assert insertion_sort(x) == list(sorted(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddb2c00f",
   "metadata": {},
   "source": [
    "From this feedback, the student can only see that the final solution is wrong. However, no further information on how to improve the code is given. At this point, the student often raises their hand looking for a TA to help. Similarly, although the lecturer can see that the final solution is wrong, the only way to mark the assignment is to carefully examine the code.\n",
    "\n",
    "#### PyBryt feedback"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e48ead2e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "REFERENCE: exercise-1_1\n",
      "SATISFIED: False\n",
      "MESSAGES:\n",
      "  - ERROR: Hmmm... It looks like your algorithm does not perform insertion sort.\n",
      "  - ERROR: Please make sure your outer loop iterates from the second element to the last.\n",
      "  - SUCCESS: Great! Your inner loop iterates towards left.\n",
      "  - ERROR: Your function returns a wrong solution.\n"
     ]
    }
   ],
   "source": [
    "with pybryt.check(pybryt_reference(1, 1)):\n",
    "    insertion_sort([55, 111, -33, 65, 1001, -362, 451])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "586153f4",
   "metadata": {},
   "source": [
    "From the PyBryt's feedback, the student can see that although her inner loop is correct, the outer loop is wrong. Because of this, the algorithm does not perform sort as expected an other two `ERROR` messages are shown as well. This allows the student not only to see if her final solution is correct, but also what exactly is wrong and point the student to the \"outer loop\" to correct the mistake. Similarly, the lecturer does not have to go into the source code and try to find where a mistake is, but he can refer to the PyBryt's feedback.\n",
    "\n",
    "### Cheating case\n",
    "\n",
    "Let us also have a look at the extreme case:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "e7aed9f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(x):\n",
    "    return list(sorted(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09460801",
   "metadata": {},
   "source": [
    "#### Unit-test-like \"feedback\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "380bc0c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [55, 111, -33, 65, 1001, -362, 451]\n",
    "assert insertion_sort(x) == list(sorted(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "822d712e",
   "metadata": {},
   "source": [
    "Everything seems to be fine. However, we have no idea if insertion sort was implemented.\n",
    "\n",
    "#### PyBryt feedback"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "fc19525f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "REFERENCE: exercise-1_1\n",
      "SATISFIED: False\n",
      "MESSAGES:\n",
      "  - ERROR: Hmmm... It looks like your algorithm does not perform insertion sort.\n",
      "  - ERROR: Please make sure your outer loop iterates from the second element to the last.\n",
      "  - ERROR: Please make sure your inner loop iterates towards left.\n",
      "  - SUCCESS: Amazing! Your function returns the correct solution.\n"
     ]
    }
   ],
   "source": [
    "with pybryt.check(pybryt_reference(1, 1)):\n",
    "    insertion_sort([55, 111, -33, 65, 1001, -362, 451])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb5e6b0c",
   "metadata": {},
   "source": [
    "Here, we can see that although PyBryt tells us that the final solution is correct, there are three `ERROR` messages to indicate the something is wrong."
   ]
  }
 ],
 "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}