3 - Time Complexity and Bubble Sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "67d97db8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example 1\n",
    "\n",
    "def foo(n):\n",
    "    x = 1 # 1\n",
    "    y = 2 # 1\n",
    "    z = 3 # 1\n",
    "    print(n) # 1\n",
    "    \n",
    "# Each line inside the function body being considered as 1 operation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "fce3b3f3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "foo(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7f008bb3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000\n"
     ]
    }
   ],
   "source": [
    "foo(1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "9439a04b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nNumber of operations = 4 (CONSTANT)\\nThey are independent from the input in the function.\\n'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "Number of operations = 4 (CONSTANT)\n",
    "They are independent from the input in the function.\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "7ea7768e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example 2\n",
    "\n",
    "def foo(n):\n",
    "    for i in range(n):\n",
    "        print(i, end = \" \") # n "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c6ad1100",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 "
     ]
    }
   ],
   "source": [
    "foo(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "63cd4ad7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 "
     ]
    }
   ],
   "source": [
    "foo(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "1fc311d6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nNumber of operations = n (LINEAR)\\nInput and number of operations share a linear relationship.\\n'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "Number of operations = n (LINEAR)\n",
    "Input and number of operations share a linear relationship.\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "c6936b9d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example 3\n",
    "\n",
    "def foo(n):\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            print(i + j, end = \" \") # n^2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "a0a5f94b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 1 2 "
     ]
    }
   ],
   "source": [
    "foo(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "badd5acf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6 "
     ]
    }
   ],
   "source": [
    "foo(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "01b3d4c2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nNumber of operations = n^2 (QUADRATIC)\\nInput and numver of operations share a quadratic relationship.\\n'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "Number of operations = n^2 (QUADRATIC)\n",
    "Input and numver of operations share a quadratic relationship.\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "ddb2a554",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example 4\n",
    "def foo(n):\n",
    "    x = 5 # 1\n",
    "    y = 10 # 1\n",
    "    \n",
    "    for i in range(n):\n",
    "        print(i) # n\n",
    "        \n",
    "        \n",
    "# Number of operations -> n + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "318a1f20",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example 5\n",
    "\n",
    "def foo(n):\n",
    "    x = 5\n",
    "    y = 10\n",
    "    \n",
    "    for i in range(n):\n",
    "        print(i) # n\n",
    "        \n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            print(i) # n^2\n",
    "            \n",
    "# Number of operations - Cost Function -> n^2 + n + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "17662511",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example 6 \n",
    "\n",
    "def foo(n):\n",
    "    if n == 1:\n",
    "        return \"We got 1\" # 1\n",
    "    \n",
    "    for i in range(n):\n",
    "        print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "5cf05cbf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int(1.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "0dc7843a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int(True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "546641ed",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JavaScript and TypeScript\n"
     ]
    }
   ],
   "source": [
    "random = {}\n",
    "random[1.1] = \"JavaScript\"\n",
    "random[1.0] = \"Python\"\n",
    "random[1] = \"C++\"\n",
    "random[True] = \"JAVA\"\n",
    "random[1+0j] = \"TypeScript\"\n",
    "\n",
    "print(f\"{random[1.1]} and {random[True]}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "a6fc887c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['weirdamI']"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ i+j+k for k in [\"I\"] for j in [\"am\"] for i in [\"weird\"] ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "903ea1fd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 9]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted([5, 4, 3, 7, 9, 1, 2, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "7c1cd171",
   "metadata": {},
   "outputs": [],
   "source": [
    "l = [5, 4, 3, 7, 9, 1, 2, 6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "3741d166",
   "metadata": {},
   "outputs": [],
   "source": [
    "l.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "acda5e32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 9]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d16cfaca",
   "metadata": {},
   "source": [
    "# Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "55dc6b73",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(a):\n",
    "    for i in range(len(a) - 1):\n",
    "        for j in range(len(a) - 1 - i):\n",
    "            if a[j] > a[j + 1]:\n",
    "                a[j], a[j+1] = a[j+1], a[j]\n",
    "                \n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "1b48090c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 9]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bubble_sort([5, 4, 3, 7, 9, 1, 2, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "a8c39110",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort_visual(a):\n",
    "    for i in range(len(a) - 1):\n",
    "        print(a)\n",
    "        \n",
    "        for j in range(len(a) - 1 - i):\n",
    "            swap = False\n",
    "            \n",
    "            if a[j] > a[j + 1]:\n",
    "                a[j], a[j+1] = a[j+1], a[j]\n",
    "                swap = True\n",
    "                \n",
    "            print(f\"\\t {a} -> {f'Swapped {a[j]} with {a[j+1]}' if swap else ''}\")\n",
    "    print('-' * 50)\n",
    "    \n",
    "    print(f\"FINAL RESULT -> {a}\")            \n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "222c1acf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 4, 3, 7, 9, 1, 2, 6]\n",
      "\t [4, 5, 3, 7, 9, 1, 2, 6] -> Swapped 4 with 5\n",
      "\t [4, 3, 5, 7, 9, 1, 2, 6] -> Swapped 3 with 5\n",
      "\t [4, 3, 5, 7, 9, 1, 2, 6] -> \n",
      "\t [4, 3, 5, 7, 9, 1, 2, 6] -> \n",
      "\t [4, 3, 5, 7, 1, 9, 2, 6] -> Swapped 1 with 9\n",
      "\t [4, 3, 5, 7, 1, 2, 9, 6] -> Swapped 2 with 9\n",
      "\t [4, 3, 5, 7, 1, 2, 6, 9] -> Swapped 6 with 9\n",
      "[4, 3, 5, 7, 1, 2, 6, 9]\n",
      "\t [3, 4, 5, 7, 1, 2, 6, 9] -> Swapped 3 with 4\n",
      "\t [3, 4, 5, 7, 1, 2, 6, 9] -> \n",
      "\t [3, 4, 5, 7, 1, 2, 6, 9] -> \n",
      "\t [3, 4, 5, 1, 7, 2, 6, 9] -> Swapped 1 with 7\n",
      "\t [3, 4, 5, 1, 2, 7, 6, 9] -> Swapped 2 with 7\n",
      "\t [3, 4, 5, 1, 2, 6, 7, 9] -> Swapped 6 with 7\n",
      "[3, 4, 5, 1, 2, 6, 7, 9]\n",
      "\t [3, 4, 5, 1, 2, 6, 7, 9] -> \n",
      "\t [3, 4, 5, 1, 2, 6, 7, 9] -> \n",
      "\t [3, 4, 1, 5, 2, 6, 7, 9] -> Swapped 1 with 5\n",
      "\t [3, 4, 1, 2, 5, 6, 7, 9] -> Swapped 2 with 5\n",
      "\t [3, 4, 1, 2, 5, 6, 7, 9] -> \n",
      "[3, 4, 1, 2, 5, 6, 7, 9]\n",
      "\t [3, 4, 1, 2, 5, 6, 7, 9] -> \n",
      "\t [3, 1, 4, 2, 5, 6, 7, 9] -> Swapped 1 with 4\n",
      "\t [3, 1, 2, 4, 5, 6, 7, 9] -> Swapped 2 with 4\n",
      "\t [3, 1, 2, 4, 5, 6, 7, 9] -> \n",
      "[3, 1, 2, 4, 5, 6, 7, 9]\n",
      "\t [1, 3, 2, 4, 5, 6, 7, 9] -> Swapped 1 with 3\n",
      "\t [1, 2, 3, 4, 5, 6, 7, 9] -> Swapped 2 with 3\n",
      "\t [1, 2, 3, 4, 5, 6, 7, 9] -> \n",
      "[1, 2, 3, 4, 5, 6, 7, 9]\n",
      "\t [1, 2, 3, 4, 5, 6, 7, 9] -> \n",
      "\t [1, 2, 3, 4, 5, 6, 7, 9] -> \n",
      "[1, 2, 3, 4, 5, 6, 7, 9]\n",
      "\t [1, 2, 3, 4, 5, 6, 7, 9] -> \n",
      "--------------------------------------------------\n",
      "FINAL RESULT -> [1, 2, 3, 4, 5, 6, 7, 9]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 9]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bubble_sort_visual([5, 4, 3, 7, 9, 1, 2, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "e86eaabe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nHOMEWORK ->\\n\\nFigure out a way to optimise bubble sort and save unnecesary iterations at the end :)\\n'"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "HOMEWORK ->\n",
    "\n",
    "Figure out a way to optimise bubble sort and save unnecesary iterations at the end :)\n",
    "'''"
   ]
  }
 ],
 "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}