Sorting and Searching.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ba58183b",
   "metadata": {},
   "source": [
    "# Sorting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "cbcce19b",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [4,5,8,1,9,15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c53eb51",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a85c3bf9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9c449366",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7163af91",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "af31acc8",
   "metadata": {},
   "source": [
    "### Inbuilt sorting methods"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0a1b4cf",
   "metadata": {},
   "source": [
    "#### sort() method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "50038415",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [4,5,8,1,9,15]\n",
    "a.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "3980c001",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 5, 8, 9, 15]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c47bc3b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "b = a.sort()\n",
    "# b = None\n",
    "# Does not return anything\n",
    "# It returns None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fc447c74",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af90067b",
   "metadata": {},
   "source": [
    "#### sorted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "1d776a19",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [4,5,8,1,9,15]\n",
    "\n",
    "b = sorted(a, reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "52e01f94",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 5, 8, 1, 9, 15]\n"
     ]
    }
   ],
   "source": [
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "4b5c118c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[15, 9, 8, 5, 4, 1]\n"
     ]
    }
   ],
   "source": [
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43c64492",
   "metadata": {},
   "source": [
    "### Time complexity for both is = O(n log n)\n",
    "Tim sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3b4f4a6f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "57cea2e6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7de0c15d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c7dacdaa",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "7bb6126e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f64343ee",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "edfc63c6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "73abe853",
   "metadata": {},
   "source": [
    "## Bubble sort"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75e54bc1",
   "metadata": {},
   "source": [
    "Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the intended order. It is called bubble sort because the movement of array elements is just like the movement of air bubbles in the water. Bubbles in water rise up to the surface; similarly, the array elements in bubble sort move to the end in each iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "044b85c4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "c2f36b92",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [4, 2, 5, 10, 1, 3]\n",
    "\n",
    "n = len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "9db5e514",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(n):\n",
    "    for j in range(n-1):\n",
    "#         Pick two consecutive elements.\n",
    "#         If they are NOT in correct order, swap them\n",
    "        if a[j] > a[j+1]:\n",
    "            a[j], a[j+1] = a[j+1], a[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "41a126dc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 10]\n"
     ]
    }
   ],
   "source": [
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1758b78",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "c545bc57",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 5\n"
     ]
    }
   ],
   "source": [
    "x = 5\n",
    "y = 2\n",
    "\n",
    "x,y = y,x\n",
    "\n",
    "print(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1bb7d3d1",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e9f3660d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "ff524fba",
   "metadata": {},
   "source": [
    "# Searching\n",
    "![](./searching.gif)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e58b8e96",
   "metadata": {},
   "source": [
    "### Linear Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "b02afd24",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [4,2,5,6,12,7,1,-1,90]\n",
    "key = 90\n",
    "\n",
    "# Check if key (5) is in the list(a) and report the index as well"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "ea8aa8e9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found at index 8\n"
     ]
    }
   ],
   "source": [
    "ans = -1\n",
    "\n",
    "for i in range(len(a)):\n",
    "    if a[i] == key:\n",
    "        ans = i\n",
    "        break\n",
    "        \n",
    "if ans == -1:\n",
    "    print(\"Not found\")\n",
    "else:\n",
    "    print(\"Found at index\", ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "da67e258",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Not found\n"
     ]
    }
   ],
   "source": [
    "ans = -1\n",
    "\n",
    "for i,num in enumerate(a):\n",
    "    if num == key:\n",
    "        ans = i\n",
    "        break\n",
    "\n",
    "if ans == -1:\n",
    "    print(\"Not found\")\n",
    "else:\n",
    "    print(\"Found at index\", ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d59ed0b",
   "metadata": {},
   "source": [
    "Time complexity - O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5083ec4e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1809aa8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "116430bc",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "3efe9ba5",
   "metadata": {},
   "source": [
    "## Binary Search"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bf17fea",
   "metadata": {},
   "source": [
    "##### Prerequisite\n",
    "- Array must be sorted\n",
    "\n",
    "\n",
    "##### Algorithm\n",
    "- Find the middle element and compare it with x.\n",
    "- If middle element is equal to x, end the search. You found the element.\n",
    "- If middle element is greater than x, search for x in left half.\n",
    "- If middle element is less than x, search for x in right half. \n",
    "- Repeat the above steps till you find x, or till you exhaust the array.\n",
    "\n",
    "##### Points to remember\n",
    "- Binary Search is Divide and Conquer technique. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "4fd64da9",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1, 5, 7, 10, 15, 20, 23]\n",
    "\n",
    "target = 20\n",
    "\n",
    "n = len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "fe3e53ef",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "ans = -1\n",
    "\n",
    "start = 0\n",
    "end = n - 1\n",
    "\n",
    "while start <= end:\n",
    "    mid = (start + end) // 2\n",
    "#     mid is an index\n",
    "    \n",
    "#     That I found the target number\n",
    "    if a[mid] == target:\n",
    "        ans = mid\n",
    "        break\n",
    "#     That the mid number is greater than target\n",
    "    elif a[mid] > target:\n",
    "#         Search in the left part\n",
    "        end = mid - 1\n",
    "#     That the mid number is less than target\n",
    "    else:\n",
    "#         Search in the right part\n",
    "        start = mid + 1\n",
    "    \n",
    "    \n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "173c140b",
   "metadata": {},
   "source": [
    "## Duplicate elements - lowerbound, upperbound"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "0ef8d975",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1,2,2,2,2,3,3,3,3,4,4]\n",
    "\n",
    "target = 3\n",
    "\n",
    "n = len(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "490fdefa",
   "metadata": {},
   "source": [
    "## lowerbound - index of the first occurence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "e3a42a2b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "ans = -1\n",
    "\n",
    "start = 0\n",
    "end = n - 1\n",
    "\n",
    "[1,2,2,2,2,3,3,3,3,4,4]\n",
    "\n",
    "while start <= end:\n",
    "    mid = (start + end) // 2\n",
    "    if a[mid] == target:\n",
    "        ans = mid\n",
    "#         break\n",
    "        end = mid - 1\n",
    "    elif a[mid] > target:\n",
    "        end = mid - 1\n",
    "    else:\n",
    "        start = mid + 1\n",
    "    \n",
    "    \n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e11fa44c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "69386839",
   "metadata": {},
   "source": [
    "## upperbound - index of the last occurence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "408de4f2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "ans = -1\n",
    "\n",
    "start = 0\n",
    "end = n - 1\n",
    "\n",
    "while start <= end:\n",
    "    mid = (start + end) // 2\n",
    "    if a[mid] == target:\n",
    "        ans = mid\n",
    "#         break\n",
    "        start = mid + 1\n",
    "    elif a[mid] > target:\n",
    "        end = mid - 1\n",
    "    else:\n",
    "        start = mid + 1\n",
    "    \n",
    "    \n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e73dd70d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9798847f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79dc804c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c402035",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4446c092",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "316b8c96",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "46a7e56a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "370447ec",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c2b40de",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}