DATA STRUCTURES IMPLEMENTATION - PYTHON

Table of Contents
1. Linked List ..................................................................................................................................................... 2
1.1 Singly Linked List (SLL)............................................................................................................................. 2
1.2 Doubly Linked List (DLL) ......................................................................................................................... 4
2. Stack............................................................................................................................................................. 6
2.1 Using LinkedList (Node) .......................................................................................................................... 6
2.2 Using List .................................................................................................................................................. 7
3. Queue .......................................................................................................................................................... 8
3.1 Using LinkedList ....................................................................................................................................... 8
3.2 Using Two Stacks .................................................................................................................................... 9
3.3 Using Deque ......................................................................................................................................... 10
4. Binary Search Tree (BST) ........................................................................................................................... 11
4.1 Using Node class .................................................................................................................................. 11
5. Heap ........................................................................................................................................................... 13
5.1 Max Heap ............................................................................................................................................. 13
5.2 Min Heap .............................................................................................................................................. 14
6. Graph ......................................................................................................................................................... 15
7. Trie .............................................................................................................................................................. 16
8. Matrix.......................................................................................................................................................... 17
9. Sorting Algorithms ..................................................................................................................................... 19
9.1 Bubble Sort ........................................................................................................................................... 19
9.2 Selection Sort........................................................................................................................................ 19
9.3 Insertion Sort ......................................................................................................................................... 19
9.4 Merge Sort ............................................................................................................................................ 20
9.5 Quick Sort ............................................................................................................................................. 20
9.6 Radix Sort .............................................................................................................................................. 20
9.7 Heap Sort .............................................................................................................................................. 20

JOYDEEP BASU
(For more, please visit my career site)
 Ref: [Link]
1. Linked List
1.1 Singly Linked List (SLL)
# Create a Singly LinkedList with below Properties ([Link],[Link],[Link])
# methods ([Link],[Link],[Link],[Link],[Link],[Link],[Link],[Link],[Link])
import treevizer
class Node:
def __init__(self,val):
[Link] = val
[Link] = None

class SinglyLinkedList:
def __init__(self):
[Link] = None
[Link] = None
[Link] = 0

def print(self):
treevizer.to_png([Link], structure_type="ll", dot_path="[Link]",
png_path="[Link]")

def push(self,nval):
nd = Node(nval)
if [Link] is None:
[Link] = nd
[Link] = [Link]
else:
[Link] = nd
[Link] = nd
[Link] +=1

def pop(self):
if [Link] == 0: return None
if [Link] == 1:
[Link] = None
[Link] = None
else:
cNode = [Link]
for x in range(1, [Link]-1):
cNode = [Link]
[Link] = cNode
[Link] =None

[Link] -=1
return self

def get(self, index):

if [Link] > index and index >= 0:
cNode = [Link]
if index == 0: return [Link]
for x in range(1, index+1):
cNode = [Link]
return [Link]
return None

Page 2
 Ref: [Link]
def set(self, index,nval):
if [Link] > index and index >= 0:
cNode = [Link]
if index == 0:
[Link] = nval
return True
for x in range(1, index+1):
cNode = [Link]
[Link] = nval
return True
return False

def reverse(self):
prevNode, curNode = None, [Link]
[Link] = curNode
while (curNode):
nextNode = [Link]
[Link] = prevNode
prevNode = curNode
curNode = nextNode
[Link] = prevNode

def reversePos(self,start,end):
if start > 0 and end <[Link] -1:
sNode = eNode = [Link]
for x in range(1,start):
sNode = [Link]
for x in range(1,end+1):
eNode = [Link]

headNode = sNode
tailNode = [Link]

prevNode = tailNode
curNode = [Link]
while(curNode is not tailNode):
nextNode = [Link]
[Link] = prevNode
prevNode = curNode
curNode = nextNode
[Link] = prevNode

def printSll(self):
cNode = [Link]
lst = []
while(cNode):
[Link]([Link])
cNode = [Link]
print(lst)

if __name__ == '__main__':
sll = SinglyLinkedList()
for x in range(1,11): [Link](x)
[Link]()

[Link]()
[Link](1,7)
[Link]()
print('Head [', [Link],']')
print('Tail [',[Link],']')

Page 3
 Ref: [Link]
