incoming_students_algorithms101.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>Algorithms 101 - sorting a list of integer numbers</h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One of the simplest algorithms to sort a list of numbers is BubbleSort. You can watch one of the many video tutorials on BubbleSort available online, for example: https://www.youtube.com/watch?v=Jdtq5uKz-w4 (focus on the first 5:40 minutes).\n",
    "\n",
    "Below is python code implementing BubbleSort. Read the code and then \"run it\" by clicking on the cell below then pressing \"Ctrl + Enter\" together. You will know the cell has been run if the left mark ```In[]``` changes to ```In[1]```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# python program implementing BubbleSort over a list of numbers\n",
    "  \n",
    "def bubbleSort(mylist): \n",
    "    n = len(mylist) \n",
    "  \n",
    "    # traverse through all the elements in the list\n",
    "    for i in range(n-1): \n",
    "  \n",
    "        # last i elements are already in place\n",
    "        # continue to sort the first (n-i)\n",
    "        for j in range(0, n-i-1): \n",
    "  \n",
    "            # traverse the list from 0 to n-i-1 \n",
    "            # swap if the element found is greater than the next element \n",
    "            if mylist[j] > mylist[j+1] : \n",
    "                tmp = mylist[j]\n",
    "                mylist[j] = mylist[j+1] \n",
    "                mylist[j+1] = tmp \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is important you \"run\" the cell above, even if nothing is actually computed within it, so that the Bubble Sort function is defined (if you do not run it, when you next try call the function, you will get an error: \"NameError: name 'bubbleSort' is not defined\").\n",
    "\n",
    "To test whether the above algorithm works, you can run the following test code (click the cell below then press \"Ctrl+Enter\" together):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unsorted list is: [64, 34, 25, 12, 22, 11, 90]\n",
      "Sorted list is: [11, 12, 22, 25, 34, 64, 90]\n"
     ]
    }
   ],
   "source": [
    "# test code for Bubble Sort \n",
    "\n",
    "mytestlist = [64, 34, 25, 12, 22, 11, 90] \n",
    "\n",
    "print(\"Unsorted list is:\", mytestlist)\n",
    "\n",
    "bubbleSort(mytestlist) \n",
    "  \n",
    "print (\"Sorted list is:\", mytestlist) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "BubbleSort is functionally <b>correct</b>, but also extremelly <b>inefficient</b>. Change the value of the variable MAXNUMBER below and repeatedly run the cell, each time increasing the length of the list (e.g., from 100 to 1000, 10000, and 20000 integer numbers). See how long it takes to complete. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "#how many numbers to generate \n",
    "#try changing the value of MAXNUMBER below from 100 to 1000, 10000, 20000 and see how long it takes BubbleSort to complete\n",
    "MAXNUMBER = 100\n",
    "\n",
    "#min/max possible values to generate\n",
    "min_value = 0 \n",
    "max_value = 50000\n",
    "\n",
    "#create a random list of integers\n",
    "randomListOfIntegers = [random.randint(min_value, max_value) for i in range(MAXNUMBER)]\n",
    "\n",
    "print(\"Starting to sort\", MAXNUMBER, \"numbers. First 100 elements in the list:\")\n",
    "for i in range(0,99):\n",
    "    print(randomListOfIntegers[i], end=\" \")\n",
    "\n",
    "#sort the list\n",
    "bubbleSort(randomListOfIntegers)\n",
    "\n",
    "print(\"\\n \\nSorting complete. First 100 elements in the list:\")\n",
    "for i in range(0,99):\n",
    "    print(randomListOfIntegers[i], end=\" \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There exist many other ways (algorithms) to sort a list of numbers that run much faster than BubbleSort. They are already implemented and available in the <a href=\"https://pypi.org/project/pysort/\">PySort</a> python library. The library has already been installed, so you can just import it and start using it. Let us start with a function called ```mergeSort()```, which implements the Merge Sort algortihm. Run the cell below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#import the relevant library\n",
    "from sorting_techniques import pysort\n",
    "\n",
    "#create a sorting object\n",
    "sortingObj = pysort.Sorting()\n",
    "\n",
    "#set how many numbers to generate \n",
    "MAXNUMBER = 20000\n",
    "\n",
    "#create a new random list of integers as above\n",
    "randomListOfIntegers = [random.randint(min_value, max_value) for i in range(MAXNUMBER)]\n",
    "\n",
    "#sort the new list using MergeSort\n",
    "print(\"Sorting with MergeSort. First 100 elements in the list:\")\n",
    "for i in range(0,99):\n",
    "    print(randomListOfIntegers[i], end=\" \")\n",
    "\n",
    "sortedList = sortingObj.mergeSort(randomListOfIntegers)\n",
    "\n",
    "print(\"\\n \\nSorting complete. First 100 elements:\")\n",
    "for i in range(0,99):\n",
    "    print(sortedList[i], end=\" \")\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to evaluate the usefulness of this performance improvement, you can time how long it takes to run the code. To do so, we will make use of the Python timeit package. Run the next two cells, first to time how long it takes Bubble Sort to sort 20,000 random integers, then how long it takes Merge Sort."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "\n",
    "#create a new random list of integers \n",
    "randomListOfIntegers = [random.randint(min_value, max_value) for i in range(MAXNUMBER)]\n",
    "\n",
    "#sort it with BubbleSort, compute how long it takes, and print it\n",
    "\n",
    "starttime = timeit.default_timer()\n",
    "bubbleSort(randomListOfIntegers)\n",
    "endtime = timeit.default_timer()\n",
    "print(\"BubbleSort took\", endtime-starttime, \"to sort\", MAXNUMBER, \"integer numbers\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create a new random list of integers \n",
    "randomListOfIntegers = [random.randint(min_value, max_value) for i in range(MAXNUMBER)]\n",
    "\n",
    "#sort it with MergeSort, compute how long it takes, and print it\n",
    "\n",
    "starttime = timeit.default_timer()\n",
    "sortingObj.mergeSort(randomListOfIntegers)\n",
    "endtime = timeit.default_timer()\n",
    "print(\"MergeSort took\", endtime-starttime, \"to sort\", MAXNUMBER, \"integer numbers\")\n",
    "   \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>Exercise</b>. Now experiment on your own with other sorting algorithms, for example QuickSort. Quicksort is often dubbed \"the best\" sorting algorithm. It is available from the pysort library and you can call it as:\n",
    "\n",
    "<tt>sortingObj.quickSort(listname, min_index, max_index)</tt>\n",
    "\n",
    "Note that, as well as passing the name of the list of numbers to be sorted (listname), QuickSort also requires that you pass the min and max index in the list you wish to sort. If you follow from the examples above, you would call:\n",
    "\n",
    "<tt>sortingObj.quickSort(randomListOfIntegers, 0, MAXNUMBER-1)</tt>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now try again comparing MergeSort and QuickSort running time again, but using the list of numbers ```newListOfIntegers``` defined below instead of the previous ```randomListOfIntegers``` list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "MAXNUMBER = 2500\n",
    "\n",
    "newListOfIntegers = [(MAXNUMBER - i) for i in range(MAXNUMBER)]\n",
    "\n",
    "#first call MergeSort on the list above, compute and print its running time\n",
    "\n",
    "#now call QuickSort on the list above, compute and print its running time\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us try one final time, using the list of numbers below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "MAXNUMBER = 2500\n",
    "\n",
    "newListOfIntegers = [i for i in range(MAXNUMBER)]\n",
    "\n",
    "#first call MergeSort on the list above, compute and print its running time\n",
    "\n",
    "#now call QuickSort on the list above, compute and print its running time\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QuickSort is much slower than MergeSort on these two lists of numbers. Can you see what is peculiar about them? We will learn the whats and whys of sorting algorithms as part of the \"COMP0005 - Algorithms\" module in term 2. See you then!"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}