1.
Selection Sort
def selection_sort(arr):
for i in range(0, len(arr)-1):
min = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min]:
min = j
arr[i], arr[min] = arr[min], arr[i]
arr=[]
n=int(input("Enter the limit:"))
for i in range(0,n):
arr.append(int(input()))
selection_sort(arr)
print("Sorted array" , arr)
2.Bubble Sort
def bubble_sort(arr):
n=len(arr)
for i in range (n):
for j in range (0,n-i-1):
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
arr=[]
n=int(input("Enter the limit:"))
for i in range(n):
arr.append(int(input()))
result=bubble_sort(arr)
print("Sorted array" , arr)
3.Merge Sort
def merge_sort(arr, low, high):
if low >= high:
return
mid = (low + high)//2
merge_sort(arr, low, mid)
merge_sort(arr, mid + 1, high)
merge(arr, low, high, mid)
def merge(arr, low, high, mid):
left = arr[low:mid + 1]
right = arr[mid+1:high+1]
left_index = 0
right_index = 0
sorted_index = low
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
arr[sorted_index] = left[left_index]
left_index = left_index + 1
else:
arr[sorted_index] = right[right_index]
right_index = right_index + 1
sorted_index = sorted_index + 1
while left_index < len(left):
arr[sorted_index] = left[left_index]
left_index = left_index + 1
sorted_index = sorted_index + 1
while right_index < len(right):
arr[sorted_index] = right[right_index]
right_index = right_index + 1
sorted_index = sorted_index + 1
arr = [44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48]
print("The given list before performing the merge sort is: ", arr)
merge_sort(arr, 0, len(arr) -1)
print("The given list after performing the merge sort is:", arr)
4. Quick Sort
def quick_sort(arr,l,h):
if l < h:
pivot_index=partition(arr,l,h)
quick_sort(arr,l,pivot_index-1)
quick_sort(arr,pivot_index+1,h)
def partition(arr,l,h):
pivot=arr[l]
i=l+1
j=h
while True:
while i<=j and arr[j]>=pivot:
j=j-1
while i<=j and arr[i]<=pivot:
i=i+1
if i<j:
arr[i],arr[j]=arr[j],arr[i]
else:
break
arr[l],arr[j]=arr[j],arr[l]
return j
arr=[10,16,8,12,15,6,3,9,5]
quick_sort(arr,0,len(arr)-1)
print("Sorted array",arr)
5.Binary search
def binarySearch(lst,item,n):
low=0
high=n-1
while low <= high:
mid=(low+high)//2
if lst[mid]== item:
return mid
elif lst[mid]< item:
low=mid+1
else:
high=mid-1
return -1
lst=[]
n=int(input("Enter the number of elements :"))
for i in range (n):
ele=int(input())
lst.append(ele)
item=int(input("Enter the element to search:"))
result= binarySearch(lst,item,n)
if result !=-1:
print("Element present at the index :" + str(result))
else:
print ("Not found")
6. Linear search
def LinearSearch(lst,n,item):
for i in range (0,n):
if(lst[i]==item):
return i
return -1
lst=[]
n=int(input("Enter the number of elements :"))
for i in range (0,n):
ele=int(input())
lst.append(ele)
item=int(input("Enter the element to search:"))
result=LinearSearch(lst,n,item)
if (result==-1):
print("Element not found")
else:
print("Element found at index :",result)
6.Brute force
def brute_force(text,pattern):
n=len(text)
m=len(pattern)
for i in range(n-m+1):
j=0
while j<m and text[i+j]==pattern[j]:
j+=1
if j ==m:
return i
return -1
text =input("Enter the pattern:")
pattern=input("Enter thr patterm to be searched:")
n=brute_force(text,pattern)
if n==-1:
print("Pattern not found")
else:
print("Pattern found at loation",n+1)
7.Adjacency Matrix
class Graph:
# Initialize the matrix
def __init__(self, size):
self.adjMatrix = []
for i in range(size):
self.adjMatrix.append([0 for i in range(size)])
self.size = size
# Add edges
def add_edge(self, v1, v2):
if v1 == v2:
print("Same vertex %d and %d" % (v1, v2))
else:
self.adjMatrix[v1][v2] = 1
self.adjMatrix[v2][v1] = 1
# Remove edges
def remove_edge(self, v1, v2):
if self.adjMatrix[v1][v2] == 0:
print("No edge between %d and %d" % (v1, v2))
return
self.adjMatrix[v1][v2] = 0
self.adjMatrix[v2][v1] = 0
# Print matrix
def print_matrix(self):
for row in self.adjMatrix:
for val in row:
print(val, end=" ")
print()
def main():
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(0, 3)
print("The adjacency matrix of the Graph:")
g.print_matrix()
print()
print("The adjacency matrix of the Graph after removing the edge (0,2):")
g.remove_edge(0, 2)
g.print_matrix()
if __name__ == '__main__':
main()
7.BFS
def bfs_shortest_path(graph, start, goal):
# Queue for BFS
queue = [(start, [start])]
visited = [] # List to track visited nodes
while queue:
# Pop the first element from the queue
current, path = queue.pop(0)
# Check if we have already visited this node
if current in visited:
continue
# Mark the current node as visited
visited.append(current)
# Check if we reached the goal
if current == goal:
return path
# Explore neighbors
for neighbor in graph[current]:
if neighbor not in visited:
queue.append((neighbor, path + [neighbor]))
print(queue)
return None # Return None if there is no path
# Example graph as an adjacency list
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Finding the shortest path from A to F
start_node = 'A'
goal_node = 'F'
shortest_path = bfs_shortest_path(graph, start_node, goal_node)
if shortest_path:
print(f"The shortest path from {start_node} to {goal_node} is: {' -> '.join(shortest_path)}")
else:
print(f"There is no path from {start_node} to {goal_node}.")
7. DFS
def dfs(graph, source):
if source is None or source not in graph:
return "Please enter valid input"
path =[]
stack_val=[source]
while (len(stack_val) != 0):
s= stack_val.pop()
if s not in path:
path.append(s)
if s not in graph:
continue
for neighbor_node in graph [s]:
stack_val.append(neighbor_node)
return " ".join(path)
graph= { "A":["B","C","D"],
"B": ["E"],
"C": ["G","F"],
"D": ["H"],
"E": ["I"],
"F": ["J"],
"G": ["K"]}
print(dfs(graph,"A"))
8.Binary Search tree
class Node:
def __init__(self,data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data> self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
#Traversal Algorithm
def inorder(self , root):
res=[]
if root:
res = self.inorder(root.left)
res.append(root.data)
res=res+self.inorder(root.right)
return res
def preorder(self , root):
res=[]
if root:
res.append(root.data)
res = res+self.preorder(root.left)
res=res+self.preorder(root.right)
return res
def postorder(self , root):
res=[]
if root:
res = self.postorder(root.left)
res=res+self.postorder(root.right)
res.append(root.data)
return res
def print_tree(self):
if self.left:
self.left.print_tree()
print(self.data)
if self.right:
self.right.print_tree()
root= Node(43)
root.insert(34)
root.insert(74)
root.insert(21)
root.insert(18)
root.insert(30)
root.insert(65)
root.insert(14)
print("\nPreorder Traversal:")
print(root.preorder(root))
print("\nPostorder Traversal:")
print(root.postorder(root))
print("\nInorder Traversal:")
print(root.inorder(root))
9.Sum of subset
from itertools import combinations
def sumsubset (n,arr,x):
for i in range(1,n):
for subset in combinations (arr,i):
if sum(subset)==x:
print(list(subset))
arr=[1,9,7,5,18,12,20,15]
x=35
n=len(arr)
sumsubset(n,arr,x)
10. Sequential file
file=open("name.txt","w+")
l1=[]
for i in range(5):
nm=input("Enter the name:")
l1.append(nm+"\n")
file.writelines(l1)
print("Names Written Successfully")
file.seek(0)
names=file.readlines()
print("The contents of the file are:")
for i in names:
print(i.strip())
nser=input("Enter the name to be searched :")
for i in names:
val=i.strip()
if val ==nser:
print("Name",nser," found in the file")
break
else:
print("Name",nser,"not found in the file")
