Scribd
Upload
28 views23 pages

Search and Sort Algorithms Implementation

The document contains multiple examples of algorithm implementations, including linear search, binary search, pattern matching algorithms (naive, Rabin-Karp, KMP), sorting algorithms (insertion sort, heap sort), and graph algorithms (BFS, DFS, Dijkstra's, Prim's). Each example includes a program code, sample input, and output demonstrating the algorithm's functionality. The document also includes time complexity analysis through plotting execution times for various test cases.

Uploaded by

antonyshanthi.cse
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
28 views23 pages

Search and Sort Algorithms Implementation

The document contains multiple examples of algorithm implementations, including linear search, binary search, pattern matching algorithms (naive, Rabin-Karp, KMP), sorting algorithms (insertion sort, heap sort), and graph algorithms (BFS, DFS, Dijkstra's, Prim's). Each example includes a program code, sample input, and output demonstrating the algorithm's functionality. The document also includes time complexity analysis through plotting execution times for various test cases.

Uploaded by

antonyshanthi.cse
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

EX:NO: 1 IMPLEMENTATION OF LINEAR SEARCH

PROGRAM:
import numpy as np
import [Link] as plt
import time
times = []
a = []
n = int(input("Enter the number of test cases: "))
for i in range(n):
m = int(input("Enter the number of elements: "))
print("Array elements for test case", i + 1, ":")
for i in range(m):
ab = int(input())
[Link](ab)
key = int(input("Enter a key to search: "))
f=1
start = [Link]()
for i in range(len(a)):
if a[i] == key:
print("Key is found at index",i)
f=0
break
if(f==1):
print("Key is not found")
end = [Link]()
total = end - start
print("Total time taken:", total)
[Link](total)
[Link]()
[Link](range(0, n),times,label='Search Time')
[Link]('Test Case')
[Link]('Time (s)')
[Link]('Linear Search Time Complexity')
[Link]()
[Link]()

