Skip to content

Instantly share code, notes, and snippets.

@amanuel2

amanuel2/AlgoImplement.ipynb

Created December 20, 2020 16:49
Show Gist options
  • Save amanuel2/7e18aa904e9d0ada3f1b7ea5ade2f5c1 to your computer and use it in GitHub Desktop.
Save amanuel2/7e18aa904e9d0ada3f1b7ea5ade2f5c1 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
AlgoImplement.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 189,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Original() [10, 6, 7, 5, 15, 17, 12]\n",
"Quicksort() [5, 6, 7, 10, 12, 15, 17]\n"
]
}
],
"source": [
"# Quicksort\n",
"\n",
"# Simple Swap\n",
"def swap(A,i,j):\n",
" A[i],A[j] = A[j],A[i]\n",
"\n",
"# Quicksort\n",
"def quicksort(A,l,r):\n",
" \n",
" # Partition method\n",
" def partition(A,l,r):\n",
" # pointers \n",
" i = l-1\n",
" pivot = A[r]\n",
" \n",
" # Main part\n",
" for j in range(l,r):\n",
" if A[j]<=pivot:\n",
" i+=1\n",
" swap(A,i,j)\n",
"\n",
" # New pivot\n",
" swap(A,i+1,r)\n",
" return i+1\n",
" \n",
" if l < r:\n",
" # parition based on pivot\n",
" pivot = partition(A,l,r)\n",
" quicksort(A,l,pivot-1)\n",
" quicksort(A,pivot+1,r)\n",
" \n",
"# Testing\n",
"from copy import deepcopy\n",
"arr = [10,6,7,5,15,17,12]\n",
"tmp = deepcopy(arr)\n",
"\n",
"quicksort(arr,0,len(arr)-1)\n",
"print(\"Original() \",tmp)\n",
"print(\"Quicksort()\",arr)"
]
},
{
"cell_type": "code",
"execution_count": 190,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Original() [10, 6, 7, 5, 15, 17, 12]\n",
"Mergesort() [5, 6, 7, 10, 12, 15, 17]\n"
]
}
],
"source": [
"# Mergesort\n",
"\n",
"# Simple Swap\n",
"def swap(A,i,j):\n",
" A[i],A[j] = A[j],A[i]\n",
" \n",
" \n",
"def mergesort(A,l,r):\n",
" def merge(A,l,m,r):\n",
" # vars\n",
" tmp = []\n",
" i,j=l,m+1\n",
"\n",
" # main loop\n",
" while i<=m and j<=r:\n",
" if A[i]<A[j]:\n",
" tmp.append(A[i])\n",
" i+=1\n",
" else:\n",
" tmp.append(A[j])\n",
" j+=1\n",
"\n",
" # edge cases\n",
" while i<=m:\n",
" tmp.append(A[i])\n",
" i+=1\n",
"\n",
" while j<=r:\n",
" tmp.append(A[j])\n",
" j+=1\n",
"\n",
" # update changes on main array\n",
" A[l:r+1]=tmp[0:(r+1)-l]\n",
" \n",
" if l<r:\n",
" # Parition in middle\n",
" m = (l+r)//2\n",
" left = mergesort(A,l,m)\n",
" right = mergesort(A,m+1,r)\n",
" merge(A,l,m,r)\n",
" \n",
"# Testing\n",
"from copy import deepcopy\n",
"arr = [10,6,7,5,15,17,12]\n",
"tmp = deepcopy(arr)\n",
"\n",
"mergesort(arr,0,len(arr)-1)\n",
"print(\"Original() \",tmp)\n",
"print(\"Mergesort()\",arr)"
]
},
{
"cell_type": "code",
"execution_count": 191,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"BuildHeap() [17, 15, 12, 5, 6, 7, 10]\n",
"Heapsort() [5, 6, 7, 10, 12, 15, 17]\n"
]
}
],
"source": [
"# Heapsort\n",
"\n",
"arr = [10,6,7,5,15,17,12]\n",
"\n",
"# simple swap func\n",
"def swap(arr,i,j):\n",
" arr[i],arr[j]=arr[j],arr[i]\n",
"\n",
"# Convert to Max-Heap\n",
"def buildheap(arr):\n",
" n = len(arr)//2\n",
" \n",
" for n in range(n,-1,-1):\n",
" # children\n",
" l = (2*n)+1\n",
" r = (2*n)+2\n",
" \n",
" # heapify-down\n",
" while(n<len(arr) and l<len(arr)):\n",
" m = 0\n",
" if r>= len(arr):\n",
" m = max(arr[n],arr[l])\n",
" else:\n",
" m = max(max(arr[n],arr[l]),arr[r])\n",
" \n",
" # parent is max element\n",
" if m == arr[n]:\n",
" break\n",
" \n",
" # left child is max elem\n",
" elif m == arr[l]:\n",
" swap(arr,n,l)\n",
" n = l\n",
" \n",
" # right child is max elem\n",
" elif m == arr[r]:\n",
" swap(arr,n,r)\n",
" n = r\n",
" \n",
" # re-structure\n",
" l = (2*n)+1\n",
" r = (2*n)+2\n",
"\n",
"buildheap(arr)\n",
"print(\"BuildHeap()\",arr)\n",
"\n",
"import copy\n",
"\n",
"# Heapsort (Need to build a max-heap first)\n",
"def heapsort(arr):\n",
" tmp = copy.deepcopy(arr)\n",
" res = []\n",
" \n",
" while(len(tmp)>1):\n",
" i,j = 0,len(tmp)-1\n",
" \n",
" # switch elements\n",
" swap(tmp,i,j)\n",
" res.append(tmp[-1])\n",
" tmp.pop()\n",
" \n",
" # heapify down from root\n",
" n = 0\n",
" l = (2*n)+1\n",
" r = (2*n)+2\n",
" \n",
" while(n<len(tmp) and l<len(tmp)):\n",
" m = 0\n",
" if r>=len(tmp):\n",
" m = max(tmp[n],tmp[l])\n",
" else:\n",
" m = max(max(tmp[n],tmp[l]),tmp[r])\n",
" \n",
" # parent is max\n",
" if m == tmp[n]:\n",
" break\n",
" \n",
" # left child is max\n",
" elif m == tmp[l]:\n",
" swap(tmp,n,l)\n",
" n = l\n",
" \n",
" # right child is max\n",
" else:\n",
" swap(tmp,n,r)\n",
" n = r\n",
" \n",
" # re-structure\n",
" l = (2*n)+1\n",
" r = (2*n)+2\n",
" \n",
" # add last elem\n",
" res+=tmp\n",
" \n",
" return res\n",
"\n",
"sort_lst = heapsort(arr)\n",
"print(\"Heapsort() \", list(reversed(sort_lst)))"
]
},
{
"cell_type": "code",
"execution_count": 192,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4\n",
"10\n",
"5\n",
"8\n",
"6\n"
]
}
],
"source": [
"# Breadth-First Search\n",
"\n",
"from collections import deque\n",
"import networkx as nx\n",
"\n",
"\n",
"\n",
"def bfs(grph, start, end, visited=set()):\n",
" # BFS revolves around Queue DS\n",
" queue = deque()\n",
" \n",
" # Appends inital value\n",
" queue.appendleft(start)\n",
" visited.add(start)\n",
" \n",
" # Main\n",
" while len(queue)>0:\n",
" \n",
" # Current Node being Proccessed\n",
" curr = queue.pop()\n",
" visited.add(curr)\n",
" print(curr)\n",
" \n",
" # We are done\n",
" if curr == end:\n",
" break\n",
" \n",
" # Add each non-visited nodes to the queue\n",
" for edge in grph.edges(curr):\n",
" edge = edge[1]\n",
" if edge not in visited:\n",
" queue.appendleft(edge)\n",
" visited.add(edge)\n",
" \n",
" \n",
" \n",
" \n",
" \n",
"G = nx.Graph()\n",
"G.add_node(4)\n",
"G.add_node(5)\n",
"G.add_node(3)\n",
"G.add_node(10)\n",
"G.add_node(6)\n",
"G.add_node(8)\n",
"G.add_node(9)\n",
"\n",
"G.add_edge(4, 10)\n",
"G.add_edge(4, 5)\n",
"\n",
"G.add_edge(5, 6)\n",
"G.add_edge(5, 3)\n",
"\n",
"G.add_edge(10, 8)\n",
"\n",
"G.add_edge(3, 6)\n",
"G.add_edge(3, 9)\n",
"\n",
"G.add_edge(8, 9)\n",
"G.add_edge(8, 6)\n",
"\n",
"G.add_edge(9, 6)\n",
"\n",
"bfs(G,4,6)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Graph\n",
"\n",
"<img src=\"https://i.imgur.com/TCElnDz.png\"/>"
]
},
{
"cell_type": "code",
"execution_count": 193,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4\n",
"10\n",
"8\n",
"9\n",
"6\n"
]
}
],
"source": [
"# Depth-First Search\n",
"\n",
"done = False\n",
"\n",
"def dfs(grph, start, end, visited=set()):\n",
" \n",
" # Outer variable\n",
" global done\n",
" if start in visited:\n",
" return\n",
" \n",
" # Current node being processed\n",
" curr = start\n",
" visited.add(curr)\n",
" print(curr)\n",
" \n",
" # We are done\n",
" if curr == end:\n",
" done = True\n",
" return\n",
" \n",
" # Recurse through all nodes not in visited\n",
" for edge in grph.edges(curr):\n",
" edge = edge[1]\n",
" if edge not in visited and not done:\n",
" dfs(grph,edge,end,visited)\n",
" \n",
"G = nx.Graph()\n",
"G.add_node(4)\n",
"G.add_node(5)\n",
"G.add_node(3)\n",
"G.add_node(10)\n",
"G.add_node(6)\n",
"G.add_node(8)\n",
"G.add_node(9)\n",
"\n",
"G.add_edge(4, 10)\n",
"G.add_edge(4, 5)\n",
"\n",
"G.add_edge(5, 6)\n",
"G.add_edge(5, 3)\n",
"\n",
"G.add_edge(10, 8)\n",
"\n",
"G.add_edge(3, 6)\n",
"# G.add_edge(3, 9)\n",
"\n",
"G.add_edge(8, 9)\n",
"G.add_edge(8, 6)\n",
"\n",
"# G.add_edge(9, 6)\n",
"\n",
"dfs(G,4,6)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Graph\n",
"<img src='https://i.imgur.com/V0hCJtC.png'/>"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.8.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment