15_June_2024_SortingAssignmnet.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "49f65158",
   "metadata": {},
   "source": [
    "## Sorting Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8688061b",
   "metadata": {},
   "source": [
    "### Problem 1.Given an array of n numbers, give an algorithm which gives the element appearing maximum number of times?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55133fb1",
   "metadata": {},
   "source": [
    "### Ans 1)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array and create a new unique element array.\n",
    "- Initialise count and maxEle variables to store the final result.\n",
    "- Iterate through each element of the new Array to find their count in original array.\n",
    "- If the count of any element is greater than initialized count element then update it.\n",
    "- Return the max count element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "6daba6e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxFreqEle(arr):\n",
    "    ## create a new unique element array\n",
    "    newArr = set(arr)\n",
    "    \n",
    "    ## initialise count and maxEle to store the final result\n",
    "    count , maxEle = 0 , arr[0]\n",
    "    \n",
    "    ## iterate through newArr to find their count in original array\n",
    "    for ele in newArr:\n",
    "        newCount = arr.count(ele)\n",
    "        if newCount > count:\n",
    "            count = newCount\n",
    "            maxEle = ele\n",
    "            \n",
    "    return maxEle\n",
    "\n",
    "## Time Complexity : O(n)  ; linearly traversing through array\n",
    "## Space Complexity : O(n) ; creating extra unique element array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "4ac84c24",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [1, 2, 10, 5, 10, 10, 2, 1, 11, 12, 10]\n",
      "Max appearing element : 10\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "arr = [1,2,10,5,10,10,2,1,11,12,10]\n",
    "\n",
    "## calling the function\n",
    "output = maxFreqEle(arr)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr}\\nMax appearing element : {output}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00148f81",
   "metadata": {},
   "source": [
    "### Problem 2 : We are given a list of n-1 integers and these integers are in the range of 1 to n . There are no duplicates in the list. One of the integers is missing in the list. Give an algorithm to find that element Ex: [1,2,4,6,3,7,8] 5 is the missing num."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e61857ae",
   "metadata": {},
   "source": [
    "### Ans 2)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array and sort it using bubble sort.\n",
    "- Traverse through the sorted array.\n",
    "- Check weather after adding one into current element ,is it equal to next element or not.\n",
    "- If not then return the current plus one element as missing element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "570c9c72",
   "metadata": {},
   "outputs": [],
   "source": [
    "def BubbleSort(arr):\n",
    "    for i in range(len(arr)-1):\n",
    "        for j in range(len(arr)-1-i):\n",
    "            if arr[j] > arr[j+1]:\n",
    "                arr[j] , arr[j+1] = arr[j+1] , arr[j]\n",
    "\n",
    "def missingEle(arr):\n",
    "    ## call the bubble sort to sort the arr\n",
    "    BubbleSort(arr)\n",
    "    \n",
    "    ## find the missing element in the sorted array\n",
    "    for i in range(len(arr)-1):\n",
    "        if arr[i]+1 != arr[i+1]:\n",
    "            return f\"Missing element is : {arr[i]+1}\"\n",
    "        \n",
    "        \n",
    "## Time Complexity : O(n^2)  ; Because of bubble sorting\n",
    "## Space Complexity : O(1)   ; No extra space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "75bbe990",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [1, 2, 3, 4, 5, 7, 8, 9, 10]\n",
      "Missing element is : 6\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "arr1 = [10,1,4,2,5,3,7,9,8]\n",
    "\n",
    "## calling the function\n",
    "output1 = missingEle(arr1)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr1}\\n{output1}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "144cdc74",
   "metadata": {},
   "source": [
    "### Problem 3 : Given an array of n positive numbers. All numbers occurs even number of times except 1 which occurs odd number of times. Find that number in O(n) time and O(1) space. Ex: [1,2,3,2,3,1,3]. 3 is repeats odd times."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f1abdb9",
   "metadata": {},
   "source": [
    "### Ans 3)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array.\n",
    "- Traverse through each element of the array.\n",
    "- find the count of each element.\n",
    "- if the count of any element is odd return that element as the Element that occur odd number of time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "57f2af04",
   "metadata": {},
   "outputs": [],
   "source": [
    "def OddCountNum(arr):\n",
    "    ## traverse through each element of arr and find the count of each element\n",
    "    ## if the count of any element is odd return that element\n",
    "    \n",
    "    for ele in arr:\n",
    "        if (arr.count(ele))%2 != 0:\n",
    "            return ele"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "538b5224",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [1, 2, 3, 2, 3, 1, 3]\n",
      "Element that occur odd number of time : 3\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "arr3 = [1,2,3,2,3,1,3]\n",
    "\n",
    "## calling the function\n",
    "output3 = OddCountNum(arr3)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr3}\\nElement that occur odd number of time : {output3}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63898f72",
   "metadata": {},
   "source": [
    "### Problem 4 : Given an array of n elements. Find two elements in the array such that their sum is equal to given element K."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b80fa946",
   "metadata": {},
   "source": [
    "### Ans 4)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array and k.\n",
    "- Traverse through each element of the array using outer loop.\n",
    "- Add each element of the array with each other element using inner loop.\n",
    "- If the addition is equal to given value of k then returns that pair of elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "c3c68300",
   "metadata": {},
   "outputs": [],
   "source": [
    "def PairSum(arr,k):\n",
    "    n = len(arr)\n",
    "    for i in range(n-1):\n",
    "        for j in range(i+1, n):\n",
    "            if arr[i]+arr[j] == k:\n",
    "                return (arr[i],arr[j])\n",
    "            \n",
    "    return -1\n",
    "\n",
    "## Time Complexity  : O(n^2)\n",
    "## Space Complexity : O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "524de4cf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [6, 5, 9, 3, 7]\n",
      "Pair of elements which sum equals to: 8  : (5, 3)\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "arr4 = [6,5,9,3,7]\n",
    "k = 8\n",
    "\n",
    "## calling the function\n",
    "output4 = PairSum(arr4, k)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr4}\\nPair of elements which sum equals to: {k}  : {output4}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43784bfa",
   "metadata": {},
   "source": [
    "### Problem 5 : Given an array of both positive and negative numbers, find two numbers such that their sum is closest to 0. Ex: [ 1 ,60 ,-10, 70, -80,85]. Ans : -80,85."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8704319",
   "metadata": {},
   "source": [
    "### Ans 5)\n",
    "- Appraoch : \n",
    "- We know the range...\n",
    "- ...-5,-4,-3,-2,-1,(0),+1,+2,+3,+4,+5.......\n",
    "- if i ask between -3 and +2 which is one is more closer to zero.\n",
    "- Ans : +2 , how? , to reach to zero using +2 i have to take 2 steps, for -3 i have to take 3 steps.\n",
    "- So choose that pair which summation is closet to zero.(which takes less step to reach to zero.)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array.\n",
    "- Traverse through each element of the array using outer loop.\n",
    "- Add each element of the array with each other element using inner loop.\n",
    "- If the addition is equal to zero then returns that pair of elements.\n",
    "- If absolute addition of elements is less than initialised sum then update the sum and array elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "dc76d12f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def NearZeroPari(arr):\n",
    "    EleSum = 999999\n",
    "    newSum = 0\n",
    "    pair = []\n",
    "    newPair = []\n",
    "    n = len(arr)\n",
    "    \n",
    "    for i in range(n-1):\n",
    "        for j in range(i+1, n):\n",
    "            newSum = arr[i]+arr[j]\n",
    "            newPair = [arr[i],arr[j]]\n",
    "            \n",
    "            if newSum == 0:\n",
    "                return newPair\n",
    "            elif abs(newSum) < EleSum :\n",
    "                EleSum = abs(newSum)\n",
    "                pair = newPair.copy()\n",
    "                \n",
    "    return pair      \n",
    "\n",
    "\n",
    "## Time Complexity  : O(n^2)\n",
    "## Space Complexity : O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "34970e17",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [1, 60, -10, 70, -80, 90]\n",
      "Pair of elements which sum is closest to zero : [1, -10]\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "arr5 = [1,60,-10,70,-80,90]\n",
    "\n",
    "\n",
    "## calling the function\n",
    "output5 = NearZeroPari(arr5)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr5}\\nPair of elements which sum is closest to zero : {output5}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f14b549d",
   "metadata": {},
   "source": [
    "### Problem 6 : Given an array of n elements . Find three elements such that their sum is equal to the given number."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2afa7f7f",
   "metadata": {},
   "source": [
    "### Ans 6)\n",
    "- Approach : \n",
    "1. Find the three elements using 3 nested loops.    TC : (n^3)\n",
    "2. First sort the array then apply the logic.       TC : O(n^2)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array.\n",
    "- Sort the array using Bubble Sort.\n",
    "- Take two pointers left and right.\n",
    "- Find the sum by adding left and right value.\n",
    "- find the diff between given sum value and calculated sum.\n",
    "- Search this diff in given array using Binary search.\n",
    "- If element found return left, right and diff values as three elements.\n",
    "- Else return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "53e420d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def BubbleSort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n-1):\n",
    "        for j in range(n-1-i):\n",
    "            if arr[j] > arr[j+1]:\n",
    "                arr[j] , arr[j+1] = arr[j+1] , arr[j]\n",
    "\n",
    "\n",
    "def BinarySearch(arr,left, right, ele):\n",
    "    while left <= right :\n",
    "        mid = (right+left)//2\n",
    "        \n",
    "        if arr[mid] == ele:\n",
    "            return True\n",
    "        elif ele > arr[mid]:\n",
    "            left = mid+1\n",
    "        else:\n",
    "            right = mid-1       \n",
    "    return False\n",
    "        \n",
    "    \n",
    "\n",
    "def ThreeSum(arr,k):\n",
    "    ## sort the array\n",
    "    BubbleSort(arr)\n",
    "    \n",
    "    ## \n",
    "    left , right = 0 , len(arr)-1\n",
    "    \n",
    "    while left < right:\n",
    "        eleSum = arr[left] + arr[right]\n",
    "        diff = k - eleSum\n",
    "        \n",
    "        ## search diff in array using binary search\n",
    "        output = BinarySearch(arr,left+1, right-1, diff)\n",
    "        \n",
    "        ## comparison\n",
    "        if output:\n",
    "            return (arr[left], arr[right], diff)\n",
    "        else:\n",
    "            if eleSum < k :\n",
    "                left+=1\n",
    "            else:\n",
    "                right-=1\n",
    "                \n",
    "    return -1\n",
    "        \n",
    "    \n",
    "    \n",
    "## Time complexity : O(n^2)\n",
    "## Space Complexity : O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9ba9f84b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [1, 2, 3, 4, 5, 7]\n",
      "Triplet : (3, 7, 5)\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "#arr7 = [3, 1, 4, 6, 5]\n",
    "arr6 = [3,7,5,2,1,4]\n",
    "k = 15\n",
    "\n",
    "## calling the function\n",
    "output6 = ThreeSum(arr6,k)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr6}\\nTriplet : {output6}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbd0a2fd",
   "metadata": {},
   "source": [
    "### Problem 7 : Given an array of n elements . Find three elements i, j, k in the array such that : i * i + j * j = k*k."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8ac8108",
   "metadata": {},
   "source": [
    "### Ans 7)\n",
    "- Approach : \n",
    "1. Find the Triplets using 3 nested loops.    TC : (n^3)\n",
    "2. First sort the array then apply the logic. TC : O(n^2)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array.\n",
    "- Sort the array using Bubble Sort.\n",
    "- Take three pointers i,j and k and check whether arr[i]^2 + arr[j]^2 = arr[k]^2 or not.\n",
    "- If the addition is equal then return the triplet.\n",
    "- Else return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "b736a89e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def BubbleSort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n-1):\n",
    "        for j in range(n-1-i):\n",
    "            if arr[j] > arr[j+1]:\n",
    "                arr[j] , arr[j+1] = arr[j+1] , arr[j]\n",
    "\n",
    "\n",
    "def PythagoTriplet(arr):\n",
    "    ## sort the given array\n",
    "    BubbleSort(arr)\n",
    "    \n",
    "    ## traverse through array using three pointers\n",
    "    for i in range(len(arr)-2):\n",
    "        j = i+1\n",
    "        k = i+2\n",
    "        \n",
    "        # after sorting array will be like .... arr[i]<arr[j]<arr[k]\n",
    "        x = arr[i] * arr[i]\n",
    "        y = arr[j] * arr[j]\n",
    "        z = arr[k] * arr[k]\n",
    "        \n",
    "        if z == x+y :\n",
    "            return (arr[i],arr[j],arr[k])\n",
    "        \n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "0ca79434",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [1, 4, 5, 6, 8, 10]\n",
      "Pythogorean Triplet : (6, 8, 10)\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "#arr7 = [3, 1, 4, 6, 5]\n",
    "arr7 = [8, 1, 10,4, 6, 5]\n",
    "\n",
    "\n",
    "## calling the function\n",
    "output7 = PythagoTriplet(arr7)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr7}\\nPythogorean Triplet : {output7}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef7a010d",
   "metadata": {},
   "source": [
    "### Problem 8 : An element is a majority if it appears more than n/2 times. Give an algorithm takes an array of n element as argument and identifies a majority (if it exists)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6cc70fe",
   "metadata": {},
   "source": [
    "### Ans 8)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array.\n",
    "- Traverse through each element of the array.\n",
    "- Count the frequency of each element in the array.\n",
    "- If its count more than n/2 then return that element.\n",
    "- If there is no such element which count is more than n/2 then return -1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "d16ba7ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def MajorityEle(arr):\n",
    "    n = len(arr)\n",
    "    majorCount = n//2\n",
    "    \n",
    "    for ele in arr:\n",
    "        if arr.count(ele) > majorCount:\n",
    "            return ele\n",
    "        \n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "e69dec8f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [3, 4, 2, 4, 2, 4, 4]\n",
      " 4\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "arr6 = [3, 4, 2, 4, 2, 4,4]\n",
    "\n",
    "\n",
    "## calling the function\n",
    "output6 = MajorityEle(arr6)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr6}\\n {output6}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7dfeed45",
   "metadata": {},
   "source": [
    "### Problem 9 : Given n × n matrix, and in each row all 1’s are followed by 0’s. Find the row with the maximum number of 0’s."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6bfa54f",
   "metadata": {},
   "source": [
    "### Ans 8)\n",
    "\n",
    "#### Steps :\n",
    "- Take an array.\n",
    "- Initialize variables count and row\n",
    "- Traverse through each row of the matrix.\n",
    "- Count the frequency of zeros in each row.\n",
    "- Update the count and row if there is high count then previous one.\n",
    "- Return the row."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3023d132",
   "metadata": {},
   "outputs": [],
   "source": [
    "def MatZeroCount(mat):\n",
    "    ## variable initialization\n",
    "    count , row = 0 ,0\n",
    "    \n",
    "    ## traverse through each row of the matrix to find count of zeros\n",
    "    for i in range(len(mat)):\n",
    "        newcount = mat[i].count(0)\n",
    "        \n",
    "        if newcount > count:\n",
    "            count = newcount\n",
    "            row = i\n",
    "            \n",
    "    return row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "210e85dc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [[0, 1, 1], [0, 0, 1], [0, 1, 1]]\n",
      "Row with max zeros : 1\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "arr9 = [[0,1,1],[0,0,1],[0,1,1]]\n",
    "\n",
    "\n",
    "## calling the function\n",
    "output9 = MatZeroCount(arr9)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Input array : {arr9}\\nRow with max zeros : {output9}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abbce384",
   "metadata": {},
   "source": [
    "### Problem 10 : Sort an array of 0’s, 1’s and 2’s [or R’s, G’s and B’s]: Given an array A[] consisting of 0’s, 1’s and 2’s, give an algorithm for sorting A[].The algorithm should put all 0’s first, then all 1’s and finally all 2’s at the end. Example Input = {0,1,1,0,1,2,1,2,0,0,0,1}, Output = {0,0,0,0,0,1,1,1,1,1,2,2}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfc82ff8",
   "metadata": {},
   "source": [
    "### Ans 10)\n",
    "\n",
    "- Approach : \n",
    "- First write a function to sort all zeros in left side and all numbers greater than zero in right side.\n",
    "- Then from the exact position where the number greater than zero starts, sort them in right side.\n",
    "\n",
    "#### Steps :\n",
    "1. Sort zeros and ones first.\n",
    "- - Initialize two pointers left and right with zero and n-1 respectively.\n",
    "- - If left value is equals to zero then update the left pointer untill we get a value greater than zero.\n",
    "- - Then we stop and search from right to left, when value is greater than zero then continously increase the pointer untill we get the zero value.\n",
    "- - Now wherever the pointers are stopped we swap those values and update left and right pointers accordingly.\n",
    "\n",
    "2. Sort ones and twos.\n",
    "- - After sorting all ones in left side, now start sorting all remaining values.\n",
    "- - Consider the left pointer value that you stopped in sorting zeros and ones. And right pointer as last index value.\n",
    "- - Start searching 1 from left and 2 from right side.\n",
    "- - Increase the left pointer until you get the 2 and decrease the right pointer untill you get the 1.\n",
    "- - Then swap them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "4133a31b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def SortZeroOne(arr):\n",
    "   \n",
    "    n = len(arr)\n",
    "    left = 0\n",
    "    right = n-1\n",
    "    \n",
    "    while left < right:\n",
    "        while arr[left] == 0 and (left < right):\n",
    "            left += 1\n",
    "            \n",
    "        \n",
    "        while arr[right] == 1 and (left < right):\n",
    "            right -= 1\n",
    "            \n",
    "            \n",
    "        #if left < right :\n",
    "        arr[left] , arr[right] = arr[right] , arr[left]\n",
    "        left+=1\n",
    "        right-=1\n",
    "        \n",
    "            \n",
    "    \n",
    "    \n",
    "    return arr,left\n",
    "\n",
    "\n",
    "def SortOneTwo(arr,left):\n",
    "    n = len(arr)\n",
    "    right = n-1\n",
    "    \n",
    "    while left < right :\n",
    "        while (arr[left] == 1) and (left < right):\n",
    "            left += 1\n",
    "            \n",
    "        while (arr[right] == 2) and (left < right):\n",
    "            right =- 1\n",
    "            \n",
    "        #if left < right:\n",
    "        arr[left] , arr[right] = arr[right] , arr[left]\n",
    "        left+=1\n",
    "        right-=1\n",
    "            \n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "c9d79dc4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def SortZeroOneTwo(arr):\n",
    "    \n",
    "    arr,left = SortZeroOne(arr)\n",
    "    \n",
    "    arr = SortOneTwo(arr,left-1)\n",
    "    \n",
    "    return arr\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "3e8fbaae",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input array : [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]\n",
      "Output array : [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "## input array\n",
    "arr10 = [0,1,1,0,1,2,1,2,0,0,0,1]\n",
    "print(f\"Input array : {arr10}\")\n",
    "\n",
    "## calling the function\n",
    "output10 = SortZeroOneTwo(arr10)\n",
    "\n",
    "## displaying output\n",
    "print(f\"Output array : {output10}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ceab1314",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "\n",
    "\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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}