OUTPUT:
Enter the number of test cases: 4
Enter the number of elements: 3
Array elements for test case 1 :
1
5
3
Enter a key to search: 5
Key is found at index 1
Total time taken: 0.015625
Enter the number of elements: 4
Array elements for test case 2 :
5
7
3
4
Enter a key to search: 4
Key is found at index 3
Total time taken: 0.01550912857055664
Enter the number of elements: 5
Array elements for test case 3 :
6
7
1
4
3
Enter a key to search: 1
Key is found at index 2
Total time taken: 0.01564621925354004
Enter the number of elements: 2
Array elements for test case 4 :
5
6
Enter a key to search: 1
Key is not found
Total time taken: 0.0312497615814209
EX:NO:2 IMPLEMENTATION OF BINARY SEARCH
PROGRAM:
import numpy as np
import [Link] as plt
import time
times = []
arr = []
n = int(input("Enter the number of test cases: "))
for i in range(n):
m = int(input("Enter the number of elements: "))
print("Array elements for test case", i + 1, ":")
for i in range(m):
ab = int(input())
[Link](ab)
key = int(input("Enter a key to search: "))
start = [Link]()
def binary_search(arr, low, high, key):
if high >= low:
mid = (high + low) // 2
if arr[mid] == key:
return mid
elif arr[mid] > key:
return binary_search(arr, low, mid - 1, key)
else:
return binary_search(arr, mid + 1, high, key)
else:
return -1
result = binary_search(arr, 0, len(arr) - 1, key)
if result == -1:
print("Key is not found")
else:
print("Key is found at index", result)
end=[Link]()
total = end - start
print("Total time taken:", total)
[Link](total)
[Link]()
[Link](range(0, n), times,label='Search Time')
[Link]('Test Case')
[Link]('Time (s)')
[Link]('Recursive Binary Search Time Complexity')
[Link]()
OUTPUT:
Enter the number of test cases: 4
Enter the number of elements: 3
Array elements for test case 1 :
1
4
8
Enter a key to search: 4
Key is found at index 1
Total time taken: 0.01551365852355957
Enter the number of elements: 4
Array elements for test case 2 :
2
4
5
8
Enter a key to search: 8
Key is found at index 3
Total time taken: 0.015626192092895508
Enter the number of elements: 5
Array elements for test case 3 :
1
3
4
6
8
Enter a key to search: 1
Key is found at index 0
Total time taken: 0.01562809944152832
Enter the number of elements: 2
Array elements for test case 4 :
4
6
Enter a key to search: 6
Key is found at index 1
Total time taken: 0.01562643051147461
EX:NO:3 IMPLEMENTATION OF PATTERN MATCHING ALGORITHM
A)NAÏVE PATTERN MATCHING ALGORITHM:
PROGRAM:
def naive_pattern_search():
txt = input("Enter the text: ")
pat = input("Enter the pattern: ")
m = len(pat)
n = len(txt)
for i in range(n-m+1):
flag = True
for j in range(m):
if pat[j] != txt[i+j]:
flag = False
break
if flag:
print("Pattern found at index", i)
print("Example-1:")
naive_pattern_search()
print("Example-2:")
naive_pattern_search()
OUTPUT:
Example-1:
Enter the text: bacabadacababd
Enter the pattern: caba
Pattern found at index 2
Pattern found at index 8
Example-2:
Enter the text: adacdabdcab
Enter the pattern: abdca
Pattern found at index 5
B)RABIN-KARP ALGORITHM:
PROGRAM:
def hash_string(s):
p = 31
m = 10**9 + 9
hash_value = 0
p_pow = 1
for char in s:
hash_value = (hash_value + (ord(char) - ord('a') + 1) * p_pow) % m
p_pow = (p_pow * p) % m
return hash_value
def rabin_karp(text, pattern):
n = len(text)
m = len(pattern)
pattern_hash = hash_string(pattern)
text_hash = hash_string(text[:m])
for i in range(n - m + 1):
if pattern_hash == text_hash and text[i:i+m] == pattern:
print("Pattern found at index", i)
if i < n - m:
text_hash = (text_hash - (ord(text[i]) - ord('a') + 1) + (ord(text[i+m]) - ord('a') + 1)) %
(10**9 + 9)
text="AABAACAADAABAAABAA"
pattern="AABA"
rabin_karp(text,pattern)

