Lab-01-Selection Sort, Insertion Sort, Merge Sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this assignment, we will look at some sorting algorithms. Here we want to sort a list of elements based on their keys. Each element is represented as a pair $(k, v)$ where $k$ stands for the key and $v$ stands for the value. The final output should have the same elements as the input, but sorted in the increasing order of keys."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Tuples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python tuples are similar to lists. The key difference is that tuples are immutable. The basic usage is illustrated below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = (11, 21, 13)\n",
    "print(a[0], a[1], a[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following blocks are functions useful for testing your code. Please just run these blocks without any change."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random as rnd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Do NOT modify this cell!\n",
    "\n",
    "# Helper functions\n",
    "\n",
    "def toss_coin(p=0.5):\n",
    "    r = rnd.random()\n",
    "    if r <= p:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "\n",
    "def get_random_list(max_length=1000, min_length=0, key_start=0):\n",
    "    n = rnd.randint(min_length, max_length)\n",
    "    \n",
    "    values = list( range(n) )\n",
    "    rnd.shuffle( values )\n",
    "    \n",
    "    rls = []\n",
    "    \n",
    "    i = 0\n",
    "    while True:\n",
    "        # Toss a fair coin and decide whether to include this key or not.\n",
    "        if toss_coin():\n",
    "            rls.append( (key_start, values[i]) )\n",
    "            i += 1\n",
    "            \n",
    "            if i >= n:\n",
    "                break\n",
    "        \n",
    "        # Again toss a biased coin (p=0.9) to decide whether to increment the key.\n",
    "        if toss_coin(0.8):\n",
    "            key_start += 1\n",
    "            \n",
    "    rls2 = rls[:]\n",
    "    rnd.shuffle(rls2)\n",
    "    return rls2, rls\n",
    "    \n",
    "    \n",
    "def test_sort(sort_fn = None):\n",
    "    a = []\n",
    "    sort_fn(a)\n",
    "    assert a==[]\n",
    "\n",
    "    for i in range(10):\n",
    "        a, asorted = get_random_list(max_length=20, min_length=5, key_start=-10)\n",
    "        sort_fn(a)\n",
    "        assert [x[0] for x in a] == [x[0] for x in asorted]\n",
    "    \n",
    "\n",
    "    for i in range(5):\n",
    "        a, asorted = get_random_list(max_length=1000, min_length=100, key_start=-100)\n",
    "        sort_fn(a)\n",
    "        assert [x[0] for x in a] == [x[0] for x in asorted]\n",
    "        \n",
    "    print(\"Everything works!\")\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "get_random_list(5,5)[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selection Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Selection sort sorts by repeatedly finding the minimum of sublists. In the iteration $i$, the minimum of elements from indices $i$, $i+1$, ... is found. This minimum is put in the index $i$. So in the 0th iteration, the minimum of the whole list (indices $0$, $1$, ... ) is found and placed in the 0th position. In the 1st iteration, the minimum of the list excluding the first element (indices $1$, $2$, ... ) is found and put in the 1st position, and so on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_min(alist, start_idx=0):\n",
    "    # Return the index of the smallest element from the list alist[start_idx, start_idx+1, ....]\n",
    "    # Note that our list consists of tuples.\n",
    "    \n",
    "    # Your Code here.\n",
    "\n",
    "    return # return the index in the original list, not the tuple/value.\n",
    "\n",
    "def selection_sort(alist):\n",
    "    \n",
    "    for i in range(len(alist)):\n",
    "        idx = find_min(alist, i)\n",
    "                \n",
    "        # Now we swap the element at index idx with the index i\n",
    "        alist[i], alist[idx] = alist[idx], alist[i]\n",
    "        \n",
    "    return alist\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Do NOT modify this cell!\n",
    "\n",
    "# Test suit\n",
    "\n",
    "test_sort(sort_fn = selection_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Insertion Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In insertion sort, we maintain a sorted list of the elements we have seen so far. That is, once iteration $i$ is over, we can be sure that elements at indices $0$, $1$, $2$, ... $i$ are in sorted order. Now when we see the $\\text{alist}[i+1]$, we insert the element to the correct position so that all elements at indices $0$, $1$, ... $i$, $i+1$ are in sorted order. We continue this process until we get the sorted list. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(alist):\n",
    "    for i, kv in enumerate(alist):\n",
    "        # Our assumption: alist[0], alist[1], ... alist[i-1] are already sorted.\n",
    "        # Now insert the element alist[i] at the proper place and shift the tuples with keys which \n",
    "        # are greater than alist[i].\n",
    "        for j in range(i-1, -1, -1):\n",
    "            # If alist[j][0] is greater than kv[0], copy alist[j][0] to alist[j+1][0]\n",
    "            # Otherwise, break out of the loop.\n",
    "            # Your CODE here\n",
    "\n",
    "            \n",
    "        # Now we know where to copy kv\n",
    "        # Copy kv to that index.\n",
    "        # Your CODE here\n",
    "        \n",
    "    return alist # Not really needed since we are sorting in place.\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Do NOT modify this cell!\n",
    "\n",
    "# Test suit\n",
    "\n",
    "test_sort(sort_fn = insertion_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Merge Sort, we break the list to be sorted into two. Then we sort the two lists independently and then merge the two half lists to obtain the final sorted list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(ahalf_list1, ahalf_list2, alist):\n",
    "    # Given two sorted lists ahalf_list1 and ahalf_list2,\n",
    "    # produce the final sorted list in alist[0, 1, ...]\n",
    "\n",
    "    # YOUR CODE HERE\n",
    "    \n",
    "    return alist\n",
    "\n",
    "\n",
    "def merge_sort(alist):\n",
    "    n = len(alist)\n",
    "    if n < 2:\n",
    "        # No need to sort\n",
    "        return alist\n",
    "    \n",
    "    half_idx = n//2\n",
    "    \n",
    "    ahalf_list1 = alist[0:half_idx]\n",
    "    ahalf_list2 = alist[half_idx : n]\n",
    "    \n",
    "    merge_sort(ahalf_list1)\n",
    "    merge_sort(ahalf_list2)\n",
    "    \n",
    "    merge(ahalf_list1, ahalf_list2, alist)\n",
    "    \n",
    "    return alist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Do NOT modify this cell!\n",
    "\n",
    "# Test suit\n",
    "\n",
    "test_sort(sort_fn = merge_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Extra Credit: Evaluating the Runtime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following code evaluates the time taken by the various sorts for different sized inputs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def measure_time_sortn(sort_fn, n, count):\n",
    "    total_time = 0\n",
    "    for i in range(count):\n",
    "        to_sort = get_random_list(n, n)[0]\n",
    "        start = time.process_time()\n",
    "        sort_fn(to_sort)\n",
    "        total_time += time.process_time() - start\n",
    "    return total_time / count\n",
    "\n",
    "\n",
    "def measure_time_sort(sort_fn, ns, count=5):\n",
    "    ys = []\n",
    "    \n",
    "    for n in ns:\n",
    "        ys.append( measure_time_sortn(sort_fn, n, count))\n",
    "    return ys\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let us evaluate the three sorting functions\n",
    "\n",
    "ns = [n for n in range(10, 1000, 10)]\n",
    "\n",
    "ys_ss = measure_time_sort(selection_sort, ns)\n",
    "ys_is = measure_time_sort(insertion_sort, ns)\n",
    "ys_ms = measure_time_sort(merge_sort, ns)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now plot $\\text{ys_ss}$, $\\text{ys_is}$ and $\\text{ys_ms}$ against $\\text{ns}$ using matplotlib."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "# Your CODE here:\n",
    "\n",
    "\n"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}