{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"provenance":[],"collapsed_sections":["MC8HznqaunCf","mgo8sjTzuqKx","PdA4NEBih_DE","2kE0b8fR34PM","1sCHWr9qcTs0","TK2-an5qZP10","-PD5vWild0VB","xh01qAKjVlOp","z3-Yya1gwJim"],"authorship_tag":"ABX9TyNssCaS6h6Ts7qvkCZFlqAy"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","source":["# Time complexity"],"metadata":{"id":"MC8HznqaunCf"}},{"cell_type":"code","execution_count":null,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"CykOp1qu43q_","executionInfo":{"status":"ok","timestamp":1749198668206,"user_tz":-330,"elapsed":18,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"3f89405f-79c7-4c5d-a628-5343996c2e47"},"outputs":[{"output_type":"stream","name":"stdout","text":["123 O(logN)\n"]}],"source":["def IntToStr(n):\n"," result=''\n"," while(n>0):\n"," result = str(n%10) + result\n"," n = n//10\n"," return result\n","r = IntToStr(123)\n","print(r,type(r),'O(logN)')"]},{"cell_type":"code","source":["def factorial(n):\n"," if n==1:\n"," return 1\n"," else:\n"," return n*factorial(n-1)\n","\n","print(factorial(5),'O(N)')\n","\n","# Input -> 5 10 100\n","#Function call -> 5 10 100"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"ebcCQW378zSb","executionInfo":{"status":"ok","timestamp":1749796397758,"user_tz":-330,"elapsed":74,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"689f9867-5184-4886-f746-d623dcd54b07"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["120 O(N)\n"]}]},{"cell_type":"code","source":["def fibonaci(n):\n"," if n==1 or n==0:\n"," return 1\n"," else:\n"," return fibonaci(n-1) + fibonaci(n-2)\n","\n","print(fibonaci(10),'TC = < O(2^N) OR 1.7^N')\n","# Input -> 1 2 3 5 (add)\n","#Function call -> 1 2 4 14 (multiply)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"2AReP6qE9r7Y","executionInfo":{"status":"ok","timestamp":1749796523137,"user_tz":-330,"elapsed":71,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"6d1d5b45-411b-4cb2-8f41-3c97a65fa476"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["89 TC = < O(2^N) OR 1.7^N\n"]}]},{"cell_type":"code","source":["def power(num):\n"," if num<1:\n"," return 0\n"," elif num == 1:\n"," print(1)\n"," return 1\n"," else:\n"," prev = power(num//2)\n"," curr = prev*2\n"," print(curr)\n"," return curr\n","\n","power(20)\n","print('O(logN)')\n","# Input -> 10 100 1000 (multiply)\n","#Function call -> 4 8 12 (add) number is divided"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"WVIf5Syw_fyb","executionInfo":{"status":"ok","timestamp":1749798701544,"user_tz":-330,"elapsed":29,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"b03c79c9-6210-4619-a05e-44416c9534aa"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["1\n","2\n","4\n","8\n","16\n","O(2^N)\n"]}]},{"cell_type":"code","source":["def mod(a,b):\n"," if b<=0:\n"," return -1\n"," div = a//b\n"," return a - div*b\n","\n","print(mod(10,3),'O(1)')"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"8hhGXl-QAqBQ","executionInfo":{"status":"ok","timestamp":1749799098747,"user_tz":-330,"elapsed":41,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"7f0774b8-976d-47d1-eacf-866aa3d765cd"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["1 O(1)\n"]}]},{"cell_type":"markdown","source":["# LinkedList"],"metadata":{"id":"mgo8sjTzuqKx"}},{"cell_type":"markdown","source":["Basic"],"metadata":{"id":"7nqAT9DKGL46"}},{"cell_type":"code","source":["class Node:\n","\n"," def __init__(self,value):\n"," self.data = value\n"," self.next = None"],"metadata":{"id":"EDUWz_LkuskQ"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["a = Node(1)\n","b = Node(2)\n","c = Node(3)"],"metadata":{"id":"EZmqaJ81vZdB"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print(a)\n","print(a.data)\n","print(a.next)\n","print(b)\n","print(b.data)\n","print(b.next)\n","print(c)\n","print(c.data)\n","print(c.next)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"L-khtfKavhJg","executionInfo":{"status":"ok","timestamp":1749910277786,"user_tz":-330,"elapsed":9,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"4693804e-33c1-4cd3-87cd-f5e90201bb33"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["<__main__.Node object at 0x7c692910cb90>\n","1\n","None\n","<__main__.Node object at 0x7c69291414d0>\n","2\n","None\n","<__main__.Node object at 0x7c6929142410>\n","3\n","None\n"]}]},{"cell_type":"code","source":["print(id(a))\n","print(id(b))\n","print(id(c))"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"YA-5jMtOwdmw","executionInfo":{"status":"ok","timestamp":1749910392958,"user_tz":-330,"elapsed":24,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"acaa8baf-294b-4384-9069-070fbb859afa"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["136791102376848\n","136791102592208\n","136791102596112\n"]}]},{"cell_type":"code","source":["a.next = b\n","b.next = c"],"metadata":{"id":"MZHM9aagxIVj"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print(a.next)\n","print(b.next)\n","print(c.next)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"voTO2JQuyE1B","executionInfo":{"status":"ok","timestamp":1749910348167,"user_tz":-330,"elapsed":12,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"a0a23a7f-6af0-4a75-b727-6358da5da311"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["<__main__.Node object at 0x7c69291414d0>\n","<__main__.Node object at 0x7c6929142410>\n","None\n"]}]},{"cell_type":"code","source":["print(int(0x7c69291414d0))\n","print(int(0x7c6929142410))"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"D_8O17oryG59","executionInfo":{"status":"ok","timestamp":1749910461278,"user_tz":-330,"elapsed":11,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"7cafd029-5db5-4937-ccdd-0b49db8c723c"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["136791102592208\n","136791102596112\n"]}]},{"cell_type":"markdown","source":["Create Class"],"metadata":{"id":"xhLGw1m0GNvK"}},{"cell_type":"code","source":["class Node:\n","\n"," def __init__(self,value):\n"," self.data = value\n"," self.next = None"],"metadata":{"id":"-WHdSbGxyeps"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["class LinkedList:\n","\n"," def __init__(self):\n","\n"," #Empty linked list\n"," self.head = None\n"," self.n = 0\n","\n"," def __len__(self):\n"," return self.n\n","\n","#insert at start\n"," def insert_head(self,value):\n","\n"," #new node\n"," new_node = Node(value)\n","\n"," #create connection\n"," new_node.next = self.head\n","\n"," #reassign head\n"," self.head = new_node\n","\n"," #increment n\n"," self.n += 1\n","#insert at end\n"," def append(self,value):\n"," new_node = Node(value)\n","\n"," if self.head == None:\n"," self.head = new_node\n"," self.n += 1\n"," return\n","\n"," curr = self.head\n"," while curr.next != None:\n"," curr = curr.next\n","\n"," #you are at last node\n"," curr.next = new_node\n"," self.n += 1\n","#insert after(middle)\n"," def insert_after(self,after,value):\n"," new_node = Node(value)\n","\n"," curr = self.head\n","\n"," while curr != None:\n"," if curr.data == after:\n"," break\n"," curr = curr.next\n","\n"," #case 1 break -> item found -> curr = not none\n"," if curr!= None:\n"," new_node.next = curr.next\n"," curr.next = new_node\n"," self.n += 1\n"," else:\n"," return 'item not found'\n","\n","\n","\n","#delete whole\n"," def clear(self):\n"," self.head = None\n"," self.n = 0\n","\n","#delete from head(front)\n"," def delete_head(self):\n"," if self.head == None:\n"," return 'Empty 1'\n"," self.head = self.head.next\n"," self.n -= 1\n","\n","#delete from tail(pop)\n"," def pop(self):\n"," if self.head == None:\n"," return 'Empty 2'\n"," curr = self.head\n"," if curr.next == None:\n"," return self.delete_head()\n"," else:\n"," while curr.next.next != None:\n"," curr = curr.next\n"," curr.next = None\n"," self.n -= 1\n","#delete by value\n"," def remove(self,value):\n","\n"," curr = self.head\n"," if self.head == None:\n"," return 'Empty 4'\n"," elif curr.data == value:\n"," return self.delete_head()\n"," while curr.next != None:\n"," if curr.next.data == value:\n"," break\n"," curr = curr.next\n","\n"," # case 1 -> item found\n"," # case 2 -> item not found\n"," if curr.next == None:\n"," return 'item not found'\n"," else:\n"," curr.next = curr.next.next\n"," self.n -= 1\n","#delete by index(magic method)\n"," def __delitem__(self,index):\n"," if self.head == None:\n"," raise IndexError('Deletion from empty list')\n"," if index == 0:\n"," return self.delete_head()\n"," curr = self.head\n"," pos = 0\n"," while curr != None:\n"," if pos == index:\n"," prev.next = curr.next\n"," self.n -= 1\n"," return\n"," prev = curr\n"," curr = curr.next\n"," pos += 1\n"," raise IndexError('Index out of bounds')\n","\n","\n","#searching\n"," def search(self,item):\n","\n"," curr = self.head\n"," pos=0\n","\n"," while curr != None:\n"," if curr.data == item:\n"," return pos\n"," curr = curr.next\n"," pos += 1\n"," return 'Not found'\n","\n","#search by index\n"," def __getitem__(self,index):\n","\n"," curr = self.head\n"," pos = 0\n","\n"," while curr != None:\n"," if pos == index:\n"," return curr.data\n"," curr = curr.next\n"," pos += 1\n"," return 'Index error'\n","\n","#traverse\n"," def __str__(self):\n","\n"," if self.head == None:\n"," return 'Empty 3'\n","\n"," curr = self.head\n"," result = ''\n"," while curr != None:\n"," result = result + str(curr.data) + '->'\n"," curr = curr.next\n"," return result[:-2]\n","\n","\n","\n","#Practice Problems\n"," def replace_max(self,value):\n"," temp = self.head\n"," max = temp\n"," while temp != None:\n"," if temp.data > max.data:\n"," max = temp\n"," temp = temp.next\n"," max.data = value\n","\n"," def odd_index_sum(self):\n"," temp = self.head\n"," pos = 0\n"," sum = 0\n"," while temp != None:\n"," if pos%2 != 0:\n"," sum += temp.data\n"," temp = temp.next\n"," pos += 1\n"," return sum"],"metadata":{"id":"jF5zRIVBGTnE"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["L = LinkedList()\n","print(L)\n","len(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"9r0_oIrsHOxO","executionInfo":{"status":"ok","timestamp":1750157730435,"user_tz":-330,"elapsed":25,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"214f54d0-4e1e-496d-e2f2-afc1d260e248"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["Empty 3\n"]},{"output_type":"execute_result","data":{"text/plain":["0"]},"metadata":{},"execution_count":195}]},{"cell_type":"code","source":["L.insert_head(1)\n","L.insert_head(2)\n","L.insert_head(3)\n","L.insert_head(4)"],"metadata":{"id":"KmG94iSUHlWD"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["len(L)\n","print(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"vWUfn2I2J5wD","executionInfo":{"status":"ok","timestamp":1750157734038,"user_tz":-330,"elapsed":69,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"33e3bbde-a9c3-4ed7-8181-f06fbcb9e18d"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["4->3->2->1\n"]}]},{"cell_type":"code","source":["L.append(5)\n","L.append(6)\n","print(L)"],"metadata":{"id":"7G5_MKi0Rr4g","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1750157734417,"user_tz":-330,"elapsed":8,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"7e60950d-ee00-494f-a4a4-f056fbeda767"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["4->3->2->1->5->6\n"]}]},{"cell_type":"code","source":["L.insert_after(1,0)\n","print(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"XRo0Aw-5APpU","executionInfo":{"status":"ok","timestamp":1750157409370,"user_tz":-330,"elapsed":48,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"a2ce0572-1992-413a-e3af-02209b8ae78e"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["4->3->2->1->0->5->6\n"]}]},{"cell_type":"code","source":["L.delete_head()\n","print(L)"],"metadata":{"id":"UUn6D2XEMmBx","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1750157409371,"user_tz":-330,"elapsed":24,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"3aa0b636-2c00-4948-b1d6-f37a2b405c51"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["3->2->1->0->5->6\n"]}]},{"cell_type":"code","source":["L.pop()\n","print(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"X3TBnAwRCNA2","executionInfo":{"status":"ok","timestamp":1750157409374,"user_tz":-330,"elapsed":15,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"517457de-5212-4a5d-ee4f-75d6058a288f"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["3->2->1->0->5\n"]}]},{"cell_type":"code","source":["L.remove(10)"],"metadata":{"id":"0p160kWyFmOj","colab":{"base_uri":"https://localhost:8080/","height":36},"executionInfo":{"status":"ok","timestamp":1750157409378,"user_tz":-330,"elapsed":6,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"faff4185-0228-4e6e-b6c3-d179b396de3e"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["'item not found'"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":186}]},{"cell_type":"code","source":["L.remove(1)\n","print(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"R_48Md920TRA","executionInfo":{"status":"ok","timestamp":1750157409394,"user_tz":-330,"elapsed":13,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"fe22a797-76e3-4fae-8cd4-a8d4c2ca5b03"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["3->2->0->5\n"]}]},{"cell_type":"code","source":["L.search(2)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"1sZIPzTS1edW","executionInfo":{"status":"ok","timestamp":1750157409428,"user_tz":-330,"elapsed":8,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"11d3b0d8-612b-492d-bf59-0364add65753"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["1"]},"metadata":{},"execution_count":188}]},{"cell_type":"code","source":["L[0]"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"0AOkARgU2jgX","executionInfo":{"status":"ok","timestamp":1750157409441,"user_tz":-330,"elapsed":10,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"99eb873f-a7c4-4b68-8d50-8c67f05fd177"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["3"]},"metadata":{},"execution_count":189}]},{"cell_type":"code","source":["del L[0]"],"metadata":{"id":"J_ZVA4cR3eW9"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"fhygKhk2aFXR","executionInfo":{"status":"ok","timestamp":1750157411016,"user_tz":-330,"elapsed":9,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"8bd65687-ca6b-48d7-b960-1886799980a9"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["2->0->5\n"]}]},{"cell_type":"code","source":["L.replace_max(10)"],"metadata":{"id":"oLntbODGgsEG"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"8aXYLrlcgvL1","executionInfo":{"status":"ok","timestamp":1750157428012,"user_tz":-330,"elapsed":23,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"f81eb3d7-b6ef-46c4-ab90-9ef543f6317a"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["2->0->10\n"]}]},{"cell_type":"markdown","source":["# Practice problems of Linkedlist"],"metadata":{"id":"PdA4NEBih_DE"}},{"cell_type":"code","source":["class Node:\n"," def __init__(self,value):\n"," self.data = value\n"," self.next = None"],"metadata":{"id":"J_HZPW5EgwNd"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["class LinkedList:\n","\n"," def __init__(self):\n"," self.head = None\n"," self.n = 0\n","\n"," def __len__(self):\n"," return self.n\n","\n"," def append(self,value):\n"," new_node = Node(value)\n"," if self.head == None:\n"," self.head = new_node\n"," self.n += 1\n"," return\n"," curr = self.head\n"," while curr.next != None:\n"," curr = curr.next\n"," curr.next = new_node\n"," self.n += 1\n"," return\n","\n","#Practice Problems\n"," def replace_max(self,value):\n"," temp = self.head\n"," max = temp\n"," while temp != None:\n"," if temp.data > max.data:\n"," max = temp\n"," temp = temp.next\n"," max.data = value\n","\n"," def odd_index_sum(self):\n"," temp = self.head\n"," pos = 0\n"," sum = 0\n"," while temp != None:\n"," if pos%2 != 0:\n"," sum += temp.data\n"," temp = temp.next\n"," pos += 1\n"," return sum\n","\n","#in-place reversal\n"," def reverse(self):\n"," prev_node = None\n"," curr_node = self.head\n","\n"," while curr_node != None:\n"," next_node = curr_node.next\n"," curr_node.next = prev_node\n"," prev_node = curr_node\n"," curr_node = next_node\n"," self.head = prev_node\n","\n"," def traverse(self):\n"," curr = self.head\n"," while curr != None:\n"," print(curr.data,end='')\n"," curr=curr.next\n","\n","# if single '*' and '/' then ' ' and double '*' and '/' then ' ' and capital next char\n"," def replace_char(self):\n"," temp = self.head\n","\n"," while temp != None:\n","\n"," if temp.data == '*' or temp.data == '/':\n"," temp.data = ' '\n","\n"," if temp.next.data == '*' or temp.next.data == '/':\n"," temp.next.next.data = temp.next.next.data.upper()\n"," temp.next = temp.next.next\n"," temp = temp.next\n","\n"," def __str__(self):\n","\n"," if self.head == None:\n"," return 'Empty'\n"," result = ''\n"," curr = self.head\n"," while curr != None:\n"," result = result + str(curr.data) + '->'\n"," curr = curr.next\n"," return result[:-2]"],"metadata":{"id":"sA0kbWNii3Od"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["L = LinkedList()"],"metadata":{"id":"i5XXkrCskpCM"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["L.append(1)\n","L.append(2)\n","L.append(3)\n","L.append(4)\n","L.append(5)\n","L.append(6)\n","L.append(8)"],"metadata":{"id":"o8IUhpE2ktXo"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"Oh2LpjKmsfzx","executionInfo":{"status":"ok","timestamp":1750228149416,"user_tz":-330,"elapsed":5,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"4a48521b-a1e7-46bc-ad9a-6bd86f9ab812"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["1->2->3->4->5->6->8\n"]}]},{"cell_type":"code","source":["L.odd_index_sum()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"7DLH_erJshC9","executionInfo":{"status":"ok","timestamp":1750228149633,"user_tz":-330,"elapsed":15,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"325483e7-b9d7-4813-c458-83437bc10024"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["12"]},"metadata":{},"execution_count":13}]},{"cell_type":"code","source":["L.replace_max(7)"],"metadata":{"id":"eBsxBnIBstkY"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print(L)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"5QD9GJ1js4VU","executionInfo":{"status":"ok","timestamp":1750228149946,"user_tz":-330,"elapsed":14,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"43d940bb-5bbc-42ff-b72c-eb233038646b"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["1->2->3->4->5->6->7\n"]}]},{"cell_type":"code","source":["L.reverse()\n","print(L)"],"metadata":{"id":"uMqgvn6js5KF","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1750228168058,"user_tz":-330,"elapsed":6,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"35a94200-9d5f-49e5-e870-994a44ea9290"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["7->6->5->4->3->2->1\n"]}]},{"cell_type":"markdown","source":["Replace characters"],"metadata":{"id":"VHyAKvWf0hs5"}},{"cell_type":"code","source":["L1 = LinkedList()"],"metadata":{"id":"EyMkAG5tukqH"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["L1.append('T')\n","L1.append('h')\n","L1.append('e')\n","L1.append('/')\n","L1.append('*')\n","L1.append('s')\n","L1.append('k')\n","L1.append('y')\n","L1.append('*')\n","L1.append('i')\n","L1.append('s')\n","L1.append('/')\n","L1.append('/')\n","L1.append('b')\n","L1.append('l')\n","L1.append('u')\n","L1.append('e')"],"metadata":{"id":"Rbhz4W0F0vE2"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["L1.traverse()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"CKCUKXBY1FbS","executionInfo":{"status":"ok","timestamp":1750230542505,"user_tz":-330,"elapsed":20,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"bca3c676-b2de-4ac0-d1ca-3092ad1353c2"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["The/*sky*is//blue"]}]},{"cell_type":"code","source":["L1.replace_char()"],"metadata":{"id":"E7vANgtG1GxI"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["L1.traverse()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"EAsNF7N53cF9","executionInfo":{"status":"ok","timestamp":1750230542832,"user_tz":-330,"elapsed":44,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"95c02c7d-c25e-4542-d180-dd297d6146d4"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["The Sky is Blue"]}]},{"cell_type":"markdown","source":["# Stack using Linkedlist\n","\n","1. -> LIFO\n","2. ->push,pop,peek,empty,size"],"metadata":{"id":"2kE0b8fR34PM"}},{"cell_type":"markdown","source":["using LL"],"metadata":{"id":"9Wlg3mwsYX3J"}},{"cell_type":"code","source":["class Node:\n"," def __init__(self,value):\n"," self.data = value\n"," self.next = None"],"metadata":{"id":"BDLn8pUNYk0k"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["#from inspect import isgenerator\n","class Stack:\n"," def __init__(self):\n"," self.top = None\n","\n"," def isempty(self):\n"," return self.top == None\n","\n"," def push(self,value):\n"," new_node = Node(value)\n"," new_node.next = self.top\n"," self.top = new_node\n","\n"," def traverse(self):\n"," temp = self.top\n"," while temp:\n"," print('|' + str(temp.data) + '|')\n"," temp = temp.next\n","\n"," def peek(self):\n"," if self.isempty():\n"," return 'Empty stack'\n"," else:\n"," return self.top.data\n","\n"," def pop(self):\n"," if self.isempty():\n"," return 'Empty Stack'\n"," else:\n"," self.top = self.top.next\n"," return 'item pop'"],"metadata":{"id":"Fo_bYOPn3dvp"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["s = Stack()"],"metadata":{"id":"98Euj0yfZ8wS"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["s.peek()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":36},"id":"_3qUWt92bTiY","executionInfo":{"status":"ok","timestamp":1750240039970,"user_tz":-330,"elapsed":8,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"1a3e8b39-6761-4a63-e038-8825be0d13f6"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["'Empty stack'"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":75}]},{"cell_type":"code","source":["s.isempty()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"ITbNmrNMaCyz","executionInfo":{"status":"ok","timestamp":1750240040146,"user_tz":-330,"elapsed":20,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"b6d54e3d-3644-4bf4-b587-476e5c8e3dfb"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{},"execution_count":76}]},{"cell_type":"code","source":["s.push(1)\n","s.push(2)\n","s.push(3)"],"metadata":{"id":"m1lbGAv-aD-f"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["s.traverse()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"svVJ2O49aKec","executionInfo":{"status":"ok","timestamp":1750240040492,"user_tz":-330,"elapsed":33,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"76c27927-0bfd-4bcb-b0d1-9b92e5ad97a5"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["|3|\n","|2|\n","|1|\n"]}]},{"cell_type":"code","source":["s.isempty()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"xSZPh3-FaLYk","executionInfo":{"status":"ok","timestamp":1750240040795,"user_tz":-330,"elapsed":12,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"6f91d972-8df4-4696-da28-169b658266c3"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["False"]},"metadata":{},"execution_count":79}]},{"cell_type":"code","source":["s.push(4)\n","s.push(5)\n","s.push(6)"],"metadata":{"id":"Ipo6Lnx3avnE"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["s.traverse()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"JDrBUQ2Wa5k7","executionInfo":{"status":"ok","timestamp":1750240040949,"user_tz":-330,"elapsed":19,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"0f08ebb5-dc0c-41ec-8c4d-88ded22726d8"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["|6|\n","|5|\n","|4|\n","|3|\n","|2|\n","|1|\n"]}]},{"cell_type":"code","source":["s.peek()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"KDWcCnHma6zz","executionInfo":{"status":"ok","timestamp":1750240041116,"user_tz":-330,"elapsed":54,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"2858deba-7e04-4fbb-a528-4a2dee9ece92"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["6"]},"metadata":{},"execution_count":82}]},{"cell_type":"code","source":["s.pop()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":36},"id":"FjWJVl0HbHr1","executionInfo":{"status":"ok","timestamp":1750240041818,"user_tz":-330,"elapsed":20,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"a6f07c13-2bb4-4672-89e9-65517ec53f2d"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["'item pop'"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":83}]},{"cell_type":"code","source":["s.traverse()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"a1s5xgWCb1ky","executionInfo":{"status":"ok","timestamp":1750240044749,"user_tz":-330,"elapsed":54,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"b17fc9ac-eee8-4e66-a120-e8fb8564bb0f"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["|5|\n","|4|\n","|3|\n","|2|\n","|1|\n"]}]},{"cell_type":"markdown","source":["#Practice Problems using Stack"],"metadata":{"id":"1sCHWr9qcTs0"}},{"cell_type":"code","source":["class Node:\n"," def __init__(self,value):\n"," self.data = value\n"," self.next = None\n"],"metadata":{"id":"O9DimxUvb6Tv"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["# we never use stack for string reversal becasue it takes O(N) TC and SC"],"metadata":{"id":"kxRfP8bDJURz"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["class Stack:\n"," def __init__(self):\n"," self.top = None\n","\n"," def push(self,value):\n"," new_node = Node(value)\n"," new_node.next = self.top\n"," self.top = new_node\n","\n"," def size(self):\n"," temp = self.top\n"," count = 0\n"," while temp:\n"," temp = temp.next\n"," count += 1\n"," return count\n","\n"," def isempty(self):\n"," return self.top == None\n","\n"," def pop(self):\n"," if self.isempty():\n"," return 'Empty'\n"," else:\n"," value = self.top.data\n"," self.top = self.top.next\n"," return value\n","\n"," def traverse(self):\n"," temp = self.top\n"," while temp:\n"," print('|' + str(temp.data) + '|')\n"," temp = temp.next\n"," def peek(self):\n"," return self.top.data"],"metadata":{"id":"Je7e-PoLcmEc"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["def reverse(text):\n"," s = Stack()\n","\n"," for i in text:\n"," s.push(i)\n","\n"," if s.isempty():\n"," return 'Empty string'\n"," else:\n"," result =''\n"," temp = s.top\n"," while temp:\n"," result += str(s.pop())\n"," temp = temp.next\n"," print(result)"],"metadata":{"id":"zcW6t8GzOHoy"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["reverse('hello world')"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"PhXtFcPPd1FS","executionInfo":{"status":"ok","timestamp":1750338198642,"user_tz":-330,"elapsed":14,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"15657608-136f-4aa0-8128-b4256762a781"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["dlrow olleh\n"]}]},{"cell_type":"code","source":["def text_editor(text,pattern):\n","\n"," u = Stack()\n"," r = Stack()\n","\n"," for i in text:\n"," u.push(i)\n","\n"," for i in pattern:\n"," if i == 'u':\n"," data = u.pop()\n"," r.push(data)\n"," else:\n"," data = r.pop()\n"," u.push(data)\n"," result =''\n"," while not u.isempty():\n"," result = str(u.pop()) + result\n"," print(result)"],"metadata":{"id":"n1Q6f31Lfjyu"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["text_editor('hello','uur')"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"5rcXRhjwMRXc","executionInfo":{"status":"ok","timestamp":1750338200529,"user_tz":-330,"elapsed":21,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"1073fce2-f63e-48eb-a102-30e3fe3a6393"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["hell\n"]}]},{"cell_type":"code","source":["l = [\n"," [0,0,1,1],\n"," [0,0,1,0],\n"," [0,0,0,0],\n"," [0,0,1,0]\n","]"],"metadata":{"id":"TCM2v_2TNden"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["def find_the_celeb(L):\n","\n"," s = Stack()\n","\n"," for i in range(len(L)):\n"," s.push(i)\n","\n"," while s.size() >= 2:\n","\n"," i = s.pop()\n"," j = s.pop()\n","\n"," if L[i][j] == 0:\n"," #j is not celebrity\n"," s.push(i)\n"," else:\n"," #i is not celebrity\n"," s.push(j)\n","\n"," celeb = s.pop()\n","\n"," for i in range(len(L)):\n"," if i != celeb:\n"," if L[i][celeb] == 0 or L[celeb][i] == 1:\n"," print('No one is a celebrity')\n"," return\n"," print(celeb,'is a celebrity' )\n"],"metadata":{"id":"djhVGuRyhs_5"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["find_the_celeb(l)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"DApKrkZjh014","executionInfo":{"status":"ok","timestamp":1750338210748,"user_tz":-330,"elapsed":24,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"fea5d3c9-8b67-49a0-9a8e-9f9533786a8e"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["2 is a celebrity\n"]}]},{"cell_type":"code","source":["def balance_para(exp):\n"," s = Stack()\n"," for char in exp:\n","\n"," if char == '(' or char == '[' or char == '{':\n"," s.push(char)\n","\n"," elif char == ')':\n"," if s.size() == 0 or s.peek() != '(':\n"," return False\n"," s.pop()\n","\n"," elif char == ']':\n"," if s.size() == 0 or s.peek() != '[':\n"," return False\n"," s.pop()\n","\n"," elif char == '}':\n"," if s.size() == 0 or s.peek() != '{':\n"," return False\n"," s.pop()\n","\n"," return s.size() == 0"],"metadata":{"id":"SBnYDnzgkzFE"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["balance_para('{}{}')"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"76lCgXDuRzrR","executionInfo":{"status":"ok","timestamp":1750338653434,"user_tz":-330,"elapsed":54,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"cc27e1d7-7546-4aa1-a3f1-ced7fc810d0e"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{},"execution_count":64}]},{"cell_type":"markdown","source":["#Stack using Array"],"metadata":{"id":"TK2-an5qZP10"}},{"cell_type":"code","source":["class Stack:\n","\n"," def __init__(self,size):\n"," self.size = size\n"," self.stack = [None] * self.size\n"," self.top = -1\n","\n"," def push(self,value):\n"," if self.top == self.size - 1:\n"," return 'Overflow'\n"," else:\n"," self.top += 1\n"," self.stack[self.top] = value\n","\n"," def pop(self):\n"," if self.top == -1:\n"," return 'Empty'\n"," else:\n"," data = self.stack[self.top]\n"," self.top -= 1\n"," return data\n"," def traverse(self):\n","\n"," for i in range(self.top + 1):\n"," print(self.stack[i],end=' ')"],"metadata":{"id":"bGxVMmgaZmFZ"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["s = Stack(3)"],"metadata":{"id":"cBD7UOPldDYk"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["s.stack"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"xMzlZKBFdGef","executionInfo":{"status":"ok","timestamp":1750357809204,"user_tz":-330,"elapsed":7,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"253f4655-5f21-419f-e012-2d2f281cd26c"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[None, None, None]"]},"metadata":{},"execution_count":45}]},{"cell_type":"code","source":["s.push(1)"],"metadata":{"id":"rgg_P3HYdJZ5"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["s.stack"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"Rd2LoGdddK0p","executionInfo":{"status":"ok","timestamp":1750357819357,"user_tz":-330,"elapsed":37,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"8a4f6b5a-d936-4818-9c46-bc80104e2e5d"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[1, None, None]"]},"metadata":{},"execution_count":47}]},{"cell_type":"code","source":["s.pop()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"fO1lGGLXdL3z","executionInfo":{"status":"ok","timestamp":1750357824900,"user_tz":-330,"elapsed":23,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"0b5b5a9a-5234-4fb7-b46f-f41c2e0a4721"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["1"]},"metadata":{},"execution_count":48}]},{"cell_type":"code","source":["s.stack"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"THJKFifudNM1","executionInfo":{"status":"ok","timestamp":1750357831243,"user_tz":-330,"elapsed":5,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"95f60116-370a-429c-d41f-44467b372d86"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[1, None, None]"]},"metadata":{},"execution_count":49}]},{"cell_type":"code","source":["s.push(2)"],"metadata":{"id":"yhbSO8rGdQxb"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["s.traverse()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"0h7kRpVOdOyS","executionInfo":{"status":"ok","timestamp":1750357850039,"user_tz":-330,"elapsed":6,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"8a2e1a3d-df9f-407e-bd84-163b47cdf54e"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["2 "]}]},{"cell_type":"markdown","source":["# Queue"],"metadata":{"id":"-PD5vWild0VB"}},{"cell_type":"markdown","source":["1. FIFO\n","2. head = Front\n","3. tail = Rear\n","4. insertion = Enque\n","5. deletion = Deque\n","6. Entry from one side and Exit from another side, both operation in O(1)"],"metadata":{"id":"ETckmxkQd3DT"}},{"cell_type":"code","source":["class Node:\n","\n"," def __init__(self,value):\n"," self.data = value\n"," self.next = None"],"metadata":{"id":"5TFM4im4d1hN"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["class Queue:\n","\n"," def __init__(self):\n"," self.front = None\n"," self.rear = None\n","\n"," def enqueue(self,value):\n"," new_node = Node(value)\n"," if self.rear == None:\n"," self.front = new_node\n"," self.rear = self.front\n"," else:\n"," self.rear.next = new_node\n"," self.rear = new_node\n","\n"," def dequeue(self):\n"," if self.front == None:\n"," return 'Empty'\n"," else:\n"," data = self.front.data\n"," self.front = self.front.next\n"," return data\n","\n"," def isempty(self):\n"," return self.front == None\n","\n"," def size(self):\n"," count = 0\n"," temp = self.front\n"," while temp:\n"," temp = temp.next\n"," count += 1\n"," return count\n","\n"," def front_item(self):\n"," if self.front == None:\n"," return 'Empty'\n"," else:\n"," return self.front.data\n","\n"," def rear_item(self):\n"," if self.rear == None:\n"," return 'Empty'\n"," else:\n"," return self.rear.data\n","\n"," def traverse(self):\n"," temp = self.front\n"," while temp:\n"," print(temp.data,end = ' ')\n"," temp = temp.next"],"metadata":{"id":"PTe2SJBROZrI"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["q = Queue()"],"metadata":{"id":"g85IR0kOQNEx"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["q.enqueue(0)\n","q.enqueue(1)\n","q.enqueue(2)\n","q.enqueue(3)\n","q.enqueue(4)"],"metadata":{"id":"PGcdD3t6QRAy"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["q.dequeue()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"1HxbmReIQ3QJ","executionInfo":{"status":"ok","timestamp":1750422094647,"user_tz":-330,"elapsed":24,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"126a67e4-7ebc-4c50-bca5-44bc36f2a673"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["0"]},"metadata":{},"execution_count":41}]},{"cell_type":"code","source":["q.traverse()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"FGMlszIxQ8WY","executionInfo":{"status":"ok","timestamp":1750422094850,"user_tz":-330,"elapsed":19,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"c6988f26-c800-4f96-9408-5603a25bb833"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["1 2 3 4 "]}]},{"cell_type":"code","source":["q.isempty()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"_JWEp8zSQ9yG","executionInfo":{"status":"ok","timestamp":1750422095050,"user_tz":-330,"elapsed":96,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"4ea9198d-b5c6-49c7-bb42-acf102b293c5"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["False"]},"metadata":{},"execution_count":43}]},{"cell_type":"code","source":["q.size()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"7ZhcwUZoRvB6","executionInfo":{"status":"ok","timestamp":1750422095117,"user_tz":-330,"elapsed":7,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"350fe23c-218c-4d48-b31e-1b929d169fce"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["4"]},"metadata":{},"execution_count":44}]},{"cell_type":"code","source":["q.front_item()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"vCN1h_BaRwjs","executionInfo":{"status":"ok","timestamp":1750422096448,"user_tz":-330,"elapsed":17,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"c8ef9309-8e08-4c94-ddb4-061f6b8ffc9c"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["1"]},"metadata":{},"execution_count":45}]},{"cell_type":"code","source":["q.rear_item()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"jrL8rrVzSQkp","executionInfo":{"status":"ok","timestamp":1750422096759,"user_tz":-330,"elapsed":12,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"3dd5919e-a592-490e-e889-6a440e4ef303"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["4"]},"metadata":{},"execution_count":46}]},{"cell_type":"markdown","source":["# Practice problems using queue"],"metadata":{"id":"xh01qAKjVlOp"}},{"cell_type":"markdown","source":["1. Queue behaviour using 2 stack"],"metadata":{"id":"9AUnWsFPWHzk"}},{"cell_type":"code","source":["s1 = Stack()\n","s2 = Stack()"],"metadata":{"id":"STd8L0FySSGQ"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["def enqueue_s(value):\n"," s1.push(value)\n","\n","def dequeue_s():\n"," if s1.isempty() and s2.isempty():\n"," return 'Empty'\n"," elif s2.isempty():\n"," while not s1.isempty():\n"," s2.push(s1.pop())\n"," return s2.pop()"],"metadata":{"id":"pC0RPjW_WYhc"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["enqueue_s(0)\n","enqueue_s(1)\n","enqueue_s(2)\n","enqueue_s(3)\n","enqueue_s(4)"],"metadata":{"id":"c-7HxNhrXJad"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["dequeue_s()"],"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":36},"id":"ttwuddO8XNnS","executionInfo":{"status":"ok","timestamp":1750423605859,"user_tz":-330,"elapsed":8,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"4e8dcd26-a0b9-45c8-d580-74459197aa53"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["'item pop'"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":75}]},{"cell_type":"markdown","source":["# Hashing\n","\n","1. searching in o(1)\n","\n","---\n","Colision avoiding\n","\n","1. Chaining(array of linkedlist)\n","2. Linear Probing\n","3. Quadratic probing\n"],"metadata":{"id":"z3-Yya1gwJim"}},{"cell_type":"markdown","source":["**Linear Probing**"],"metadata":{"id":"mFIpT7AXy9UU"}},{"cell_type":"code","source":["class Dictionary:\n","\n"," def __init__(self,size):\n"," self.size = size\n"," self.slots = [None] * self.size\n"," self.data = [None] * self.size\n","\n"," def put(self,key,value):\n"," hashvalue = self.hash_function(key)\n","\n"," if self.slots[hashvalue] == None:\n"," self.slots[hashvalue] = key\n"," self.data[hashvalue] = value\n"," else:\n"," if self.slots[hashvalue] == key:\n"," self.data[hashvalue] = value\n"," else:\n"," new_hash_value = self.rehash(hashvalue)\n","\n"," while self.slots[new_hash_value] != None and self.slots[new_hash_value] != key:\n"," new_hash_value = self.rehash(new_hash_value)\n","\n"," if self.slots[new_hash_value] == None:\n"," self.slots[new_hash_value] = key\n"," self.data[new_hash_value] = value\n"," else:\n"," self.data[new_hash_value] = value\n","\n"," def __setitem__(self,key,value):\n"," self.put(key,value)\n","\n"," def get(self,key):\n"," start_pos = self.hash_function(key)\n"," current_pos = start_pos\n","\n"," while self.slots[current_pos] != None:\n"," if self.slots[current_pos] == key:\n"," return self.data[current_pos]\n"," current_pos = self.rehash(current_pos)\n"," if current_pos == start_pos:\n"," return 'Not Found'\n"," return 'None Not Found'\n","\n"," def __str__(self):\n","\n"," for i in range(len(self.slots)):\n"," if self.slots[i] != None:\n"," print(self.slots[i],':',self.data[i],end=' ')\n"," return ''\n","\n"," def __getitem__(self,key):\n"," return self.get(key)\n","\n","\n"," def hash_function(self,key):\n"," return abs(hash(key)) % self.size\n","\n"," def rehash(self,oldhash):\n"," return (oldhash + 1) % self.size\n"],"metadata":{"id":"3pgB59FpwKok"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["D1 = Dictionary(3)"],"metadata":{"id":"ntkYlWxg3DoT"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["D1.slots"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"W5Cn5y2E3GVK","executionInfo":{"status":"ok","timestamp":1750701341399,"user_tz":-330,"elapsed":22,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"5b564aa5-2eef-4b51-b142-eb280a3391ab"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[None, None, None]"]},"metadata":{},"execution_count":80}]},{"cell_type":"code","source":["D1.data"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"fsdi9wRd3Ilw","executionInfo":{"status":"ok","timestamp":1750701341730,"user_tz":-330,"elapsed":124,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"901bf562-34a9-4989-d112-7d5c888a7a12"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[None, None, None]"]},"metadata":{},"execution_count":81}]},{"cell_type":"code","source":["D1['python'] = 50\n","D1.put('java',50)"],"metadata":{"id":"zFNMTXwq3KOF"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print(D1.slots)\n","print(D1.data)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"0gH75glu3dVG","executionInfo":{"status":"ok","timestamp":1750701341957,"user_tz":-330,"elapsed":29,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"14ea9a12-cd1e-42d6-852b-d3294f659c08"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["['java', None, 'python']\n","[50, None, 50]\n"]}]},{"cell_type":"code","source":["D1.put('java',80)"],"metadata":{"id":"iB8MNaft3zQG"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print(D1.slots)\n","print(D1.data)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"52Vz6yiX355O","executionInfo":{"status":"ok","timestamp":1750701342264,"user_tz":-330,"elapsed":18,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"d7a661b2-1fec-423e-8806-1bbc782ea2fe"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["['java', None, 'python']\n","[80, None, 50]\n"]}]},{"cell_type":"code","source":["D1.get('C')"],"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":36},"id":"RSz7S4CB4Wq0","executionInfo":{"status":"ok","timestamp":1750701342905,"user_tz":-330,"elapsed":14,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"8e79f2f1-39d4-41a8-8ec4-a8f5a2d20e5a"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["'None Not Found'"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":86}]},{"cell_type":"code","source":["D1[\"C++\"]"],"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":36},"id":"-7o8E0N96Xwb","executionInfo":{"status":"ok","timestamp":1750701343415,"user_tz":-330,"elapsed":7,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"a1015034-f31e-4922-9779-8e8878e4b27a"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["'None Not Found'"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":87}]},{"cell_type":"code","source":["print(D1)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"6f3BbJOy60Ob","executionInfo":{"status":"ok","timestamp":1750701351903,"user_tz":-330,"elapsed":15,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"d8ddba8f-4a81-4b97-f2c5-dedecf2e4ec0"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["java : 80 python : 50 \n"]}]},{"cell_type":"markdown","source":["#Skipping hashing"],"metadata":{"id":"woh4g0e2733_"}},{"cell_type":"markdown","source":["# Sort"],"metadata":{"id":"VlVWZ0rOF3tM"}},{"cell_type":"markdown","source":["Absolutely! Here's the **full comparison table** of popular sorting algorithms with:\n","\n","* ✅ **Best, Average, Worst-case Time Complexity**\n","* 💾 **Space Complexity**\n","* 🔁 **Stability**\n","* 🔍 **Comparison or Non-comparison**\n","* 🧠 **Adaptiveness** *(Does it optimize for already sorted input?)*\n","\n","---\n","\n","## 📊 Master Comparison of Sorting Algorithms\n","\n","| Algorithm | Best Case | Average Case | Worst Case | Space | Stable | Type | Adaptive |\n","| ----------------------- | ---------- | ------------ | ---------- | -------- | ------ | ---------------- | -------- |\n","| **Bubble Sort** | O(n) | O(n²) | O(n²) | O(1) | ✅ | Comparison-based | ✅ |\n","| **Selection Sort** | O(n²) | O(n²) | O(n²) | O(1) | ❌ | Comparison-based | ❌ |\n","| **Insertion Sort** | O(n) | O(n²) | O(n²) | O(1) | ✅ | Comparison-based | ✅ |\n","| **Merge Sort** | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | Comparison-based | ❌ |\n","| **Quick Sort** | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | Comparison-based | ❌ |\n","| **Heap Sort** | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | Comparison-based | ❌ |\n","| **Count Sort** | O(n + k) | O(n + k) | O(n + k) | O(n + k) | ✅ | Non-comparison | ❌ |\n","| **Radix Sort** | O(nk) | O(nk) | O(nk) | O(n + k) | ✅ | Non-comparison | ❌ |\n","| **Bucket Sort** | O(n + k) | O(n + k) | O(n²) | O(n + k) | ✅ | Non-comparison | ❌ |\n","| **Shell Sort** | O(n log n) | O(n^1.5) | O(n²) | O(1) | ❌ | Comparison-based | ✅ |\n","| **Tim Sort** *(Python)* | O(n) | O(n log n) | O(n log n) | O(n) | ✅ | Comparison-based | ✅ |\n","\n","---\n","\n","### 🔍 Legend\n","\n","* **Stable**: Maintains the order of equal elements.\n","* **Adaptive**: Performs faster if the array is already or nearly sorted.\n","* **k**: Range of input values (used in count/radix).\n","* **n**: Number of elements.\n","\n","---\n","\n","## 🏆 Summary\n","\n","| Use Case | Recommended Algorithm |\n","| --------------------------------------- | ------------------------ |\n","| Small or nearly sorted | Insertion Sort, Tim Sort |\n","| Large general purpose | Merge Sort, Quick Sort |\n","| Integers in small range | Count Sort |\n","| Integers/floats in uniform distribution | Bucket Sort |\n","| Fixed-length integers/strings | Radix Sort |\n","| In-place with no extra memory | Heap Sort |\n","\n","---\n","\n"],"metadata":{"id":"EVVr8uwrQCBP"}},{"cell_type":"code","source":["def is_sorted(arr):\n","\n"," sorted = True\n","\n"," for i in range(len(arr)-1):\n"," if arr[i] > arr[i+1]:\n"," sorted = False\n"," return sorted\n"," return sorted"],"metadata":{"id":"bslK60uzF_ot"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["import random\n","a=[1,2,3,4]\n","random.shuffle(a)\n","a"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"XLHIHG-EGZQN","executionInfo":{"status":"ok","timestamp":1750737815718,"user_tz":-330,"elapsed":6,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"398acf16-19c4-48b6-9225-02cc89f7e8b7"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[2, 4, 3, 1]"]},"metadata":{},"execution_count":15}]},{"cell_type":"code","source":["#monkey sort\n","import time\n","def monkey_sort(arr):\n","\n"," while not is_sorted(arr):\n"," time.sleep(1)\n"," random.shuffle(arr)\n"," print(arr)\n"," print(arr)"],"metadata":{"id":"qFsk4Km7F4jm"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["a = [1,4,3,6,5]\n","monkey_sort(a)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"9vk9A9rZGo1n","executionInfo":{"status":"ok","timestamp":1750738032352,"user_tz":-330,"elapsed":19002,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"301d03c5-9542-4b71-c0c4-fd6449ca1c71"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["[3, 4, 1, 6, 5]\n","[4, 1, 5, 3, 6]\n","[3, 6, 4, 5, 1]\n","[5, 4, 3, 1, 6]\n","[4, 3, 5, 1, 6]\n","[4, 3, 6, 1, 5]\n","[3, 5, 6, 4, 1]\n","[4, 1, 6, 5, 3]\n","[6, 4, 5, 1, 3]\n","[5, 6, 1, 4, 3]\n","[5, 4, 3, 1, 6]\n","[4, 1, 6, 5, 3]\n","[5, 3, 6, 1, 4]\n","[5, 3, 4, 1, 6]\n","[4, 3, 5, 6, 1]\n","[1, 5, 6, 3, 4]\n","[6, 1, 3, 4, 5]\n","[5, 4, 3, 6, 1]\n","[1, 3, 4, 5, 6]\n","[1, 3, 4, 5, 6]\n"]}]},{"cell_type":"code","source":["#sleep sort print after array elements seconds"],"metadata":{"id":"hPEGknKLG-yl"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["#bubble sort\n","\n","# No. of pass = n-1\n","# No. of comparison = maximum possible --> n(n-1)/2 --> o(n)^2\n","# No. of swap = o(n)^2\n","# Time Complexity --> Best case = O(N), avarage case = O(N)^2, worst case = O(N)^2\n","# Space Complexity = O(1)\n","# bubble sort is not adaptive but we can make it using flag so best case -> o(n)\n","# bubble sort is stable\n","\n","def bubble_sort(arr):\n"," for i in range(len(arr) - 1):\n"," flag = 0\n"," for j in range(len(arr) - 1 - i):\n"," if arr[j] > arr[j+1]:\n"," flag = 1\n"," arr[j],arr[j+1] = arr[j+1],arr[j]\n"," if flag == 0:\n"," break\n"," print(arr)"],"metadata":{"id":"eW4pf1jfgkNm"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["bubble_sort([4,6,2,1,8,7])"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"nF7TdEm7hy8m","executionInfo":{"status":"ok","timestamp":1750761766043,"user_tz":-330,"elapsed":31,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"4893d3fa-cd3f-4355-d19b-cc41356d93b9"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["[1, 2, 4, 6, 7, 8]\n"]}]},{"cell_type":"code","source":["#selection sort\n","\n","# no. of pass = n-1\n","# no of comparison = n(n-1)/2 -> o(n)^2\n","# no of swaps = n-1 (one swap for every pass) -> o(n)\n","# Time Complexity --> Best case = O(N)^2, avarage case = O(N)^2, worst case = O(N)^2\n","# Space complexity = O(1)\n","# Not Adaptive\n","# in best case bubble_sort performs well\n","# Not Stable\n","\n","def selection_sort(arr):\n","\n"," for i in range(len(arr)-1):\n"," min = i\n","\n"," for j in range(i+1,len(arr)):\n"," if arr[j] < arr[min]:\n"," min = j\n"," arr[i],arr[min] = arr[min],arr[i]\n"," print(arr)"],"metadata":{"id":"SdQox1FOh7EJ"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["selection_sort([4,6,2,1,8,7])"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"Gh90hIKPbL9n","executionInfo":{"status":"ok","timestamp":1750776738400,"user_tz":-330,"elapsed":11,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"12f0ae76-c517-4174-b8f3-55de85b234e8"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["[1, 2, 4, 6, 7, 8]\n"]}]},{"cell_type":"code","source":["#insertion sort\n","# no. of pass = n-1\n","# no of comparison = n(n-1)/2 -> o(n)^2\n","# no of swaps = o(n)^2\n","# Time Complexity --> Best case = O(N), avarage case = O(N)^2, worst case = O(N)^2\n","# Space complexity = O(1)\n","# Adaptive\n","# Stable\n","def insertion_sort(arr):\n","\n"," for i in range(0,len(arr)):\n"," j = i\n","\n"," while j>0 and arr[j-1] > arr[j]:\n"," arr[j-1],arr[j] = arr[j],arr[j-1]\n"," j -= 1\n","\n"," print(arr)"],"metadata":{"id":"tI6z2E9_bOfs"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["insertion_sort([7,10,4,2,6,9,8])"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"r6NsxOtZ_Tqm","executionInfo":{"status":"ok","timestamp":1750786607308,"user_tz":-330,"elapsed":14,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"ae8b5cfb-04b6-4b4a-da8e-a6df8b0f451f"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["[2, 4, 6, 7, 8, 9, 10]\n"]}]},{"cell_type":"code","source":["#merge sort(pyhton inbuilt tim-sort)\n","\n","#divide cost is o(1)\n","#making tree and go down while dividing cost is o(logn)\n","#conquer cost is o(n)\n","#Space complexity = if we use extra array merged then it will use more space so we will do changes inplace so o(n)\n","#Time complexity --> Best case = O(NlogN), avarage case = O(NlogN), worst case = O(NlogN)\n","# Not adaptive\n","# Stable\n","\n","def merge_sorted(arr1,arr2,arr):\n","\n"," i=j=k=0\n"," #merged = []\n","\n"," while i Best case = O(NlogN), avarage case = O(NlogN), worst case = O(N)^2\n","\n","def partition(arr, low, high):\n"," pivot = arr[high] # Choosing the last element as pivot\n"," i = low - 1 # Index of smaller element\n","\n"," for j in range(low, high):\n"," if arr[j] < pivot:\n"," i += 1\n"," arr[i], arr[j] = arr[j], arr[i] # Swap\n","\n"," arr[i + 1], arr[high] = arr[high], arr[i + 1] # Place pivot in correct position\n"," return i + 1\n","\n","def quick_sort(arr, low, high):\n"," if low < high:\n"," pi = partition(arr, low, high)\n","\n"," # Recursively sort elements before and after partition\n"," quick_sort(arr, low, pi - 1)\n"," quick_sort(arr, pi + 1, high)\n","\n","# Test the code\n","arr = [8, 4, 7, 3, 10, 2]\n","print(\"Original array:\", arr)\n","\n","quick_sort(arr, 0, len(arr) - 1)\n","\n","print(\"Sorted array:\", arr)\n"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"APvGcsE5QLM4","executionInfo":{"status":"ok","timestamp":1750859955218,"user_tz":-330,"elapsed":69,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"6cd84153-52d1-48c8-a706-a49153d97999"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["Original array: [8, 4, 7, 3, 10, 2]\n","Sorted array: [2, 3, 4, 7, 8, 10]\n"]}]},{"cell_type":"code","source":["#count sort\n","#not a comparison based algo\n","#not feasible for larger k value\n","#time complexity = o(n+k) ~ o(n)\n","#space complexity = o(2n+k)\n","\n","def count_sort(arr):\n"," n = len(arr)\n"," k = max(arr)\n"," count = [0] * (k+1)\n"," b = [0] * n\n"," for i in range(n):\n"," count[arr[i]] += 1\n","\n"," for i in range(1,k+1):\n"," count[i] = count[i] + count[i-1]\n","\n"," for i in range(n-1,-1,-1):\n"," count[arr[i]] -= 1\n"," b[count[arr[i]]] = arr[i]\n","\n"," return b"],"metadata":{"id":"BM4VAKBfYrng"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["count_sort([9,4,2,5,7,3,2,4])"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"pDWHaf7khfLB","executionInfo":{"status":"ok","timestamp":1750863085120,"user_tz":-330,"elapsed":10,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"bde7e56a-56da-4cc9-db10-edb0af77677b"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[2, 2, 3, 4, 4, 5, 7, 9]"]},"metadata":{},"execution_count":30}]},{"cell_type":"code","source":["#count sort to handle negative\n","def count_sort(arr):\n"," if not arr:\n"," return arr\n","\n"," n = len(arr)\n"," min_val = min(arr) # For supporting negative numbers\n"," max_val = max(arr)\n"," k = max_val - min_val + 1 # Adjust range\n","\n"," count = [0] * k\n"," output = [0] * n\n","\n"," # Count frequencies\n"," for num in arr:\n"," count[num - min_val] += 1\n","\n"," # Cumulative count\n"," for i in range(1, k):\n"," count[i] += count[i - 1]\n","\n"," # Build output array (stable sort)\n"," for i in range(n - 1, -1, -1):\n"," count[arr[i] - min_val] -= 1\n"," output[count[arr[i] - min_val]] = arr[i]\n","\n"," return output"],"metadata":{"id":"8JdN5jH_hjiq"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["#radix sort\n","#not a comparison based\n","\n","def radix_sort(arr):\n"," n = len(arr)\n"," max_ele = max(arr)\n"," pos = 1\n"," k = 10 # radix base (for decimal system)\n","\n"," while max_ele // pos > 0:\n"," arr = countSort(arr, n, pos, k)\n"," pos *= k\n","\n"," return arr\n","\n","def countSort(a, n, pos, k):\n"," count = [0] * k\n"," output = [0] * n\n","\n"," # Step 1: Count frequency of digits at current position\n"," for i in range(n):\n"," index = (a[i] // pos) % 10\n"," count[index] += 1\n","\n"," # Step 2: Compute cumulative count\n"," for i in range(1, k):\n"," count[i] += count[i - 1]\n","\n"," # Step 3: Build output array (in reverse to make it stable)\n"," for i in range(n - 1, -1, -1):\n"," index = (a[i] // pos) % 10\n"," count[index] -= 1\n"," output[count[index]] = a[i]\n","\n"," return output\n"],"metadata":{"id":"unrubLF8DNEC"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["radix_sort([2,4,2,886,5,3,3,22,865])"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"0D5kVbqPMZ5_","executionInfo":{"status":"ok","timestamp":1750873954330,"user_tz":-330,"elapsed":25,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"27788eb5-7fad-4e27-fe87-1a47cf4e77d7"},"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[2, 2, 3, 3, 4, 5, 22, 865, 886]"]},"metadata":{},"execution_count":22}]},{"cell_type":"code","source":["#bucket sort\n","#Time complexity --> Best case = O(N + k), avarage case = O(N + k), worst case = O(N)^2\n","# Doesn’t work well for non-uniform data.\n","# You need to know the distribution of data.\n","# Doesn't naturally handle negative numbers unless mapped.\n","# for 0 to 1 data\n","\n","def bucket_sort(arr):\n"," n = len(arr)\n"," if n <= 1:\n"," return arr\n","\n"," # Create n empty buckets\n"," buckets = [[] for _ in range(n)]\n","\n"," # Put array elements in different buckets\n"," for num in arr:\n"," index = int(num * n) # assuming input in [0, 1)\n"," buckets[index].append(num)\n","\n"," # Sort each bucket and concatenate\n"," sorted_array = []\n"," for bucket in buckets:\n"," sorted_array.extend(sorted(bucket)) # You can use insertion sort here too\n","\n"," return sorted_array\n","\n","# Example\n","arr = [0.23, 0.12, 0.67, 0.34, 0.89, 0.45]\n","print(\"Sorted:\", bucket_sort(arr))"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"oL6W9fFDMgUO","executionInfo":{"status":"ok","timestamp":1750874224698,"user_tz":-330,"elapsed":39,"user":{"displayName":"Dharmin Rajkotiya","userId":"02854726342790042019"}},"outputId":"ff1734fa-f09a-4158-ddc6-bd7833137224"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["Sorted: [0.12, 0.23, 0.34, 0.45, 0.67, 0.89]\n"]}]},{"cell_type":"code","source":["def shell_sort(arr):\n"," n = len(arr)\n"," gap = n // 2\n","\n"," while gap > 0:\n"," for i in range(gap, n):\n"," temp = arr[i]\n"," j = i\n","\n"," while j >= gap and arr[j - gap] > temp:\n"," arr[j] = arr[j - gap]\n"," j -= gap\n","\n"," arr[j] = temp\n"," gap //= 2\n","\n"," return arr\n","\n","# Example\n","arr = [19, 22, 63, 105, 2, 46]\n","print(\"Sorted:\", shell_sort(arr))\n"],"metadata":{"id":"WpWB_upoPHYK"},"execution_count":null,"outputs":[]},{"cell_type":"code","source":["#heap sort\n","#binary tree\n","#graph"],"metadata":{"id":"Lo7BtwxqRYZS"},"execution_count":null,"outputs":[]}]}

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

DSA Using Python.ipynb

Latest commit

History

DSA Using Python.ipynb

File metadata and controls