OUTPUT:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
C) KNUTH MORRIS PRATT ALGORITHM:
PROGRAM:
def compute_lps_array(pattern):
m = len(pattern)
lps = [0] * m
length = 0
i=1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
lps = compute_lps_array(pattern)
i=0
j=0
while i < n:
if pattern[j] == text[i]:
i += 1
j += 1
if j == m:
print("Pattern found at index", i - j)
j = lps[j - 1]
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
text = "AABAACAADAABAAABAA"
pattern = "AABA"
kmp_search(text, pattern)
OUTPUT:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
EX:NO:4 IMPLEMENTATION OF INSERTION SORT AND HEAP SORT
A)INSEERTION SORT:
PROGRAM:
import numpy as np
import [Link] as plt
import time
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j = j- 1
arr[j + 1] = key
times = []
arr = []
n = int(input("Enter the number of test cases: "))
for i in range(n):
m = int(input("Enter the number of elements: "))
print("Array elements for test case", i + 1, ":")
for k in range(m):
ab = int(input())
[Link](ab)
start = [Link]()
insertion_sort(arr)
print("Sorted Array for test case", i + 1, ":", arr)
end=[Link]()
total = end - start
print("Total time taken:", total)
[Link](total)
[Link]()
[Link](range(1, n + 1), times, label='Sort Time')
[Link]('Test Case')
[Link]('Time (s)')
[Link]()
[Link]('Insertion Sort Time Complexity')
[Link]()
OUTPUT:
Enter the number of test cases: 4
Enter the number of elements: 3
Array elements for test case 1 :
5
2
1
Sorted Array for test case 1 : [1, 2, 5]
Total time taken: 0.0312504768371582
Enter the number of elements: 4
Array elements for test case 2 :
7
9
4
3
Sorted Array for test case 2 : [3, 4, 7, 9]
Total time taken: 0.031250715255737305
Enter the number of elements: 5
Array elements for test case 3 :
3
5
1
2
8
Sorted Array for test case 3 : [1, 2, 3, 5, 8]
Total time taken: 0.046903133392333984
Enter the number of elements: 6
Array elements for test case 4 :
1
2
3
4
5
6
Sorted Array for test case 4 : [1, 2, 3, 4, 5, 6]
Total time taken: 0.04687762260437012
B)HEAP SORT:
PROGRAM:
import numpy as np
import [Link] as plt
import time
def heapify(arr, n, i):
largest = i
l=2*i+1
r=2*i+2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
times = []
arr = []
n = int(input("Enter the number of test cases: "))
for i in range(n):
m = int(input("Enter the number of elements: "))
print("Array elements for test case", i + 1, ":")
for k in range(m):
ab = int(input())
[Link](ab)
start = [Link]()
heap_sort(arr)
print("Sorted Array for test case", i + 1, ":", arr)
end=[Link]()
total = end - start
print("Total time taken:", total)
[Link](total)
[Link]()
[Link](range(1, n + 1), times,label='Sort Time')
[Link]('Test Case')
[Link]('Time (s)')
[Link]('Heap Sort Time Complexity')
[Link]()

OUTPUT:
Enter the number of test cases: 4
Enter the number of elements: 3
Array elements for test case 1 :
5
3
1
Sorted Array for test case 1 : [1, 3, 5]
Total time taken: 0.03125143051147461
Enter the number of elements: 4
Array elements for test case 2 :
2
4
6
1
Sorted Array for test case 2 : [1, 2, 4, 6]
Total time taken: 0.031250953674316406
Enter the number of elements: 5
Array elements for test case 3 :
8
4
9
1
3
Sorted Array for test case 3 : [1, 3, 4, 8, 9]
Total time taken: 0.031250715255737305
Enter the number of elements: 6
Array elements for test case 4 :
1
2
3
4
5
6
Sorted Array for test case 4 : [1, 2, 3, 4, 5, 6]
Total time taken: 0.04687762260437012
EX:NO:5 IMPLEMENTATION OF BREADTH FIRST SEARCH
PROGRAM:
graph={14:[12,16],12:[11,13],16:[17],11:[],13:[17],17:[]}
visited=[]
queue=[]
def bfs(visited,graph,node):
[Link](node)
[Link](node)
while queue:
m=[Link](0)
print(m,end=" ")
for neighbour in graph[m]:
if neighbour not in visited:
[Link](neighbour)
[Link](neighbour)
print("Breadth-First Search:")
bfs(visited,graph,14)

OUTPUT:
Breadth-First Search:
14 12 16 11 13 17
EX:NO:6 IMPLEMENTATION OF DEPTH FIRST SEARCH
PROGRAM:
graph={14:[12,16],12:[11,13],16:[17],11:[],13:[17],17:[]}
visited=set()
def dfs(visited,graph,node):
if node not in visited:
print(node,end=" ")
[Link](node)
for neighbour in graph[node]:
dfs(visited,graph,neighbour)
print("Depth-First Search")
dfs(visited,graph,14)