1.2 Doubly Linked List (DLL)
# Create a Doubly LinkedList with below properties ([Link],[Link],[Link])
# Problem: DLL FLattening with ChildDLLs or SubChildDLLs
import treevizer

class Node:
def __init__(self,val=None):
[Link] = None
[Link] = None
[Link] = val
[Link] = None

class DoublyLinkedList:
def __init__(self):
[Link] = None
[Link] = None
[Link] = 0

def print(self):
treevizer.to_png([Link], structure_type="ll", dot_path="[Link]",
png_path="[Link]")

def addChildDLL(self,index,chlDLL):
if index<0 or index>[Link]-1: return None
if index==0:
cNode = [Link]
elif index==[Link]-1:
cNode = [Link]
else:
cNode = [Link]
for x in range(1,index+1): cNode = [Link]

[Link] = [Link]

def flattenDLL(self):
psNode = [Link]
while(psNode):
if [Link] is not None:
peNode = [Link]
csNode = [Link]
while(csNode): ceNode = csNode; csNode = [Link]
# ------------------------
[Link] = [Link]
[Link] = psNode
# ------------------------
[Link] = peNode
[Link] = ceNode
# ------------------------
[Link] = None
#-------------------------
psNode = [Link]

Page 4
 Ref: [Link]

def push(self,nval):
nd = Node(nval)
if [Link] is None:
[Link] = nd
[Link] = [Link]
else:
[Link] = nd
[Link] = [Link]
[Link] = nd
[Link] +=1

def printDll(self):
# nd=[Link]
# while nd: print([Link],end='<->'); nd=[Link]
# print("\n")
print([Link]([Link]))

def buildMap(self,pNode):
tempMap = {}
while(pNode):
if [Link] is not None:
tempMap[[Link]] = [Link]([Link])
else:
tempMap[[Link]] = {}
pNode = [Link]
return tempMap

if __name__ == '__main__':
dll = DoublyLinkedList(); dll1 = DoublyLinkedList(); dll3 = DoublyLinkedList()
dll11 = DoublyLinkedList(); dll33 = DoublyLinkedList()

for x in range(0,10): [Link](x)

for x in range(10,15): [Link](x)
for x in range(30,40): [Link](x)
for x in range(120,125): [Link](x)
for x in range(330,333): [Link](x)

[Link](2,dll11)
[Link](3,dll33)
[Link](1,dll1); [Link](3,dll3)

[Link]()
[Link]() # DLL Flattening Test
[Link]()

Page 5
 Ref: [Link]
2. Stack
2.1 Using LinkedList (Node)
class Node:
def __init__(self, value):
[Link] = value
[Link] = None

class Stack:
def __init__(self):
[Link] = None
[Link] = 0

def is_empty(self):
return [Link] is None

def push(self, value):

nd = Node(value)
[Link] = [Link]
[Link] = nd
[Link]+=1

def pop(self):
if [Link] is None: return None
value = [Link]
[Link] = [Link]
[Link] -= 1
return value

def peek(self):
if [Link] is None: return None
return [Link]

def length(self): return [Link]

def print(self):
cnode = [Link]
while cnode:
print([Link],end=" -> ")
cnode=[Link]
print("None")

if __name__ == '__main__':
stk = Stack()
for i in range(1,11,2): [Link](i)
[Link]()
[Link](100)
[Link]()
print([Link]())
print([Link]())
[Link]()
[Link]()
while [Link](): val = [Link](); print(val)

Page 6
 Ref: [Link]

2.2 Using List

class stack():
def __init__(self):
[Link] = []
[Link] = 0

def push(self,val):
[Link](val)
[Link] = len([Link])

def pop(self):
[Link]()
[Link] = len([Link])

def peek(self):
if [Link] >0:
return ([Link][[Link] - 1])
else:
return None

def lookup(self, val):

print([Link](val)) if val in [Link] else print('Not found')

def printStack(self):
print([Link])

if __name__ == "__main__":
stk = stack()
[Link]('Joy')
[Link]('deep')
[Link]('Basu')
[Link]('Basu')
print([Link]())
[Link]()
print([Link]())

Page 7
 Ref: [Link]
3. Queue
3.1 Using LinkedList
class Node:
def __init__(self,val):
[Link] = val
[Link] = None

class Queue:
def __init__(self):
[Link] = None
[Link] = None
[Link] = 0

