2022/week-5.ipynb

{
 "cells": [
  {
   "cell_type": "raw",
   "id": "0d25b75c-d404-401c-8703-09065dc1640a",
   "metadata": {},
   "source": [
    "Table of Contents:\n",
    "- [Introduction](#Welcome-to-CPG!)\n",
    "- [Week 5 content](#Week-4-Sorting)\n",
    "- [Crash course in complexity]()\n",
    "- [Complexities of sorting algorithms]()\n",
    "- [Sleep sort!?](#sleep-sort)\n",
    "- [Example question](#Example-Question:-Sort-Colors)\n",
    "- [Hackerrank](#hackerrank-competition)"
   ]
  },
  {
   "cell_type": "raw",
   "id": "bc0c46f2-127f-4c81-bdd8-4d088650bbae",
   "metadata": {},
   "source": [
    "## Welcome Back to CPG!\n",
    "**Before we start...**\n",
    "\n",
    "If you'd like to follow along for yourself and run the code examples in our presentations, you can clone the repository and open up the Jupyter notebooks locally. Note this means you need to have installed [Jupyter](https://jupyter.org/install) - either JupyterLab or Jupyter Notebook will work fine. In the below example we use JupyterLab:\n",
    "```\n",
    "git clone git@github.com:UQComputingSociety/cpg\n",
    "cd cpg/2022\n",
    "jupyter-lab\n",
    "```"
   ]
  },
  {
   "cell_type": "raw",
   "id": "e0dc51d3-2d40-45b9-8c33-824026dd05a5",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Week 5: Sorting\n",
    "\n",
    "This week's focus will be on sorting. This is an incredibly broad topic but today we will briefly cover the basics."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29ba8414",
   "metadata": {},
   "source": [
    "## Crash Course in Complexity"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4deda361",
   "metadata": {},
   "source": [
    "O(...) is a rough estimate of how an algorithm performs as input size increases.\n",
    "\n",
    "O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)\n",
    "\n",
    "Examples of these complexities in practice:\n",
    "\n",
    "- O(1): lookup table, check if number is odd.\n",
    "- O(log n): binary search (see soon).\n",
    "- O(n): naive search through an array.\n",
    "- O(n log n): fastest sort.\n",
    "- O(n^2): naive two-sum (see soon).\n",
    "- O(2^n): list all combinations of a list.\n",
    "- O(n!): list all permutations of a list.\n",
    "\n",
    "![Complexities](assets/week-5/complexity.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24800c1b",
   "metadata": {},
   "source": [
    "## Average time complexities for sorting algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8c0cbd7",
   "metadata": {},
   "source": [
    "- Bubble sort: O(n^2)\n",
    "- Insertion sort: O(n^2)\n",
    "- Selection sort: O(n^2)\n",
    "- Quicksort: O(n log n)\n",
    "- Merge sort: O(n log n)\n",
    "- Bucket sort: O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5d079c7",
   "metadata": {},
   "source": [
    "## Sleep sort?!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "428a9b78",
   "metadata": {},
   "source": [
    "Researchers from Stanford and MIT have unanimously agreed that this is definitely one of the sorting algorithms of all time.\n",
    "\n",
    "It is worth noting that this only works if you have an array which contains non-negative numbers...\n",
    "\n",
    "![Sleep sort](assets/week-5/sleep-sort.jpg)\n",
    "\n",
    "The algorithm works as follows:\n",
    "\n",
    "For every element x in an array, start a new program that:\n",
    "\n",
    "- Sleeps for x seconds\n",
    "- Prints out x\n",
    "- The clock starts on all the elements at the same time.\n",
    "\n",
    "Not all sorting algorithms are created equal..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3138cdd",
   "metadata": {},
   "source": [
    "## Example Question: Sort Colors\n",
    "\n",
    "Also called the Dutch National Flag Problem, as originally proposed by Edsger Dijkstra.\n",
    "\n",
    "The flag of the Netherlands consists of three colors: red, white, and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.\n",
    "\n",
    "To represent the colours red, white and blue are the integers 0, 1 and 2 respectively.\n",
    "\n",
    "Could use an in-built sorting algorithm like 'sorted' in python, implementation of quick sort. Is there a way to do it in one pass?\n",
    "\n",
    "Consider intialising three pointers:\n",
    "- low = 0\n",
    "- mid = low\n",
    "- high = len(nums) - 1\n",
    "\n",
    "As we iterate through the array we have 3 cases:\n",
    "\n",
    "if nums[mid] == 0, we swap nums[mid] with nums[low] and increment both at once\n",
    "\n",
    "if nums[mid] == 1 No swap. We increment mid only\n",
    "\n",
    "if nums[mid] == 2 Here, we swap nums[mid] and decrement the high pointer only\n",
    "\n",
    "Why do we increment mid when swapping with a 2 but not when swapping with a 0?\n",
    "\n",
    "When swapping with the high pointer, it is possible to insert a 0 into the middle bucket of the array. This would remain incorrectly sorted as mid indicated the start of the 1 elements.\n",
    "\n",
    "Conversely, when swapping low only a 1 can be inserted into the middle of the array as the elements before mid are already sorted, so both mid can be incremented.\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "7b5f9502",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 1, 1, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "def sortColors(nums) -> None:\n",
    "\tlow = mid = 0\n",
    "\tsize = len(nums)\n",
    "\thigh = size - 1\n",
    "\twhile (mid <= high):\n",
    "\t\tif (nums[mid] == 0):\n",
    "\t\t\tnums[mid],nums[low] = nums[low], nums[mid]\n",
    "\t\t\tlow += 1\n",
    "\t\t\tmid += 1\n",
    "\t\telif (nums[mid] == 2):\n",
    "\t\t\tnums[high], nums[mid] = nums[mid], nums[high]\n",
    "\t\t\thigh -= 1\n",
    "\t\telse:\n",
    "\t\t\tmid += 1\n",
    "\n",
    "inp = [0, 1, 2, 1, 0, 2]\n",
    "sortColors(inp)\n",
    "print(inp)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e62241de",
   "metadata": {},
   "source": [
    "## Hackerrank Competition\n",
    "\n",
    "Follow this link to the Hackerrank to begin the mini competition and start solving some searching questions!\n",
    "\n",
    "https://www.hackerrank.com/cpg-230822\n",
    "Example problems pulled from https://usaco.guide/"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.4"
  },
  "vscode": {
   "interpreter": {
    "hash": "75e32c9b9f9acb3e344044c130a223afc04dfae24d98d8fcafb579bfe6a0a294"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}