Algorithm Lab Programs in Python
1. Insertion Sort (with Number of Comparisons)
def insertion_sort(arr):
"""Performs insertion sort and returns (sorted_list, comparison_count)."""
a = arr[:] # work on a copy
n = len(a)
comps = 0
for i in range(1, n):
key = a[i]
j=i-1
# Count every comparison between a[j] and key, including the final failure
while j >= 0:
comps += 1
if a[j] > key:
a[j + 1] = a[j]
j -= 1
else:
break
a[j + 1] = key
return a, comps
2. Merge Sort (with Number of Comparisons)
def _merge(left, right):
"""Merge two sorted lists and return (merged, comparison_count)."""
i=j=0
merged = []
comps = 0
while i < len(left) and j < len(right):
comps += 1
if left[i] <= right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1
# Remaining elements (no comparisons)
[Link](left[i:])
[Link](right[j:])
return merged, comps
def merge_sort(arr):
"""Performs merge sort and returns (sorted_list, comparison_count)."""
n = len(arr)
if n <= 1:
return arr[:], 0
mid = n // 2
left, c1 = merge_sort(arr[:mid])
right, c2 = merge_sort(arr[mid:])
merged, c3 = _merge(left, right)
return merged, c1 + c2 + c3
3. Heap Sort (with Number of Comparisons)
def _heapify(a, n, i):
"""Heapify subtree rooted at index i; returns comparison_count."""
comps = 0
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n:
comps += 1
if a[left] > a[largest]:
largest = left
if right < n:
comps += 1
if a[right] > a[largest]:
largest = right
if largest != i:
a[i], a[largest] = a[largest], a[i]
comps += _heapify(a, n, largest)
return comps
def heap_sort(arr):
"""Performs heap sort and returns (sorted_list, comparison_count)."""
a = arr[:]
n = len(a)
comps = 0
# Build max-heap
for i in range(n // 2 - 1, -1, -1):
comps += _heapify(a, n, i)
# Extract elements from heap
for i in range(n - 1, 0, -1):
a[0], a[i] = a[i], a[0]
comps += _heapify(a, i, 0)
return a, comps
4. Quick Sort (with Number of Comparisons)
def _partition(a, low, high):
"""Lomuto partition; returns (partition_index, comparison_count)."""
pivot = a[high]
i = low - 1
comps = 0
for j in range(low, high):
comps += 1
if a[j] <= pivot:
i += 1
a[i], a[j] = a[j], a[i]
a[i + 1], a[high] = a[high], a[i + 1]
return i + 1, comps
def _quick_sort_rec(a, low, high):
if low >= high:
return 0
pi, c1 = _partition(a, low, high)
c2 = _quick_sort_rec(a, low, pi - 1)
c3 = _quick_sort_rec(a, pi + 1, high)
return c1 + c2 + c3
def quick_sort(arr):
"""Performs quick sort and returns (sorted_list, comparison_count)."""
a = arr[:]
comps = _quick_sort_rec(a, 0, len(a) - 1)
return a, comps
Experimental Driver for Algorithms 1–4
# Experimental comparison of average number of comparisons
import random
import math
import [Link] as plt
def random_array(n, low=0, high=100000):
return [[Link](low, high) for _ in range(n)]
def run_experiments():
sizes = list(range(30, 1001, 10))
avg_ins, avg_merge, avg_heap, avg_quick, theo_nlogn = [], [], [], [], []
for n in sizes:
total_ins = total_merge = total_heap = total_quick = 0
for _ in range(10):
arr = random_array(n)
_, c_ins = insertion_sort(arr)
_, c_merge = merge_sort(arr)
_, c_heap = heap_sort(arr)
_, c_quick = quick_sort(arr)
total_ins += c_ins
total_merge += c_merge
total_heap += c_heap
total_quick += c_quick
avg_ins.append(total_ins / 10.0)
avg_merge.append(total_merge / 10.0)
avg_heap.append(total_heap / 10.0)
avg_quick.append(total_quick / 10.0)
theo_nlogn.append(n * math.log2(n))
# Plotting
[Link]()
[Link](sizes, avg_ins, label='Insertion Sort')
[Link](sizes, avg_merge, label='Merge Sort')
[Link](sizes, avg_heap, label='Heap Sort')
[Link](sizes, avg_quick, label='Quick Sort')
[Link](sizes, theo_nlogn, label='n log n (Theoretical)', linestyle='--')
[Link]('Input Size (n)')
[Link]('Average Number of Comparisons')
[Link]('Average Comparisons vs Input Size')
[Link]()
[Link](True)
[Link]()
# To run the experiment and plot graphs:
# run_experiments()
5. Strassen’s Algorithm for Matrix Multiplication
def add_matrix(A, B):
n = len(A)
return [[A[i][j] + B[i][j] for j in range(n)] for i in range(n)]
def sub_matrix(A, B):
n = len(A)
return [[A[i][j] - B[i][j] for j in range(n)] for i in range(n)]
def strassen(A, B):
"""Strassen multiplication for square matrices of size power of 2."""
n = len(A)
if n == 1:
return [[A[0][0] * B[0][0]]]
k = n // 2
# Split A
A11 = [[A[i][j] for j in range(k)] for i in range(k)]
A12 = [[A[i][j] for j in range(k, n)] for i in range(k)]
A21 = [[A[i][j] for j in range(k)] for i in range(k, n)]
A22 = [[A[i][j] for j in range(k, n)] for i in range(k, n)]
# Split B
B11 = [[B[i][j] for j in range(k)] for i in range(k)]
B12 = [[B[i][j] for j in range(k, n)] for i in range(k)]
B21 = [[B[i][j] for j in range(k)] for i in range(k, n)]
B22 = [[B[i][j] for j in range(k, n)] for i in range(k, n)]
M1 = strassen(add_matrix(A11, A22), add_matrix(B11, B22))
M2 = strassen(add_matrix(A21, A22), B11)
M3 = strassen(A11, sub_matrix(B12, B22))
M4 = strassen(A22, sub_matrix(B21, B11))
M5 = strassen(add_matrix(A11, A12), B22)
M6 = strassen(sub_matrix(A21, A11), add_matrix(B11, B12))
M7 = strassen(sub_matrix(A12, A22), add_matrix(B21, B22))
C11 = add_matrix(sub_matrix(add_matrix(M1, M4), M5), M7)
C12 = add_matrix(M3, M5)
C21 = add_matrix(M2, M4)
C22 = add_matrix(sub_matrix(add_matrix(M1, M3), M2), M6)
# Combine quadrants
C = [[0] * n for _ in range(n)]
for i in range(k):
for j in range(k):
C[i][j] = C11[i][j]
C[i][j + k] = C12[i][j]
C[i + k][j] = C21[i][j]
C[i + k][j + k] = C22[i][j]
return C
6. Counting Sort
def counting_sort(arr, max_val=None):
"""Counting sort for non-negative integers."""
if not arr:
return []
if max_val is None:
max_val = max(arr)
count = [0] * (max_val + 1)
for x in arr:
count[x] += 1
# Prefix sums (for stable sort optional)
for i in range(1, len(count)):
count[i] += count[i - 1]
output = [0] * len(arr)
# Stable version: traverse from right to left
for x in reversed(arr):
count[x] -= 1
output[count[x]] = x
return output
7. Breadth-First Search (BFS) on a Graph
from collections import deque
def bfs(graph, start):
"""
graph: adjacency list (dict or list of lists)
start: starting vertex
Returns the order of visited nodes.
"""
visited = set()
order = []
q = deque([start])
[Link](start)
while q:
u = [Link]()
[Link](u)
for v in graph[u]:
if v not in visited:
[Link](v)
[Link](v)
return order
# Example:
# graph = {
# 0: [1, 2],
# 1: [0, 3],
# 2: [0, 3],
# 3: [1, 2]
#}
# print(bfs(graph, 0))
8. Depth-First Search (DFS) on a Graph
def dfs(graph, start):
"""DFS using recursion; returns the order of visited nodes."""
visited = set()
order = []
def _dfs(u):
[Link](u)
[Link](u)
for v in graph[u]:
if v not in visited:
_dfs(v)
_dfs(start)
return order
# Example:
# graph = {
# 0: [1, 2],
# 1: [0, 3],
# 2: [0, 3],
# 3: [1, 2]
#}
# print(dfs(graph, 0))
9. Prim’s Algorithm for Minimum Spanning Tree
import math
def prim_mst(graph):
"""
graph: adjacency matrix; graph[u][v] = weight or 0/inf if no edge.
Returns parent array describing MST.
"""
n = len(graph)
key = [[Link]] * n
parent = [-1] * n
in_mst = [False] * n
key[0] = 0
for _ in range(n):
# Pick the minimum key vertex not yet included
u = -1
min_key = [Link]
for v in range(n):
if not in_mst[v] and key[v] < min_key:
min_key = key[v]
u=v
in_mst[u] = True
# Update key value and parent index of the adjacent vertices
for v in range(n):
w = graph[u][v]
if w != 0 and not in_mst[v] and w < key[v]:
key[v] = w
parent[v] = u
return parent
# After getting parent, MST edges are (parent[i], i) for i in 1..n-1
10. Dijkstra’s Algorithm (Single Source Shortest Path)
import heapq
def dijkstra(graph, source):
"""
graph: adjacency list, e.g. graph[u] = [(v, weight), ...]
source: starting vertex
Returns distances array.
"""
n = len(graph)
dist = [[Link]] * n
dist[source] = 0
pq = [(0, source)] # (distance, vertex)
while pq:
d, u = [Link](pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
[Link](pq, (dist[v], v))
return dist
# Example:
# graph = {
# 0: [(1, 4), (2, 1)],
# 1: [(3, 1)],
# 2: [(1, 2), (3, 5)],
# 3: []
#}
# dist = dijkstra(graph, 0)
11. 0-1 Knapsack Problem using Dynamic Programming
def knapsack_01(weights, values, W):
"""
weights: list of item weights
values: corresponding list of item values
W: capacity of knapsack
Returns maximum value achievable.
"""
n = len(weights)
# dp[i][w] = best value using first i items with capacity w
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
wt = weights[i - 1]
val = values[i - 1]
for w in range(W + 1):
if wt <= w:
dp[i][w] = max(dp[i - 1][w], val + dp[i - 1][w - wt])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
# Example:
# weights = [2, 3, 4, 5]
# values = [3, 4, 5, 6]
#W=5
# print(knapsack_01(weights, values, W)) # Output: 7