def enqueue(self,val):
nd = Node(val)
if ([Link] is None):
[Link] = nd
[Link] = [Link]
else:
[Link] = nd
[Link] = nd
[Link] +=1

def dequeue(self):
if [Link] == 0: return None
val = [Link]
if [Link]:
[Link] = [Link]
else:
[Link] = None
[Link] = None
[Link] -= 1
return val

def peek(self):
return [Link] if [Link] else None

# ---------------- Optional -----------------------

def printQ(self):
if [Link] == 0: return None
cNode = [Link]
while(cNode):
print([Link], end=' <- ')
cNode = [Link]
print('\n')

if __name__ == '__main__':
q = Queue()
[Link]('Joy'); [Link]('Deep'); [Link]('Basu')
print([Link]())
[Link]()

print([Link]());print([Link]());print([Link]());print([Link]());print([Link]
eue());
[Link]()
[Link]('Joy'); print([Link]()); print([Link])
print([Link]('Basu'))

Page 8
 Ref: [Link]
3.2 Using Two Stacks
class queueFromStack():
def __init__(self):
self.stk1 = [] # stack enqueue or push operation
self.stk2 = [] # stack dequeue or pop operation
[Link] = 0

def isEmpty(self):
return [Link]==0

def enqueue(self,item):
[Link](item)
[Link] +=1

def dequeue(self):
if [Link]==0: return None
if not self.stk2:
while self.stk1: [Link]([Link]())
[Link] -=1
return [Link]()

def peek(self):
if [Link] == 0: return None
if not self.stk2:
while self.stk1: [Link]([Link]())
return self.stk2[-1]

def print(self):
print(" <- ".join(self.stk1))

if __name__ == '__main__':
qs = queueFromStack()
for i in range(3): [Link](i)
print("Stack1: ", qs.stk1, "\nStack2: ", qs.stk2)
print([Link]())
print("Stack1: ", qs.stk1, "\nStack2: ", qs.stk2)
print([Link]())
[Link](3);
[Link](4);
print("Stack1: ", qs.stk1, "\nStack2: ", qs.stk2)
print([Link]())
print("Stack1: ", qs.stk1, "\nStack2: ", qs.stk2)
print([Link]())
print("Stack1: ", qs.stk1, "\nStack2: ", qs.stk2)
print([Link]())
print("Stack1: ", qs.stk1, "\nStack2: ", qs.stk2)
print([Link]())
print("Stack1: ", qs.stk1, "\nStack2: ", qs.stk2)
print([Link]())
print("Stack1: ", qs.stk1, "\nStack2: ", qs.stk2)
##############################################
for i in range(3): [Link](i)
[Link]()
print([Link]())
print([Link]())

Page 9
 Ref: [Link]
3.3 Using Deque
from collections import deque

class Queue:
def __init__(self):
self.q = deque()

def enqueue(self, item):

[Link](item)

def dequeue(self):
return [Link]() if self.q else None

def peek(self):
return self.q[0] if self.q else None

def lookup(self, key):

for item in self.q:
if item == key: return True
return False

def print(self): print("<-".join(map(str,self.q)))

q = Queue()
for x in range(1,10): [Link](x)
[Link]()
[Link](); print([Link]())
[Link]()
print([Link]())
print([Link](7))
print([Link]())

Page 10
 Ref: [Link]
4. Binary Search Tree (BST)
4.1 Using Node class
# Design a Binary Search Tree (BST) with methods
# 1. Insert, 2. Lookup, 3. Remove, 4. BFS, 5. DFS_InOrder, 6. DFS_PreOrder, 7.
DFS_PostOrder
from tree import drawTree
from collections import deque

class binaryNode:
def __init__(self, val):
[Link] = val
[Link] = None
[Link] = None
########################################################################
class binarySearchTree:
def __init__(self): [Link] = None
def print(self): drawTree([Link])

def insert(self, val):

bNode = binaryNode(val)
if [Link] is None: [Link] = bNode
curNode = [Link]
while curNode:
if [Link] == [Link]: return
if [Link] > [Link]:
if [Link]: curNode = [Link]; continue
[Link] = bNode; return
else:
if [Link]: curNode = [Link]; continue
[Link] = bNode; return

def search(self, val):