OUTPUT:
Depth-First Search
14 12 11 13 17 16
EX:NO: 7 IMPLEMENTATION OF DIJKSTRA’S ALGORIHM
PROGRAM:
Inf=999
def Dijkstra(graph, start):
l = len(graph)
dist = [Inf for i in range(l)]
dist[start] = 0
vis = [False for i in range(l)]
for i in range(l):
u = -1
for x in range(l):
if not vis[x] and (u == -1 or dist[x]<dist[u]):
u=x
if dist[u] == Inf:
break
vis[u] = True
for v, d in graph[u]:
if dist[u] + d<dist[v]:
dist[v] = dist[u] + d
return dist
graph = {0: [(1, 1)],1: [(0, 1), (2, 2), (3, 3)],2: [(1, 2), (3, 1), (4, 5)],3: [(1, 3), (2, 1), (4, 1)],4:
[(2,5), (3, 1)]}
print(Dijkstra(graph,0))
OUTPUT:
[0, 1, 3, 4, 5]
EX:NO:8 IMPLEMENTATION OF PRIM’S ALGORITHM
PROGRAM:
INF = 9999999
V=5
G = [[0, 9, 75, 0, 0],[9, 0, 95, 19, 42],[75, 95, 0, 51, 66],[0, 19, 51, 0, 31],[0, 42, 66, 31, 0]]
selected = [0, 0, 0, 0, 0]
no_edge = 0
selected[0] = True
print("Edge : Weight")
while (no_edge <V - 1):
minimum = INF
x=0
y=0
for i in range(V):
if selected[i]:
for j in range(V):
if ((not selected[j]) and G[i][j]):
if minimum >G[i][j]:
minimum = G[i][j]
x=i
y=j
print(str(x) + "-" + str(y) + ":" + str(G[x][y]))
selected[y] = True
no_edge += 1
OUTPUT:
Edge : Weight
0-1:9
1-3:19
3-4:31
EX:NO:9 IMPLEMENTATION OF FLOYD WARSHALL ALGORITHM
PROGRAM:
nV = 4
INF = 999
def floyd_warshall(G):
distance = list(map(lambda i: list(map(lambda j: j, i)), G))
for k in range(nV):
for i in range(nV):
for j in range(nV):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)
def print_solution(distance):
for i in range(nV):
for j in range(nV):
if(distance[i][j] == INF):
print("INF", end=" ")
else:
print(distance[i][j], end=" ")
print(" ")
G = [[0, 3, INF, 5],[2, 0, INF, 4],[INF, 1, 0, INF],[INF, INF, 2, 0]]
floyd_warshall(G)
OUTPUT:
0375
2064
3105
5320
EX:NO:10 IMPLEMENTATION OF TRANSITIVE CLOSURE USING WARSHALL
ALGORITHM
PROGRAM:
def transitive_closure(graph):
n = len(graph)
closure = [row[:] for row in graph]
for k in range(n):
for i in range(n):
for j in range(n):
closure[i][j] = closure[i][j] or (closure[i][k] and closure[k][j])
return closure
graph = [[1, 1, 0, 1],[0, 1, 1, 0],[0, 0, 1, 1],[0, 0, 0, 1]]
transitive_closure_matrix = transitive_closure(graph)
print("Transitive Closure Matrix:")
for row in transitive_closure_matrix:
print(row)
OUTPUT:
Transitive Closure Matrix:
[1, 1, 1, 1]
[0, 1, 1, 1]
[0, 0, 1, 1]
[0, 0, 0, 1]
EX:NO:11 IMPLEMENTATION OF MINIMUM MAXIMUM ALGORITHM
PROGRAM:
def maxmin(arr, i, j):
global max_val, min_val
if i == j:
max_val = min_val = arr[i]
elif i == j - 1:
if arr[i] < arr[j]:
max_val = arr[j]
min_val = arr[i]
else:
max_val = arr[i]
min_val = arr[j]
else:
mid = (i + j) // 2
maxmin(arr, i, mid)
max1 = max_val
min1 = min_val
maxmin(arr, mid + 1, j)
if max_val < max1:
max_val = max1
if min_val > min1:
min_val = min1
n = int(input("Enter the total number of elements:"))
arr = []
for i in range(n):
a = int(input("Enter the numbers:"))
[Link](a)
max_val = min_val = arr[0]
maxmin(arr, 0, n - 1)
print("Minimum element in the array:", min_val)
print("Maximum element in the array:", max_val)
OUTPUT:
Enter the total number of elements: 5
Enter the numbers: 8
Enter the numbers: 4
Enter the numbers: 6
Enter the numbers: 2
Enter the numbers: 7
Minimum element in the array: 2
Maximum element in the array: 8
EX:NO:12 IMPLEMENTATION OF MERGE SORT AND QUICK SORT
A)MERGE SORT
PROGRAM:
import numpy as np
import [Link] as plt
import time
def merge_sort(arr):
if len(arr)> 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i=j=k=0
while i < len(L) and j < len(R):
if L[i]< R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
times = []
arr = []
n = int(input("Enter the number of test cases:"))
for i in range(n):
m = int(input("Enter the number of elements:"))
print("Array elements for test case", i + 1, ":")
for j in range(m):
ab = int(input())
[Link](ab)
start = [Link]()
merge_sort(arr)
print("Sorted Array for test case", i + 1,":", arr)
end = [Link]()
total = end - start
print("Total time taken:", total)
[Link](total)
[Link]()
[Link](range(1, n + 1), times)
[Link]('Test Case')
[Link]('Time (s)')
[Link]('Merge Sort Time Complexity')
[Link]()
OUTPUT:
Enter the number of test cases: 4
Enter the number of elements: 3
Array elements for test case 1 :
5
2
1
Sorted Array for test case 1 : [1, 2, 5]
Total time taken: 0.02977442741394043
Enter the number of elements: 4
Array elements for test case 2 :
5
9
3
6
Sorted Array for test case 2 : [3, 5, 6, 9]
Total time taken: 0.015626907348632812
Enter the number of elements: 5
Array elements for test case 3 :
4
9
3
7
2
Sorted Array for test case 3 : [2, 3, 4, 7, 9]
Total time taken: 0.03125429153442383
Enter the number of elements: 6
Array elements for test case 4 :
3
8
2
4
7
1
Sorted Array for test case 4 : [1, 2, 3, 4, 7, 8]
Total time taken: 0.03125166893005371
B)QUICK SORT
PROGRAM:
import numpy as np
import [Link] as plt
import time
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr):
stack = []
[Link]((0, len(arr) - 1))
while stack:
low, high = [Link]()
if low < high:
pi = partition(arr, low, high)
[Link]((low, pi - 1))
[Link]((pi + 1, high))
times = []
arr = []
n = int(input("Enter the number of test cases: "))
for i in range(n):
m = int(input("Enter the number of elements: "))
print("Array elements for test case", i + 1, ":")
for j in range(m):
ab = int(input())
[Link](ab)
start = [Link]()
quick_sort(arr)
print("Sorted Array for test case", i + 1, ":", arr)
end = [Link]()
total = end - start
print("Total time taken:", total)
[Link](total)
[Link]()
[Link](range(1, n + 1), times)
[Link]('Test Case')
[Link]('Time (s)')
[Link]('Quick Sort Time Complexity')
[Link]()
OUTPUT:
Enter the number of test cases: 4
Enter the number of elements: 3
Array elements for test case 1 :
5
2
1
Sorted Array for test case 1 : [1, 2, 5]
Total time taken: 0.015509843826293945
Enter the number of elements: 4
Array elements for test case 2 :
7
9
3
4
Sorted Array for test case 2 : [3, 4, 7, 9]
Total time taken: 0.015624523162841797
Enter the number of elements: 5
Array elements for test case 3 :
5
3
7
2
8
Sorted Array for test case 3 : [2, 3, 5, 7, 8]
Total time taken: 0.015618085861206055
Enter the number of elements: 6
Array elements for test case 4 :
2
4
5
3
7
1
Sorted Array for test case 4 : [1, 2, 3, 4, 5, 7]
Total time taken: 0.031130313873291016

You might also like