Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d90483ba",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/ChandrashekharRobbi/GFG-DSA/blob/main/Sorting.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9f2fd93",
   "metadata": {
    "id": "f9f2fd93"
   },
   "source": [
    "# Sorting\n",
    "\n",
    "Make the below links workable??\n",
    "[Click Me](https://nbviewer.org/github/ChandrashekharRobbi/GFG-DSA/blob/main/Sorting.ipynb?flush_cache=true)\n",
    "\n",
    "* Some useful functions in python related to sorting\n",
    "\n",
    "1. [sort()](#1-.sort()) :- it works only for list , sorts in place\n",
    "2. [sorted()](#2-.sorted()) :- it works in any iterable , returns a new list with sorted items\n",
    "> Both use *TimSort* ( it is an hybrid of merge and insertion sort) and they are stable ( if both numbers are same then there original orders are reatained ).\n",
    "\n",
    "\n",
    "*Some Famous Sorting Techniques*\n",
    "\n",
    "1. [Bubble Sort](#Bubble-Sort)\n",
    "2. [Selection Sort](#Selection-Sort)\n",
    "3. [Insertion Sort](#Insertion-Sort)\n",
    "4. [Merge Sort](#Merge-Sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a841862d",
   "metadata": {
    "id": "a841862d"
   },
   "source": [
    "### 1 .sort()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5e03efd",
   "metadata": {
    "id": "d5e03efd"
   },
   "source": [
    "#### in ascending order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d0c8a10f",
   "metadata": {
    "id": "d0c8a10f"
   },
   "outputs": [],
   "source": [
    "l1 = [2,5,6,74,9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "fc430003",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "fc430003",
    "outputId": "1cc51865-6980-42a7-db03-61d557e5002b"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 5, 6, 74, 9]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e5506c05",
   "metadata": {
    "id": "e5506c05"
   },
   "outputs": [],
   "source": [
    "l1.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d3b0f83d",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "d3b0f83d",
    "outputId": "2bdfa005-4420-4025-dec0-326b483944d9"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 5, 6, 9, 74]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f93cf11a",
   "metadata": {
    "id": "f93cf11a"
   },
   "source": [
    "#### in descending order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "075fa64a",
   "metadata": {
    "id": "075fa64a"
   },
   "outputs": [],
   "source": [
    "l2 = [5,2,4,7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c925e6ed",
   "metadata": {
    "id": "c925e6ed"
   },
   "outputs": [],
   "source": [
    "l2.sort(reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e0429dc0",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "e0429dc0",
    "outputId": "b95d3b22-6a74-4a95-e2d5-71a2f742afba"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 5, 4, 2]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93bf6cad",
   "metadata": {
    "id": "93bf6cad"
   },
   "source": [
    "#### by using `key` or we can say by using functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "3e146015",
   "metadata": {
    "id": "3e146015"
   },
   "outputs": [],
   "source": [
    "l3 = [\"hello\" , \"hi\" , \"hey\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "8000ba2d",
   "metadata": {
    "id": "8000ba2d"
   },
   "outputs": [],
   "source": [
    "def myFunc(s):\n",
    "    return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ff828dd8",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "ff828dd8",
    "outputId": "65b66b6c-ef43-4548-85c0-28e7924dc8a7"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['hello', 'hi', 'hey']"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "4427f7a9",
   "metadata": {
    "id": "4427f7a9"
   },
   "outputs": [],
   "source": [
    "l3.sort(key=myFunc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "99d1548d",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "99d1548d",
    "outputId": "1db0148c-0b93-4c3b-9371-780fb533c229"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['hi', 'hey', 'hello']"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a52a2c4",
   "metadata": {
    "id": "9a52a2c4"
   },
   "source": [
    "#### use the `key` parameter and `reverse` parameter also"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d5de43e7",
   "metadata": {
    "id": "d5de43e7"
   },
   "outputs": [],
   "source": [
    "l4 = [\"Hello\" , \"Hi\" , \"Hey\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "5a132a15",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "5a132a15",
    "outputId": "efecd654-28d0-4895-a76e-b6b07ffc5641"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Hello', 'Hi', 'Hey']"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "69235969",
   "metadata": {
    "id": "69235969"
   },
   "outputs": [],
   "source": [
    "l4.sort(key=myFunc, reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "3e9a1139",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "3e9a1139",
    "outputId": "2dd5ffcc-ed22-4dcc-a2bc-a2cd5a2f0872"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Hello', 'Hey', 'Hi']"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4faf5740",
   "metadata": {
    "id": "4faf5740"
   },
   "source": [
    "### 2. .sorted()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "97359d6f",
   "metadata": {
    "id": "97359d6f"
   },
   "outputs": [],
   "source": [
    "l5 = [-10,2,-4,100]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "51b9adc3",
   "metadata": {
    "id": "51b9adc3"
   },
   "outputs": [],
   "source": [
    "ls = sorted(l5,key=abs,reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "fabbc97c",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "fabbc97c",
    "outputId": "4c0920cd-e33b-4582-ec01-b0be62d55c06"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[100, -10, -4, 2]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ls"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d75f5c4d",
   "metadata": {
    "id": "d75f5c4d"
   },
   "source": [
    "#### let's try with all iterable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "6a0ba613",
   "metadata": {
    "id": "6a0ba613"
   },
   "outputs": [],
   "source": [
    "t = (2,45,3,66) # tuple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "3f11174a",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "3f11174a",
    "outputId": "372fbc0d-4ce3-43a2-9033-0de071d6f42a"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 45, 66]\n"
     ]
    }
   ],
   "source": [
    "print(sorted(t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "b1acb0bf",
   "metadata": {
    "id": "b1acb0bf"
   },
   "outputs": [],
   "source": [
    "s = {\"hel\",\"oo\",\"how\",\"are\",\"you\"} # set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "828821cb",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "828821cb",
    "outputId": "8feff59f-74d9-4f16-9609-bc3fca5feeae"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['are', 'hel', 'how', 'oo', 'you']\n"
     ]
    }
   ],
   "source": [
    "print(sorted(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "74339822",
   "metadata": {
    "id": "74339822"
   },
   "outputs": [],
   "source": [
    "dic = {10:\"Hello\",1:\"How\"} # dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "e4c35395",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "e4c35395",
    "outputId": "60980e2d-bc34-4020-d2a3-075bd2657034"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 10]\n"
     ]
    }
   ],
   "source": [
    "print(sorted(dic))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "416180bf",
   "metadata": {
    "id": "416180bf"
   },
   "outputs": [],
   "source": [
    "ls = [(4,5),(3,2),(6,5)] # list of tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "52fcebed",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "52fcebed",
    "outputId": "d6b13355-a327-46e2-c484-8d52d7c9e0f5"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(3, 2), (4, 5), (6, 5)]\n"
     ]
    }
   ],
   "source": [
    "print(sorted(ls))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ed37550",
   "metadata": {
    "id": "1ed37550"
   },
   "source": [
    "## Bubble Sort\n",
    "\n",
    "\n",
    "* We have to push the greatest number to the right most side \n",
    "* It is in-place sorting algorithm\n",
    "* It is stable\n",
    "* It is mainly used in academices and not have many practical applications\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c444dc82",
   "metadata": {
    "id": "c444dc82"
   },
   "source": [
    "##### The below code takes O(n^2) time complexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "02e33f55",
   "metadata": {
    "id": "02e33f55"
   },
   "outputs": [],
   "source": [
    "def naiveBubbleSort(list):\n",
    "    n = len(list)\n",
    "    for i in range(n-1):\n",
    "        for j in range(n-i-1):\n",
    "            if list[j] > list[j+1]:\n",
    "                list[j], list[j+1] = list[j+1], list[j]\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "4d849f9a",
   "metadata": {
    "id": "4d849f9a"
   },
   "outputs": [],
   "source": [
    "l7 = [10,6,1,8,12]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "cfb67851",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "cfb67851",
    "outputId": "ac37b386-d290-4bd8-b2c7-e3aa4d3ebfb4"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 6, 8, 10, 12]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "naiveBubbleSort(l7)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b6af0db",
   "metadata": {
    "id": "5b6af0db"
   },
   "source": [
    "#### what if we pass sorted array ?\n",
    "\n",
    "\n",
    "Let's modify the code a little\n",
    "\n",
    "\n",
    "The below code takes O(n) time because it is only takes one pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "c07b3d2c",
   "metadata": {
    "id": "c07b3d2c"
   },
   "outputs": [],
   "source": [
    "def sortedBubbleSort(list):\n",
    "    n = len(list)\n",
    "    swapped = False\n",
    "    for i in range(n - 1):\n",
    "        for j in range(n - i - 1):\n",
    "            if list[j] > list[j+1]:\n",
    "                list[j] , list[j+1] = list[j+1] , list[j]\n",
    "                swapped = True\n",
    "        if swapped == False:\n",
    "            return \"The array is sorted\"\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "aee5858d",
   "metadata": {
    "id": "aee5858d"
   },
   "outputs": [],
   "source": [
    "l8 = [5,6,7,8,9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "afd9fb10",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 36
    },
    "id": "afd9fb10",
    "outputId": "965e4fc6-4edb-4cef-af8c-50681762f1b7"
   },
   "outputs": [
    {
     "data": {
      "application/vnd.google.colaboratory.intrinsic+json": {
       "type": "string"
      },
      "text/plain": [
       "'The array is sorted'"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortedBubbleSort(l8)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10fa15b8",
   "metadata": {
    "id": "10fa15b8"
   },
   "source": [
    "## Selection Sort\n",
    "\n",
    "* Does less memory writes compared to `quicksort` and `mergesort`\n",
    "* `CycleSort` does optimal memory writes\n",
    "* It is based on basic idea of `HeapSort`\n",
    "* It is not stable\n",
    "* It is in-place sorting algorithm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c694bab2",
   "metadata": {
    "id": "c694bab2"
   },
   "source": [
    "#### O(n^2) \n",
    "\n",
    "It gives same space and time complexity in all the cases ( worst, best and average)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "3af705b1",
   "metadata": {
    "id": "3af705b1"
   },
   "outputs": [],
   "source": [
    "def naiveSelectSort(list):\n",
    "    n = len(list)\n",
    "    for i in range(n-1):\n",
    "        min_index = i\n",
    "        for j in range(i+1,n):\n",
    "            if list[j] < list[min_index]:\n",
    "                min_index = j\n",
    "        list[min_index],list[i] = list[i], list[min_index]\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "d35b1d20",
   "metadata": {
    "id": "d35b1d20"
   },
   "outputs": [],
   "source": [
    "l9 = [12,15,13,16,4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "5c400f27",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "5c400f27",
    "outputId": "4fe5815d-cb0d-4bf3-b966-50c5f44b8a93"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 12, 13, 15, 16]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "naiveSelectSort(l9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9425c06d",
   "metadata": {
    "id": "9425c06d"
   },
   "source": [
    "## Insertion Sort\n",
    "\n",
    "\n",
    "* O(n^2) for worst case\n",
    "* O(n) for best case\n",
    "* It is in-place\n",
    "* It is stable\n",
    "* Used in practice for small arrays ( `Timsort` and `Inrosort` both uses `insertion sort` for small array inputs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "e6160d41",
   "metadata": {
    "id": "e6160d41"
   },
   "outputs": [],
   "source": [
    "def insertionSort(list):\n",
    "    for i in range(1,len(list)):\n",
    "        j = i\n",
    "        while list[j - 1] > list[j] and j > 0:\n",
    "            list[j] , list[j - 1] = list[j - 1] , list[j]\n",
    "            j -= 1\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "ee74a0fb",
   "metadata": {
    "id": "ee74a0fb"
   },
   "outputs": [],
   "source": [
    "l10 = [20,5,40,60,10,30]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "57551faf",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "57551faf",
    "outputId": "0bc850e2-bcd6-45e3-f656-360fca9fb47c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 10, 20, 30, 40, 60]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insertionSort(l10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2973fd4d",
   "metadata": {
    "id": "2973fd4d"
   },
   "source": [
    "#### merge two arrays and sort them"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "e9335be8",
   "metadata": {
    "id": "e9335be8"
   },
   "outputs": [],
   "source": [
    "def merge2sort(list1,list2):\n",
    "    l = list1 + list2\n",
    "    # let's apply insertion sort\n",
    "    for i in range(len(l)):\n",
    "        j = i\n",
    "        while l[j-1] > l[j] and j> 0:\n",
    "            l[j-1],l[j] = l[j] , l[j-1]\n",
    "            j -= 1\n",
    "    return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "5ede557d",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "5ede557d",
    "outputId": "b063381c-4bd6-4480-d78e-6d8908bc0117"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 6, 6, 10, 15, 20, 30]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge2sort([10,15,20],[5,6,6,30])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05c1e83f",
   "metadata": {
    "id": "05c1e83f"
   },
   "source": [
    "#### merge two sorted arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "ad2f031f",
   "metadata": {
    "id": "ad2f031f"
   },
   "outputs": [],
   "source": [
    "def merge2SortedArray(list1,list2):\n",
    "    res = []\n",
    "    m = len(list1)\n",
    "    n = len(list2)\n",
    "    i = 0\n",
    "    j = 0\n",
    "    while i<m and  j<n:\n",
    "        if list1[i] <list2[j]:\n",
    "            res.append(list1[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            res.append(list2[j])\n",
    "            j += 1\n",
    "    while i<m:\n",
    "        res.append(list1[i])\n",
    "        i += 1\n",
    "    while j<n:\n",
    "        res.append(list2[j])\n",
    "        j += 1\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "172e0b56",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "172e0b56",
    "outputId": "09655aae-486c-4caa-dc57-c8123f4fc859"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 6, 6, 10, 15, 30, 40]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge2SortedArray([10,15],[5,6,6,30,40])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c743a5e2",
   "metadata": {
    "id": "c743a5e2"
   },
   "source": [
    "#### Merge two sub arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "dc543c20",
   "metadata": {
    "id": "dc543c20"
   },
   "outputs": [],
   "source": [
    "def merge2SubArrays(a,low,mid,high):\n",
    "    l1 = a[low:mid + 1]\n",
    "    l2 = a[mid + 1:high +1]\n",
    "    a = len(l1)\n",
    "    b = len(l2)\n",
    "    i = 0\n",
    "    j = 0\n",
    "    res = []\n",
    "    while i<a and j<b:\n",
    "        if l1[i] < l2[j]:\n",
    "            res.append(l1[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            res.append(l2[j])\n",
    "            j += 1\n",
    "    while i<a:\n",
    "        res.append(l1[i])\n",
    "        i += 1\n",
    "    while j<b:\n",
    "        res.append(l2[j])\n",
    "        j += 1\n",
    "    return res\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "36ccb228",
   "metadata": {
    "id": "36ccb228"
   },
   "outputs": [],
   "source": [
    "a = [10,15,20,11,13]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "ec5a9521",
   "metadata": {
    "id": "ec5a9521"
   },
   "outputs": [],
   "source": [
    "a = [5,8,12,14,7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "fb95b062",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "fb95b062",
    "outputId": "7e1a168e-44b2-4b4d-9039-4cf66774ab29"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 7, 8, 12, 14]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge2SubArrays(a,0,3,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "e2971ef6",
   "metadata": {
    "id": "e2971ef6"
   },
   "outputs": [],
   "source": [
    "def merge(a,l,m,h):\n",
    "    left = a[l:m+1]\n",
    "    right = a[m+1:h+1]\n",
    "    i = j = 0\n",
    "    k = l\n",
    "    while i < len(left) and j < len(right):\n",
    "        if left[i] < right[j]:\n",
    "            a[k] = left[i]\n",
    "            k += 1\n",
    "            i += 1\n",
    "        else:\n",
    "            a[k] = right[j]\n",
    "            j += 1\n",
    "            k += 1\n",
    "    while i<len(left):\n",
    "        a[k] = left[i]\n",
    "        i += 1\n",
    "        k += 1\n",
    "    while j<len(right):\n",
    "        a[k] = right[j]\n",
    "        j += 1\n",
    "        k += 1\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "fe3030bd",
   "metadata": {
    "id": "fe3030bd"
   },
   "outputs": [],
   "source": [
    "arr = [5,10,30,40,1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "0de17ba4",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "0de17ba4",
    "outputId": "15cf7239-f784-4aaf-cd01-42fdc66eba8c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 5, 10, 30, 40]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge(arr,0,3,len(arr) - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06dd1b51",
   "metadata": {
    "id": "06dd1b51"
   },
   "source": [
    "## Merge Sort\n",
    "\n",
    "* Divide and conquer algorithm (Divide, Conquer and merge)\n",
    "* Stable Sorting Algortihm\n",
    "* It is not in-place sorting algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "3494e1db",
   "metadata": {
    "id": "3494e1db"
   },
   "outputs": [],
   "source": [
    "def mergeSort(list,l, r):\n",
    "    if r > l:\n",
    "        m = (l + r) // 2\n",
    "        mergeSort(list,l, m )\n",
    "        mergeSort(list,m + 1, r)\n",
    "        merge(list,l,m,r)\n",
    "    print(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "e0cb0508",
   "metadata": {
    "id": "e0cb0508"
   },
   "outputs": [],
   "source": [
    "arr = [10, 5, 30, 15, 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "719f16a7",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "719f16a7",
    "outputId": "91759fbe-c1f4-4d98-de89-bbd33136441e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 5, 30, 15, 7]\n",
      "[10, 5, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 7, 15]\n",
      "[5, 7, 10, 15, 30]\n"
     ]
    }
   ],
   "source": [
    "mergeSort(arr,0,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "32ed6af6",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "32ed6af6",
    "outputId": "c342c736-3769-4989-fffc-e8d8c3068221"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 7, 10, 15, 30]\n"
     ]
    }
   ],
   "source": [
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "3079dedf",
   "metadata": {
    "id": "3079dedf"
   },
   "outputs": [],
   "source": [
    "def mergeSort(list,l, r):\n",
    "    if r > l:\n",
    "        m = (l + r) // 2\n",
    "        mergeSort(list,l, m )\n",
    "        mergeSort(list,m + 1, r)\n",
    "        left = list[l:m+1]\n",
    "        right = list[m+1:r+1]\n",
    "        i = j = 0\n",
    "        k = l\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] < right[j]:\n",
    "                list[k] = left[i]\n",
    "                k += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                list[k] = right[j]\n",
    "                j += 1\n",
    "                k += 1\n",
    "        while i<len(left):\n",
    "            list[k] = left[i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "        while j<len(right):\n",
    "            list[k] = right[j]\n",
    "            j += 1\n",
    "            k += 1\n",
    "    print(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "7a03f559",
   "metadata": {
    "id": "7a03f559"
   },
   "outputs": [],
   "source": [
    "arr = [10, 5, 30, 15, 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "20b1878b",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "20b1878b",
    "outputId": "2e93f284-95e3-4bd7-812b-d436bcb4801a"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 5, 30, 15, 7]\n",
      "[10, 5, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 15, 7]\n",
      "[5, 10, 30, 7, 15]\n",
      "[5, 7, 10, 15, 30]\n"
     ]
    }
   ],
   "source": [
    "mergeSort(arr,0,4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7886a033",
   "metadata": {
    "id": "7886a033"
   },
   "source": [
    "## Union of Two Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23a3f7e5",
   "metadata": {
    "id": "23a3f7e5"
   },
   "source": [
    "#### naive approach"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "1db21995",
   "metadata": {
    "id": "1db21995"
   },
   "outputs": [],
   "source": [
    "a = [3,5,8]\n",
    "b = [2,8,9,10,15]\n",
    "\n",
    "c = a + b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "73432abc",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "73432abc",
    "outputId": "51b7e742-7ad8-469d-9c37-580981c1eb68"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 5, 8, 2, 8, 9, 10, 15]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "7d23947a",
   "metadata": {
    "id": "7d23947a"
   },
   "outputs": [],
   "source": [
    "def unionOfSortedArray(list,l,r):\n",
    "    if r > l:\n",
    "        m = (l + r) // 2\n",
    "        unionOfSortedArray(list,l,m)\n",
    "        unionOfSortedArray(list,m+1,r)\n",
    "        left = list[l:m+1]\n",
    "        right = list[m+1:r+1]\n",
    "        i = j = 0\n",
    "        k = l\n",
    "        while i < len(left) and j< len(right):\n",
    "            if left[i] < right[j]:\n",
    "                list[k] = left[i]\n",
    "                i += 1\n",
    "                k += 1\n",
    "            else:\n",
    "                list[k] = right[j]\n",
    "                j += 1\n",
    "                k += 1\n",
    "        while i < len(left):\n",
    "            list[k] = left[i]\n",
    "            k += 1\n",
    "            i += 1\n",
    "        while j < len(right):\n",
    "            list[k] = right[j]\n",
    "            k += 1\n",
    "            j += 1\n",
    "    print(list)\n",
    "    # print distinct elements\n",
    "    for i in range(0,len(list)):\n",
    "        if (i == 0 or list[i] != list[i - 1]):\n",
    "            print(list[i],end=\" \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "65e9c032",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "65e9c032",
    "outputId": "3fb80a45-ba45-4c6f-d313-b27115ff9387"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 5, 8, 2, 8, 9, 10, 15]\n",
      "3 5 8 2 8 9 10 15 [3, 5, 8, 2, 8, 9, 10, 15]\n",
      "3 5 8 2 8 9 10 15 [3, 5, 8, 2, 8, 9, 10, 15]\n",
      "3 5 8 2 8 9 10 15 [3, 5, 8, 2, 8, 9, 10, 15]\n",
      "3 5 8 2 8 9 10 15 [3, 5, 8, 2, 8, 9, 10, 15]\n",
      "3 5 8 2 8 9 10 15 [3, 5, 2, 8, 8, 9, 10, 15]\n",
      "3 5 2 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 [2, 3, 5, 8, 8, 9, 10, 15]\n",
      "2 3 5 8 9 10 15 "
     ]
    }
   ],
   "source": [
    "unionOfSortedArray(c,0,len(c)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e9a7112",
   "metadata": {
    "id": "3e9a7112"
   },
   "source": [
    "#### Efficient solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "c61231f6",
   "metadata": {
    "id": "c61231f6"
   },
   "outputs": [],
   "source": [
    "def EfficientUnionOfTwoSortedArray(a,b):\n",
    "    i = j = 0\n",
    "    while i < len(a) and j<len(b):\n",
    "        if i>0 and a[i] == a[i - 1]:\n",
    "            i += 1\n",
    "        elif j>0 and b[j] == b[j - 1]:\n",
    "            j += 1\n",
    "        elif a[i] < b[j]:\n",
    "            print(a[i],end=\" \")\n",
    "            i += 1\n",
    "        elif a[i] > b[j]:\n",
    "            print(b[j],end=\" \")\n",
    "            j += 1\n",
    "        else:\n",
    "            a[i] == b[j]\n",
    "            print(a[i],end=\" \")\n",
    "            i += 1\n",
    "            j += 1\n",
    "    while i<len(a):\n",
    "        print(a[i], end=\" \")\n",
    "        i += 1\n",
    "    while j<len(b):\n",
    "        print(b[j],end=\" \")\n",
    "        j += 1\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "adda0a94",
   "metadata": {
    "id": "adda0a94"
   },
   "outputs": [],
   "source": [
    "a = [3,5,8]\n",
    "b = [2,8,9,10,15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "0b6a3e48",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "0b6a3e48",
    "outputId": "5b285a3f-6f38-4aaf-9f92-779f78df5544"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3 5 8 9 10 15 "
     ]
    }
   ],
   "source": [
    "EfficientUnionOfTwoSortedArray(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1e9bbb6",
   "metadata": {
    "id": "c1e9bbb6"
   },
   "source": [
    "#### intersection of two sorted arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "Xioso3C-8QEC",
   "metadata": {
    "id": "Xioso3C-8QEC"
   },
   "outputs": [],
   "source": [
    "def intersectionTwoSorted(a,b,m,n):\n",
    "    for i in range(m):\n",
    "        if i>0 and a[i-1] == a[i]:\n",
    "            continue\n",
    "        for j in range(n):\n",
    "            if a[i] == b[j]:\n",
    "                print(a[i],end=\" \")\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "HFVf5_PW8kZR",
   "metadata": {
    "id": "HFVf5_PW8kZR"
   },
   "outputs": [],
   "source": [
    "a = [1,20,20,40,60]\n",
    "b = [2,20,20]\n",
    "m = len(a)\n",
    "n = len(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "MJBbu-Yt82Do",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "MJBbu-Yt82Do",
    "outputId": "20424180-80d3-4c72-bd4d-ce411e06278c"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20 "
     ]
    }
   ],
   "source": [
    "intersectionTwoSorted(a,b,m,n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ODR9cIJW85LP",
   "metadata": {
    "id": "ODR9cIJW85LP"
   },
   "source": [
    "#### count inversion in array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "FG-ydyoA9IWB",
   "metadata": {
    "id": "FG-ydyoA9IWB"
   },
   "outputs": [],
   "source": [
    "def countInversion(list,l,r):\n",
    "  def merge(list,l,m,r):\n",
    "    left = list[l:m+1]\n",
    "    right = list[m+1:r+1]\n",
    "    i = j = 0\n",
    "    k = l\n",
    "    res = 0\n",
    "    while i<len(left) and j<len(right):\n",
    "      if left[i] <= right[j]:\n",
    "        list[k] = left[i]\n",
    "        i += 1\n",
    "      else:\n",
    "        list[k] = right[j]\n",
    "        res += len(left) - i\n",
    "        j += 1\n",
    "      k += 1\n",
    "    while i<len(left):\n",
    "      list[k] = left[i]\n",
    "      i += 1\n",
    "      k += 1\n",
    "    while j<len(right):\n",
    "      list[k] = right[j]\n",
    "      j += 1\n",
    "      k += 1\n",
    "    return res\n",
    "\n",
    "  res = 0\n",
    "  if r>l:\n",
    "    m = (l + r)//2\n",
    "    res += countInversion(list,l,m)\n",
    "    res += countInversion(list,m+1,r)\n",
    "    res += merge(list,l,m,r)\n",
    "  print(list)\n",
    "  return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "3GYFmXKrjCXh",
   "metadata": {
    "id": "3GYFmXKrjCXh"
   },
   "outputs": [],
   "source": [
    "arr = [2,1,3,6,5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "hErICH9vjIw8",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "hErICH9vjIw8",
    "outputId": "649753e3-3b96-4251-da31-f2ca42af9354"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 1, 3, 6, 5]\n",
      "[2, 1, 3, 6, 5]\n",
      "[1, 2, 3, 6, 5]\n",
      "[1, 2, 3, 6, 5]\n",
      "[1, 2, 3, 6, 5]\n",
      "[1, 2, 3, 6, 5]\n",
      "[1, 2, 3, 6, 5]\n",
      "[1, 2, 3, 5, 6]\n",
      "[1, 2, 3, 5, 6]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countInversion(arr,0,len(arr)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "NoBLMqS1jM9z",
   "metadata": {
    "id": "NoBLMqS1jM9z"
   },
   "source": [
    "#### Partition a Given Array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "Y2tKCW7vjYmf",
   "metadata": {
    "id": "Y2tKCW7vjYmf"
   },
   "outputs": [],
   "source": [
    "arr = [3,8,6,12,10,7,4]\n",
    "p = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "mA8dwP9ljhWL",
   "metadata": {
    "id": "mA8dwP9ljhWL"
   },
   "outputs": [],
   "source": [
    "def PartitionArray(arr,a):\n",
    "  n = len(arr)\n",
    "  arr[a],arr[n-1] = arr[n-1],arr[a]\n",
    "  temp = []\n",
    "  for x in arr:\n",
    "    if x<=arr[n-1]:\n",
    "      temp.append(x)\n",
    "  for x in arr:\n",
    "    if x>arr[n-1]:\n",
    "      temp.append(x)\n",
    "  for i in range(len(arr)):\n",
    "    arr[i] = temp[i]\n",
    "\n",
    "  return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "26ANSPHokv71",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "26ANSPHokv71",
    "outputId": "9831f4dd-35ec-4475-8ad7-c750f305a713"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 6, 4, 7, 8, 12, 10]"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PartitionArray(arr,p)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exT5stwvky5E",
   "metadata": {
    "id": "exT5stwvky5E"
   },
   "source": [
    "#### Hoare's Partition\n",
    "\n",
    "\n",
    "It is not stable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "uArdpLCeDxws",
   "metadata": {
    "id": "uArdpLCeDxws"
   },
   "outputs": [],
   "source": [
    "def HoarePartition(arr,l,h):\n",
    "  pivot = arr[l]\n",
    "  i = l - 1\n",
    "  j = h + 1\n",
    "  while True:\n",
    "    i += 1\n",
    "    while arr[i] < pivot:\n",
    "      i += 1\n",
    "    j -= 1\n",
    "    while arr[j] > pivot:\n",
    "      j -= 1\n",
    "    if i>= j:\n",
    "      return j, arr\n",
    "    arr[i], arr[j] = arr[j], arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "bukxVF5uDzBS",
   "metadata": {
    "id": "bukxVF5uDzBS"
   },
   "outputs": [],
   "source": [
    "arr = [5,3,8,4,2,7,1,10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "dimcVgL4GxuH",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "dimcVgL4GxuH",
    "outputId": "15d61db4-762a-43f4-af2f-fe0fbad9839a"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, [1, 3, 2, 4, 8, 7, 5, 10])"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HoarePartition(arr,0,len(arr)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "e7wYaKkdHmH7",
   "metadata": {
    "id": "e7wYaKkdHmH7"
   },
   "outputs": [],
   "source": [
    "def LomutoPartition(arr,l,h):\n",
    "  pivot = arr[h]\n",
    "  i = l - 1\n",
    "  for j in range(l,h):\n",
    "    if arr[j] < pivot:\n",
    "      i += 1\n",
    "      arr[i] , arr[j] = arr[j], arr[i]\n",
    "  i += 1\n",
    "  arr[i] , arr[h] = arr[h] , arr[i]\n",
    "  return i, arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "L3BoIidJOJ2R",
   "metadata": {
    "id": "L3BoIidJOJ2R"
   },
   "outputs": [],
   "source": [
    "arr = [10,80,30,90,40,50,70]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "WPFec8WXOGwx",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "WPFec8WXOGwx",
    "outputId": "1ac12e24-d6b0-4a4c-bb09-af7dd4455dcf"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, [10, 30, 40, 50, 70, 90, 80])"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LomutoPartition(arr,0,len(arr)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "fEBA5yCSOxJb",
   "metadata": {
    "id": "fEBA5yCSOxJb"
   },
   "outputs": [],
   "source": [
    "arr = [10,80,30,90,40,50,70]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "6OQiWK0pOTY2",
   "metadata": {
    "id": "6OQiWK0pOTY2"
   },
   "outputs": [],
   "source": [
    "def LomutoPartition1(arr,l,h):\n",
    "  pivot = arr[h]\n",
    "  i = l\n",
    "  for j in range(l,h):\n",
    "    if arr[j] < pivot:\n",
    "      arr[i] , arr[j] = arr[j], arr[i]\n",
    "      i += 1\n",
    "  i += 1\n",
    "  arr[i] , arr[h] = arr[h] , arr[i]\n",
    "  return i, arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "QqApsEgQOriX",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "QqApsEgQOriX",
    "outputId": "5055c789-4445-4233-f4dc-17a140e5dd70"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, [10, 30, 40, 50, 80, 70, 90])"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LomutoPartition1(arr,0,len(arr)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "qy0OQoHHO2OP",
   "metadata": {
    "id": "qy0OQoHHO2OP"
   },
   "source": [
    "## Quick Sort\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "*   Divide and Conquer Method\n",
    "*   Worst Case Time - O(n^2)\n",
    "*   It is in-place\n",
    "* Cache Friendly\n",
    "* Partiton is the key function\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "M08LAUIBPxtE",
   "metadata": {
    "id": "M08LAUIBPxtE"
   },
   "source": [
    "#### Using Hoare's Partition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "V12R7MQqSobr",
   "metadata": {
    "id": "V12R7MQqSobr"
   },
   "outputs": [],
   "source": [
    "def QuickSortHoarePartition(arr,l,h):\n",
    "  def HoarePartition(arr,l,h):\n",
    "    pivot = arr[l]\n",
    "    i = l -1\n",
    "    j = h + 1\n",
    "    while True:\n",
    "      i += 1\n",
    "      while arr[i]<pivot:\n",
    "        i += 1\n",
    "      j -= 1\n",
    "      while arr[j] > pivot:\n",
    "        j -= 1\n",
    "      if i >= j:\n",
    "        return j\n",
    "      arr[i], arr[j] = arr[j] , arr[i]\n",
    "  if l < h:\n",
    "    p = HoarePartition(arr,l,h)\n",
    "    QuickSortHoarePartition(arr,l,p)\n",
    "    QuickSortHoarePartition(arr,p+1,h)\n",
    "  return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "F1uCfaHITvxy",
   "metadata": {
    "id": "F1uCfaHITvxy"
   },
   "outputs": [],
   "source": [
    "arr = [5,3,8,4,2,7,1,10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "HLEWIm9zSsAd",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "HLEWIm9zSsAd",
    "outputId": "5bb27b74-154a-4d8c-ede3-e201808f8748"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 7, 8, 10]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "QuickSortHoarePartition(arr,0,len(arr)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "ecfsIPYTTbh1",
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "ecfsIPYTTbh1",
    "outputId": "7be3b347-5512-4942-9990-c5809e78e483"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 7, 8, 10]\n"
     ]
    }
   ],
   "source": [
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "5jCJUSVqTyit",
   "metadata": {
    "id": "5jCJUSVqTyit"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "include_colab_link": true,
   "provenance": []
  },
  "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}