if [Link] is None: return None
curNode = [Link]
while curNode:
if [Link] == val: return curNode
if val > [Link]: curNode = [Link]; continue
if val < [Link]: curNode = [Link]; continue
return None

def remove(self, input_val): ## Not working ##

def helper(node, searchVal):
if node is None: return None
if searchVal < [Link]:
[Link] = helper([Link], searchVal)
elif searchVal > [Link]:
[Link] = helper([Link], searchVal)
else:
if [Link] is None: return [Link]
if [Link] is None: return [Link]
# Node with two children: Get the in-order successor (smallest in the
right subtree)
min_node = [Link]
while min_node.left: min_node = min_node.left
[Link] = helper(min_node, min_node.value)
return node

[Link] = helper([Link], input_val)

Page 11
 Ref: [Link]

def BFS(self):
q, arr = deque(), []
if [Link] is None: return []
[Link]([Link])
while q:
curNode = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
return arr

def DFS_InOrder(self):
def traverseInOrder(node, arr): # InOrder: Left Node (recursive) -> Parent Node
-> Right Node (recursive)
if [Link]: traverseInOrder([Link], arr)
[Link]([Link])
if [Link]: traverseInOrder([Link], arr)
return arr
return traverseInOrder([Link], []) # recursive call from stage

def DFS_PreOrder(self):
def traversePreOrder(node, arr): # PreOrder: Parent Node -> Left Node (R) ->
Right Node (R)
[Link]([Link])
if [Link]: traversePreOrder([Link], arr)
if [Link]: traversePreOrder([Link], arr)
return arr
return traversePreOrder([Link], []) # recursive call from stage

def DFS_PostOrder(self):
def traversePostOrder(node, arr): # PreOrder: Left Node (R) -> Right Node (R) -
> Parent Node
if [Link]: traversePostOrder([Link], arr)
if [Link]: traversePostOrder([Link], arr)
[Link]([Link])
return arr
return traversePostOrder([Link], []) # recursive call from stage

####################################################################

if __name__ == '__main__':
myBST = binarySearchTree()
for num in [20, 40, 8, 45, 43, 36, 19, 1, 47, 29, 42, 44, 30]: [Link](num)
# for num in [x for x in range(10)]: [Link](num)
[Link]()
# exit(0)
print('BFS list:', [Link]())
print('DFS In Order: ', myBST.DFS_InOrder())
print('DFS Pre Order: ', myBST.DFS_PreOrder())
print('DFS Post Order: ', myBST.DFS_PostOrder())
print('Looking up for value (28):', [Link](30))

for num in [40, 42, 20]: [Link](num)

[Link]()
print([Link]())

Page 12
 Ref: [Link]
5. Heap
5.1 Max Heap
from draw_arr2tree import arr2tree

class MaxHeap:
def __init__(self): [Link] = []

def insert(self,value):
[Link](value)
self._heapifyUp(len([Link])-1)

def extractMax(self):
if len([Link]) == 0: return None
if len([Link]) == 1: return [Link]()
maxVal = [Link][0]
[Link][0] = [Link]()
self._heapifyDown(0)
return maxVal

def Max_heapifyArr(self,arr):
[Link] = list(arr)
for index in range((len(arr)//2)-1,-1,-1): # reverse looping on "non-leaf"
nodes --> heapifyDown()
self._heapifyDown(index)

def _swapIndex(self, idx1, idx2): [Link][idx1], [Link][idx2] =

[Link][idx2], [Link][idx1]

def _heapifyUp(self,index): # Any child (left/right) to its parent comparison

pIndex = (index-1)//2
if index>0 and [Link][index] > [Link][pIndex]:
self._swapIndex(index,pIndex)
self._heapifyUp(pIndex)

def _heapifyDown(self,index): # parent to both children (left,right) comparison

largest = index
lcIndex, rcIndex = 2*index+1, 2*index+2
if lcIndex < len([Link]) and [Link][lcIndex] > [Link][largest]:
largest=lcIndex
if rcIndex < len([Link]) and [Link][rcIndex] > [Link][largest]: largest
= rcIndex
if index!=largest:
self._swapIndex(index, largest)
self._heapifyDown(largest)

def print(self): print([Link])

if __name__ == "__main__":
mxhp = MaxHeap()
mxhp.Max_heapifyArr([3, 8, 5, 2, 7, 6, 4, 1]); [Link](); arr2tree([Link])

[Link](0); [Link](); arr2tree([Link])

[Link](100); [Link](); arr2tree([Link])

print([Link]()); [Link](); arr2tree([Link])

print([Link]()); [Link](); arr2tree([Link])

Page 13
 Ref: [Link]
5.2 Min Heap
from draw_arr2tree import arr2tree

class MinHeap:
def __init__(self): [Link] = []

def insert(self,value):
[Link](value)
self._heapifyUp(len([Link])-1)

def extractMin(self):
if len([Link]) == 0: return None
if len([Link]) == 1: return [Link]()
minVal = [Link][0]
[Link][0] = [Link]()
self._heapifyDown(0)
return minVal

def Min_heapifyArr(self,arr):
[Link] = list(arr)
for index in range((len(arr)//2)-1,-1,-1): # reverse looping on "non-leaf"
nodes --> heapifyDown()
self._heapifyDown(index)

def _swapIndex(self, idx1, idx2): [Link][idx1], [Link][idx2] =

[Link][idx2], [Link][idx1]

def _heapifyUp(self,index): # Any child (left/right) to its parent comparison

pIndex = (index-1)//2
if index>0 and [Link][index] < [Link][pIndex]:
self._swapIndex(index,pIndex)
self._heapifyUp(pIndex)

def _heapifyDown(self,index): # parent to both children (left,right) comparison

smallest = index
lcIndex, rcIndex = 2*index+1, 2*index+2
if lcIndex < len([Link]) and [Link][lcIndex] < [Link][smallest]:
smallest=lcIndex
if rcIndex < len([Link]) and [Link][rcIndex] < [Link][smallest]:
smallest = rcIndex
if index!=smallest:
self._swapIndex(index, smallest)
self._heapifyDown(smallest)

def print(self): print([Link])

if __name__ == '__main__':
mnhp = MinHeap()
mnhp.Min_heapifyArr([3,8,5,2,7,6,4,1]); [Link](); arr2tree([Link])

[Link](0); [Link](); arr2tree([Link])

[Link](100); [Link](); arr2tree([Link])

print([Link]()); [Link](); arr2tree([Link])

print([Link]()); [Link](); arr2tree([Link])

Page 14
 Ref: [Link]
6. Graph
class graph:
def __init__(self): [Link] = {}
def print(self): print([Link])
def sort(self): return {k:v for k,v in sorted([Link]())}

def addVertex(self, key):

if key not in [Link]: [Link][key] = []

def removeVertex(self, key):

if key in [Link]: # removing the node
[Link](key)
for v in [Link]: # Removing all connections of deleted node
if key in [Link][v]: [Link][v].remove(key)

def addEdge(self, fromKey, toKey):

if fromKey == toKey: return
if fromKey in [Link] and toKey in [Link]:
[Link][fromKey].append(toKey)
[Link][toKey].append(fromKey)

def deleteEdge(self, fromKey, toKey):

if fromKey == toKey: return None
if fromKey in [Link] and toKey in [Link]:
if toKey in [Link][fromKey]: [Link][fromKey].remove(toKey)
if fromKey in [Link][toKey]: [Link][toKey].remove(fromKey)

def BFS(self):
q, arr, visited = Queue(), [], []
[Link](min([Link]()))
node = None
while [Link] > 0:
node = [Link]()
[Link](node); [Link](node)
for key in [Link][node]:
if key not in visited: [Link](key)
return print('BFS order: ', arr)

def DFS(self):
def traversalDFS(node, arr, visited):
if node not in visited:
[Link](node); [Link](node)
for key in [Link][node]: traversalDFS(key, arr, visited)
return arr
return print('DFS order:',traversalDFS(min([Link]()),[],[]))

if __name__ == '__main__':
grp = graph()
[Link](10); [Link](100); [Link]()
[Link](100); [Link](89); [Link]()

for item in [0, 1, 2, 3, 4, 5, 6, 7, 8]: [Link](item)

[Link](0, 1); [Link](0, 3); [Link](3, 2); [Link](3, 4)
[Link](3, 5); [Link](2, 8); [Link](4, 6); [Link](6, 7)
[Link](); [Link](4, 100); [Link](4); [Link]()

sgrp = [Link](); print(f"Sorted Graph: {sgrp}")

[Link](); [Link]()

Page 15
 Ref: [Link]
7. Trie
import treevizer
class TrieNode:
def __init__(self,val,stop=False):
[Link]={}
[Link] = val
[Link] = False

class Trie:
def __init__(self):
[Link]=TrieNode(val="")
[Link]=0 # This tracks the total number of nodes of a Trie
[Link] = 0 # This tracks unique keys/words count of a Trie

def print(self): treevizer.to_png([Link], structure_type="trie",

dot_path="[Link]", png_path="[Link]")
def wordsCount (self): return [Link]

########################################################################
def insert(self,word):
node = [Link]
for ch in word:
if ch not in [Link]: [Link][ch] = TrieNode(ch); [Link]+=1
node=[Link][ch]
if not [Link]: [Link]=True; [Link] += 1

####################### Word/Prefix search ########################

def search(self,key,type):
node = [Link]
for ch in key:
if ch not in [Link]: return False
node=[Link][ch]
# if type='prefix' always True returned, but for word search [Link] value is
returned
return [Link] if type=='word' else True

#################################################################
def delete(self,key):
stack, node = [], [Link]
for ch in key:
if ch not in [Link]: return False
node=[Link][ch]
[Link](node)
if [Link]: [Link] = False; [Link] -=1
if [Link]: return

# to recursively delete parent node hierarchy if no siblings/other key found in

the hierarchy
[Link](0,[Link])
while stack:
node = [Link]()
pNode = stack[-1]
del [Link][[Link]]; [Link] -=1
# exit loop if siblings ([Link]) or other key ([Link]) is
present
if (pNode is [Link]) or [Link] or [Link]: return

################## Autofill Suggestions ##########################

def autofill_suggestions(self,startswith):
node, stack, suggestions = [Link],[],[]

Page 16
 Ref: [Link]
for ch in startswith:
if ch not in [Link]: return []
node = [Link][ch]

for ch in [Link]: [Link](("",[Link][ch]))

while stack:
prefix, node = [Link]()
prefix += [Link]
if [Link]: [Link](prefix)
for ch in [Link]: [Link]((prefix, [Link][ch]))
return suggestions
###############################################################################

if __name__ == '__main__':
t = Trie()
for wd in
['Cap','Capstone1','Capstone2','Capstone3','Capital','Caps','Caterpillar']: [Link](wd)
[Link]()

print(f"Word (Capstone) search: {[Link]('Capstone', 'word')}")

print(f"Word (Capstone1) search: {[Link]('Capstone1', 'word')}")
print(f"Prefix/Starts_with (Capta) search: {[Link]('Capta', 'prefix')}")
print(f"Prefix/Starts_with (Capita) search: {[Link]('Capita', 'prefix')}")

print(f"Distinct Key count: {[Link]()}")

print(f"Total Node count: {[Link]}")
print(f"Prompting that starts with: 'Cap' >> {t.autofill_suggestions('Cap')}")

[Link]('Capital'); [Link]()

# print([Link]('Cats'))
# print([Link]('Catz'))
# print([Link])

8. Matrix
class Matrix:
def __init__(self, rows, cols):
[Link] = rows
[Link] = cols
[Link] = [[0 for _ in range(cols)] for _ in range(rows)]

def get(self, row, col):

if 0 <= row < [Link] and 0 <= col < [Link]:
return [Link][row][col]
return None

def set(self, row, col, value):

if 0 <= row < [Link] and 0 <= col < [Link]:
[Link][row][col] = value
else:
print("Index out of bounds")

Page 17
 Ref: [Link]
def transpose(self):
# Time Complexity: O(rows * cols)
transposed_matrix = Matrix([Link], [Link])
for i in range([Link]):
for j in range([Link]):
transposed_matrix.set(j, i, [Link][i][j])
return transposed_matrix

def add(self, other_matrix):

# Time Complexity: O(rows * cols)
if [Link] != other_matrix.rows or [Link] != other_matrix.cols:
print("Matrix dimensions do not match for addition.")
return None

result_matrix = Matrix([Link], [Link])

for i in range([Link]):
for j in range([Link]):
result_matrix.set(i, j, [Link][i][j] + other_matrix.get(i, j))
return result_matrix

def multiply(self, other_matrix):

# Time Complexity: O([Link] * [Link] * other_matrix.cols)
if [Link] != other_matrix.rows:
print("Matrix dimensions are not compatible for multiplication.")
return None

result_matrix = Matrix([Link], other_matrix.cols)

for i in range([Link]):
for j in range(other_matrix.cols):
dot_product = 0
for k in range([Link]):
dot_product += [Link][i][k] * other_matrix.get(k, j)
result_matrix.set(i, j, dot_product)
return result_matrix

def display(self):
for row in [Link]:
print(row)

# Example usage:
matrix1 = Matrix(2, 3)
[Link](0, 0, 1)
[Link](0, 1, 2)
[Link](0, 2, 3)
[Link](1, 0, 4)
[Link](1, 1, 5)
[Link](1, 2, 6)

matrix2 = Matrix(3, 2)
[Link](0, 0, 7)
[Link](0, 1, 8)
[Link](1, 0, 9)
[Link](1, 1, 10)
[Link](2, 0, 11)
[Link](2, 1, 12)

result = [Link](matrix2)
[Link]()

Page 18
 Ref: [Link]
9. Sorting Algorithms
9.1 Bubble Sort
def bubbleSort(self, arr):
for x in range(0, len(arr) - 1): # Outer loop to reduce right boundary of inner
loop by 1
end = len(arr)
for pt in range(1, end): # Inner loop to compare adjacent elements (always
checks from beginning)
if arr[pt - 1] > arr[pt]:
arr[pt - 1], arr[pt] = arr[pt], arr[pt - 1] # Swapping adjacent
elements
end = end - 1
return arr

9.2 Selection Sort

def selectionSort(self, arr):
for pt1 in range(0, len(arr) - 1): # Outer loop to increase left boundary of inner
loop by 1
smallest = pt1 # pt1 starts with 0, then increases until length of array - 1
for pt2 in range(pt1 + 1, len(arr)): # loop to find the smallest number after
arr[pt1] to replace with arr[pt1]
if arr[pt2] < arr[smallest]: smallest = pt2
if arr[smallest] < arr[pt1]:
arr[pt1], arr[smallest] = arr[smallest], arr[pt1]
return arr

9.3 Insertion Sort

def insertionSort(self, arr):
for pt1 in range(1, len(arr)):
for pt2 in range(0, pt1):
if arr[pt1] < arr[pt2]:
[Link](pt2, [Link](pt1))
break
return arr

Page 19
 Ref: [Link]
9.4 Merge Sort
def mergeSort(self, arr):
def merge(lArr, rArr):
lpt, rpt, result = 0, 0, []
while (lpt < len(lArr) and rpt < len(rArr)):
if lArr[lpt] < rArr[rpt]:
[Link](lArr[lpt]); lpt += 1
else:
[Link](rArr[rpt]); rpt += 1
while (lpt < len(lArr)): [Link](lArr[lpt]); lpt += 1
while (rpt < len(rArr)): [Link](rArr[rpt]); rpt += 1
return result
#-----------------------------------------------------------------------------------
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = [Link](arr[0:mid])
right = [Link](arr[mid:])
return merge(left, right)

9.5 Quick Sort

def quickSort(self, arr):
if len(arr) <= 1: return arr
leftArr, rightArr, pivot = [], [], [Link]()
for x in arr: [Link](x) if x < pivot else [Link](x)
return [Link](leftArr) + [pivot] + [Link](rightArr)

9.6 Radix Sort

def radixSort(self, arr):
maxPos = max([len(str(y)) for y in arr])
def getDigit(num, pos): # Helper function to get digit of specified position
return 0 if len(str(num)) < pos else int(str(num)[len(str(num)) - pos])

for pos in range(1, maxPos + 1):

resDict = {x: [] for x in range(10)} # Resetting dictionary to empty list for
keys (0-9)
#####################################
while arr:
num = [Link](0)
resDict[getDigit(num, pos)].append(num) # Pop & add array element to dict
(arr positional values = dictionary key)
######################################
for key in resDict: arr = arr + resDict[key] # Re-adding elements to arr as per
dict key order
return arr

9.7 Heap Sort

def heapsort(self, arr):
n = len(arr)
[Link](arr)
return [[Link](arr) for i in range(n)]

Page 20