Delhi Skill and Entrepreneurship University

(DSEU)
Department of B.Tech (Data Analytics)
Bhai Parmanand DSEU Shakarpur Campus-II

Practical File

Semester: 2
Subject: DATA STRUCTURES
Session: 2024-28 Code:
DTA-3-203-T

Submitted To : DR. S P AJITH KUMAR

Department: Department of B.Tech (Data Analytics)

Submitted By: Devansh Verma

INDEX
S.No. Practical List Date Teacher’s
 2

Sign

1. Write a program to perform basic array

functions in 1-D array.
2. Write a program to perform basic array
functions in 2-D array.
3. Write a program to check whether the given
matrix is sparse matrix or not.
4. Write a program for Insertion, Deletion,
Traversal operations on single linked list.
5. Write a program for Insertion, Deletion,
Traversal operations on double linked list.
6. Write a program for Insertion, Deletion,
Traversal operations on circular linked list.
7. Write a program for push and pop operations on
stack
8. Write a program to convert infix to prefix
expression.
9. Write a program to convert infix to postfix
expression.
10. Write a program to find the output using
Ackermann function for given M and N value

11. Write a program to describe mutual recursion

12. Write a program for implementing enqueue and

dequeue operations on queue using array and
linked list
13. Write a program for Priority Queue
implementation
14. Write a program for implementing Deque
[Double ended Queue]
15. Write a program for inorder, preorder, postorder
traversal.
16. Write a program for Binary Search Tree
operations
17. Write a program for Balanced Binary Tree/
AVL Tree.
18. Write a program for Graph Implementation.
 3

19. Write a program for Graph Traversal: Depth

First Search (DFS) and Breadth First Search
(BFS)
20. Write a program to find a desired item using
Linear Search.
21. Write a program to find a desired item using
Binary Search.
22. Write a program to sort list of items using
Bubble sort.
23. Write a program to sort an array using Merge
sort.
24. Write a program to sort an array using Selection
sort.
25. Write a program to sort an array using Insertion
sort.
26. Write a program to sort an array using Shell
sort.

27. Write a program to sort an array using Quick

sort.
28. Write a program to demonstrate working of
HashTable
29. Write a program for collision resolution using
quadratic probing technique.
30. Write a program to demonstrate working of
Bucket hashing

Practical 1: Basic Array Functions in 1-D Array

a. Aim
 4

To perform basic operations (insertion, deletion, searching, and traversal)

on a one-dimensional array.

b. Algorithm

1. Initialize an array.
2. Perform insertion by adding elements at a specific index.
3. Perform deletion by removing elements by value or index.
4. Search an element by iterating through the array.
5. Traverse the array and display each element.

3. Program
def display(arr):
print("Array elements:", arr)
def insert(arr, element, index):
arr.insert(index, element)
def delete(arr, element):
if element in arr:
arr.remove(element)
def search(arr, element):
return element in arr
# Initial array
arr = [10, 20, 30, 40, 50]
display(arr)
insert(arr, 25, 2)
print("After insertion:")
display(arr)
delete(arr, 30)
print("After deletion:")
display(arr)
print("Is 40 in array?", search(arr, 40))
4. Output

Array elements: [10, 20, 30, 40, 50]

After insertion:
Array elements: [10, 20, 25, 30, 40, 50]
After deletion:
Array elements: [10, 20, 25, 40, 50]
Is 40 in array? True

Practical 2: Basic Array Functions in 2-D Array

a. Aim

To demonstrate basic operations (traversal and update) on a two-

dimensional array.
 5

b. Algorithm

1. Initialize a 2D array.
2. Traverse the array row by row and print the elements.
3. Update a specific element by index.

3. Program

def display(matrix):
print("2D Array:")
for row in matrix:
print(row)

# Initialize 2D array
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]

display(matrix)

# Update value
matrix[1][1] = 10
print("After update:")
display(matrix)

4. Output

2D Array:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
After update:
2D Array:
[1, 2, 3]
[4, 10, 6]
[7, 8, 9]

Practical 3: Check Sparse Matrix

a. Aim

To check if a given matrix is a sparse matrix (i.e., most of its elements are
zero).
 6

b. Algorithm

1. Initialize a matrix.
2. Count the number of zero elements.
3. If zero elements > half of total elements, it's sparse.

3. Program

def is_sparse(matrix):
zero_count = 0
total_elements = len(matrix) * len(matrix[0])

for row in matrix:

zero_count += row.count(0)

return zero_count > total_elements / 2

matrix = [
[0, 0, 3],
[0, 0, 0],
[1, 0, 0]
]

if is_sparse(matrix):
print("The matrix is a sparse matrix.")
else:
print("The matrix is not a sparse matrix.")

4. Output

The matrix is a sparse matrix.

Practical 4: Single Linked List Operations

a. Aim

To implement insertion, deletion, and traversal operations on a singly

linked list.

b. Algorithm
 7

1. Create a Node class with data and next pointer.

2. Implement insert, delete, and traverse methods.
3. Use a LinkedList class to manage nodes.

3. Program

class Node:
def __init__(self, data):
self.data = data
self.next = None

class SinglyLinkedList:
def __init__(self):
self.head = None

def insert(self, data):

new_node = Node(data)
if not self.head:
self.head = new_node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node

def delete(self, key):

temp = self.head
if temp and temp.data == key:
self.head = temp.next
return
prev = None
while temp and temp.data != key:
prev = temp
temp = temp.next
if temp:
prev.next = temp.next

def traverse(self):
temp = self.head
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print("None")
 8

ll = SinglyLinkedList()
ll.insert(10)
ll.insert(20)
ll.insert(30)
print("Traversal:")
ll.traverse()
ll.delete(20)
print("After Deletion:")
ll.traverse()

4. Output

Traversal:
10 -> 20 -> 30 -> None
After Deletion:
10 -> 30 -> None

Practical 5: Double Linked List Operations

a. Aim

To implement insertion, deletion, and traversal operations on a doubly

linked list.

b. Algorithm

1. Create a Node class with data, next and prev pointers.

2. Implement insert, delete and traverse methods.
3. Use a DoublyLinkedList class to manage nodes.
 9

3. Program

class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None

class DoublyLinkedList:
def __init__(self):
self.head = None

def insert(self, data):

new_node = Node(data)
if not self.head:
self.head = new_node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
new_node.prev = temp

def delete(self, key):

temp = self.head
while temp and temp.data != key:
temp = temp.next
if temp:
if temp.prev:
temp.prev.next = temp.next
if temp.next:
temp.next.prev = temp.prev
if temp == self.head:
self.head = temp.next

def traverse(self):
temp = self.head
while temp:
print(temp.data, end=" <-> ")
temp = temp.next
print("None")

dll = DoublyLinkedList()
 10

dll.insert(1)
dll.insert(2)
dll.insert(3)
print("Traversal:")
dll.traverse()
dll.delete(2)
print("After Deletion:")
dll.traverse()

4. Output

Traversal:
1 <-> 2 <-> 3 <-> None
After Deletion:
1 <-> 3 <-> None

Practical 6: Circular Linked List Operations

a. Aim

To implement insertion, deletion, and traversal operations on a circular

linked list.

b. Algorithm

1. Create a Node class with data and next pointer.

2. Implement insert, delete and traverse methods.
3. Use a CircularLinkedList class with tail pointer.

3. Program

class Node:
def __init__(self, data):
self.data = data
 11

self.next = None

class CircularLinkedList:
def __init__(self):
self.tail = None

def insert(self, data):

new_node = Node(data)
if not self.tail:
self.tail = new_node
new_node.next = new_node
else:
new_node.next = self.tail.next
self.tail.next = new_node
self.tail = new_node

def delete(self, key):

if not self.tail:
return
current = self.tail.next
prev = self.tail
while True:
if current.data == key:
if current == self.tail:
if self.tail == self.tail.next:
self.tail = None
else:
prev.next = current.next
self.tail = prev
else:
prev.next = current.next
return
prev = current
current = current.next
if current == self.tail.next:
break

def traverse(self):
if not self.tail:
print("List is empty")
return
current = self.tail.next
while True:
 12

print(current.data, end=" -> ")

current = current.next
if current == self.tail.next:
break
print("(back to start)")

cll = CircularLinkedList()
cll.insert(10)
cll.insert(20)
cll.insert(30)
print("Traversal:")
cll.traverse()
cll.delete(20)
print("After Deletion:")
cll.traverse()

4. Output

Traversal:
10 -> 20 -> 30 -> (back to start)
After Deletion:
10 -> 30 -> (back to start)

Practical 7: Stack Operations: Push and Pop

a. Aim

To implement push and pop operations on a stack using a list.

b. Algorithm

1. Initialize an empty list to represent the stack.

2. Use append() for push operation.
3. Use pop() for pop operation.
4. Display the stack after each operation.

3. Program

stack = []

def push(item):
stack.append(item)
print(f"Pushed {item}")

def pop():
 13

if stack:
item = stack.pop()
print(f"Popped {item}")
else:
print("Stack is empty")

push(10)
push(20)
push(30)
print("Stack:", stack)
pop()
print("Stack after pop:", stack)

4. Output

Pushed 10
Pushed 20
Pushed 30
Stack: [10, 20, 30]
Popped 30
Stack after pop: [10, 20]

Practical 8: Infix to Prefix Conversion

a. Aim

To convert an infix expression to a prefix expression using stack

operations.

b. Algorithm

1. Reverse the infix expression.

2. Convert the reversed expression to postfix.
3. Reverse the postfix to get the prefix.

3. Program

def is_operator(c):
return c in "+-*/^"

def precedence(op):
if op == '+' or op == '-':
return 1
if op == '*' or op == '/':
return 2
if op == '^':
 14

return 3
return 0

def infix_to_prefix(expression):
def reverse(expr):
expr = expr[::-1]
expr = ['(' if c == ')' else ')' if c == '(' else c for c in expr]
return ''.join(expr)

def infix_to_postfix(expr):
stack = []
result = []
for c in expr:
if c.isalnum():
result.append(c)
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
result.append(stack.pop())
stack.pop()
else:
while stack and precedence(c) <= precedence(stack[-1]):
result.append(stack.pop())
stack.append(c)
while stack:
result.append(stack.pop())
return ''.join(result)

reversed_expr = reverse(expression)
postfix = infix_to_postfix(reversed_expr)
return postfix[::-1]

expr = "A+B*C"
print("Infix:", expr)
print("Prefix:", infix_to_prefix(expr))

4. Output

Infix: A+B*C
Prefix: +A*BC
 15

Practical 9: Infix to Postfix Conversion

a. Aim

To convert an infix expression to postfix using stack operations.

b. Algorithm

1. Use a stack to keep operators.

2. Append operands directly to result.
3. Pop operators from the stack based on precedence and associativity.

3. Program

def precedence(op):
if op == '+' or op == '-':
return 1
if op == '*' or op == '/':
return 2
if op == '^':
return 3
return 0

def infix_to_postfix(expression):
stack = []
result = ""
for c in expression:
 16

if c.isalnum():
result += c
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
result += stack.pop()
stack.pop()
else:
while stack and precedence(c) <= precedence(stack[-1]):
result += stack.pop()
stack.append(c)
while stack:
result += stack.pop()
return result

expr = "A+B*C"
print("Infix:", expr)
print("Postfix:", infix_to_postfix(expr))

4. Output

Infix: A+B*C
Postfix: ABC*+
 17

10. Ackermann Function

a. Aim
To implement the Ackermann function for given values of m and n using
recursion.

b. Algorithm

1. Define a recursive function ack(m, n).

2. Apply the Ackermann formula:

o If m == 0 → return n + 1

o If m > 0 and n == 0 → return ack(m - 1, 1)

o If m > 0 and n > 0 → return ack(m - 1, ack(m, n - 1))

3. Call the function with sample values of m and n.

c. Program

def ackermann(m, n):

if m == 0:

return n + 1

elif m > 0 and n == 0:

return ackermann(m - 1, 1)

elif m > 0 and n > 0:

return ackermann(m - 1, ackermann(m, n - 1))

print("Ackermann(2, 3):", ackermann(2, 3))

d. Output

Ackermann(2, 3): 9

11. Mutual Recursion

 18

a. Aim
To demonstrate mutual recursion using two functions that call each other.

b. Algorithm

1. Define two functions: is_even(n) and is_odd(n).

2. If n == 0, is_even returns True, is_odd returns False.

3. Otherwise, is_even calls is_odd(n - 1) and vice versa.

c. Program

def is_even(n):

if n == 0:

return True

else:

return is_odd(n - 1)

def is_odd(n):

if n == 0:

return False

else:

return is_even(n - 1)

num = 4

print(f"Is {num} even?:", is_even(num))

print(f"Is {num} odd?:", is_odd(num))

d. Output

Is 4 even?: True

Is 4 odd?: False

12. Queue using Array and Linked List

 19

a. Aim
To implement enqueue and dequeue operations on a queue using both
array and linked list.

b. Algorithm
Array Implementation:

1. Use a list to represent the queue.

2. Enqueue → use append().

3. Dequeue → use pop(0).

Linked List Implementation:

1. Create Node class with data and next.

2. Create Queue class with front and rear pointers.

3. For enqueue → add at rear.

4. For dequeue → remove from front.

c. Program

# Queue using Array

queue_array = []

def enqueue_array(item):

queue_array.append(item)

print(f"Enqueued (Array): {item}")

def dequeue_array():

if queue_array:

print(f"Dequeued (Array): {queue_array.pop(0)}")

else:

print("Queue is empty")

enqueue_array(1)

enqueue_array(2)

dequeue_array()
 20

# Queue using Linked List

class Node:

def __init__(self, data):

self.data = data

self.next = None

class Queue:

def __init__(self):

self.front = self.rear = None

def enqueue(self, item):

new_node = Node(item)

if not self.rear:

self.front = self.rear = new_node

else:

self.rear.next = new_node

self.rear = new_node

print(f"Enqueued (LL): {item}")

def dequeue(self):

if not self.front:

print("Queue is empty")

return

print(f"Dequeued (LL): {self.front.data}")

self.front = self.front.next

if not self.front:

self.rear = None

q = Queue()
 21

q.enqueue(10)

q.enqueue(20)

q.dequeue()

d. Output

Enqueued (Array): 1

Enqueued (Array): 2

Dequeued (Array): 1

Enqueued (LL): 10

Enqueued (LL): 20

Dequeued (LL): 10
 22

13. Priority Queue Implementation

a. Aim
To implement a Priority Queue where elements are dequeued based on
priority.

b. Algorithm

1. Use a list of tuples (priority, item).

2. Enqueue → insert based on priority.

3. Dequeue → remove the element with the highest priority (lowest

number).

c. Program

class PriorityQueue:

def __init__(self):

self.queue = []

def enqueue(self, item, priority):

self.queue.append((priority, item))

self.queue.sort() # lower value means higher priority

def dequeue(self):

if self.queue:

return self.queue.pop(0)[1]

else:

return "Queue is empty"

pq = PriorityQueue()

pq.enqueue("Task 1", 3)

pq.enqueue("Task 2", 1)

pq.enqueue("Task 3", 2)

print("Dequeued:", pq.dequeue())
 23

print("Dequeued:", pq.dequeue())

print("Dequeued:", pq.dequeue())

d. Output

Dequeued: Task 2

Dequeued: Task 3

Dequeued: Task 1

14. Deque (Double Ended Queue)

 24

a. Aim
To implement a deque allowing insertion and deletion from both ends.

b. Algorithm

1. Use collections.deque.

2. Support append(), appendleft(), pop(), and popleft() operations.

c. Program

from collections import deque

dq = deque()

dq.append(10)

dq.appendleft(5)

dq.append(15)

print("Deque after insertions:", list(dq))

dq.pop()

print("After pop:", list(dq))

dq.popleft()

print("After popleft:", list(dq))

d. Output

less

Edit

Deque after insertions: [5, 10, 15]

After pop: [5, 10]

After popleft: [10]

15. Tree Traversals (Inorder, Preorder, Postorder)

a. Aim
To perform inorder, preorder, and postorder traversals on a binary tree.
 25

b. Algorithm

1. Inorder: Left → Root → Right

2. Preorder: Root → Left → Right

3. Postorder: Left → Right → Root

4. Use recursion for traversal.

c. Program

python

Edit

class Node:

def __init__(self, key):

self.left = None

self.right = None

self.data = key

def inorder(root):

if root:

inorder(root.left)

print(root.data, end=" ")

inorder(root.right)

def preorder(root):

if root:

print(root.data, end=" ")

preorder(root.left)

preorder(root.right)

def postorder(root):

if root:

postorder(root.left)
 26

postorder(root.right)

print(root.data, end=" ")

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

print("Inorder traversal:")

inorder(root)

print("\nPreorder traversal:")

preorder(root)

print("\nPostorder traversal:")

postorder(root)

d. Output

Inorder traversal:

42513

Preorder traversal:

12453

Postorder traversal:

45231

16. Binary Search Tree Operations

a. Aim
To perform insertion, search, and traversal operations on a Binary Search
Tree (BST).

b. Algorithm

1. Create a Node class with left and right children.

 27

2. Insert a node:

o If key < root → go left

o If key > root → go right

3. Traverse using inorder to get sorted output.

4. Search by comparing keys recursively.

c. Program

class Node:

def __init__(self, key):

self.left = self.right = None

self.data = key

def insert(root, key):

if root is None:

return Node(key)

if key < root.data:

root.left = insert(root.left, key)

else:

root.right = insert(root.right, key)

return root

def inorder(root):

if root:

inorder(root.left)

print(root.data, end=" ")

inorder(root.right)

def search(root, key):

if root is None or root.data == key:

return root
 28

if key < root.data:

return search(root.left, key)

return search(root.right, key)

root = Node(50)

insert(root, 30)

insert(root, 70)

insert(root, 20)

insert(root, 40)

insert(root, 60)

print("Inorder traversal:")

inorder(root)

print("\nSearch 40:", "Found" if search(root, 40) else "Not found")

d. Output

Inorder traversal:

20 30 40 50 60 70

Search 40: Found

17. Balanced Binary Tree (AVL Tree)

a. Aim
To implement an AVL Tree with automatic balancing on insertion.

b. Algorithm

1. Use height-balanced tree where balance factor = height(left) -

height(right).

2. If balance is >1 or <-1, perform rotations (LL, RR, LR, RL).

3. Each insertion may trigger rotation.

 29

c. Program

class Node:

def __init__(self, key):

self.data = key

self.left = self.right = None

self.height = 1

def height(n):

return n.height if n else 0

def get_balance(n):

return height(n.left) - height(n.right) if n else 0

def right_rotate(y):

x = y.left

T2 = x.right

x.right = y

y.left = T2

y.height = max(height(y.left), height(y.right)) + 1

x.height = max(height(x.left), height(x.right)) + 1

return x

def left_rotate(x):

y = x.right

T2 = y.left

y.left = x

x.right = T2

x.height = max(height(x.left), height(x.right)) + 1

y.height = max(height(y.left), height(y.right)) + 1

 30

return y

def insert(root, key):

if not root:

return Node(key)

elif key < root.data:

root.left = insert(root.left, key)

else:

root.right = insert(root.right, key)

root.height = 1 + max(height(root.left), height(root.right))

balance = get_balance(root)

# Balancing

if balance > 1 and key < root.left.data:

return right_rotate(root)

if balance < -1 and key > root.right.data:

return left_rotate(root)

if balance > 1 and key > root.left.data:

root.left = left_rotate(root.left)

return right_rotate(root)

if balance < -1 and key < root.right.data:

root.right = right_rotate(root.right)

return left_rotate(root)

return root

def preorder(root):

if root:
 31

print(root.data, end=" ")

preorder(root.left)

preorder(root.right)

root = None

for key in [10, 20, 30, 40, 50, 25]:

root = insert(root, key)

print("Preorder traversal of AVL tree:")

preorder(root)

d. Output

Preorder traversal of AVL tree:

30 20 10 25 40 50

18. Graph Implementation

a. Aim
To implement a graph using adjacency list representation.

b. Algorithm

1. Use a dictionary where keys are nodes and values are lists of
adjacent nodes.

2. Add edges by updating the adjacency list.

c. Program

class Graph:

def __init__(self):

self.graph = {}
 32

def add_edge(self, u, v):

if u in self.graph:

self.graph[u].append(v)

else:

self.graph[u] = [v]

def display(self):

for node in self.graph:

print(f"{node} -> {self.graph[node]}")

g = Graph()

g.add_edge(0, 1)

g.add_edge(0, 2)

g.add_edge(1, 2)

g.add_edge(2, 0)

g.add_edge(2, 3)

g.add_edge(3, 3)

print("Graph adjacency list:")

g.display()

d. Output

Graph adjacency list:

0 -> [1, 2]

1 -> [2]

2 -> [0, 3]

3 -> [3]
 33

19. Graph Traversal: Depth First Search (DFS) and Breadth First
Search (BFS)

a. Aim
To implement DFS and BFS traversal algorithms for a graph.

b. Algorithm
DFS:

1. Start at the source node.

2. Mark it visited.

3. Recursively visit all unvisited adjacent nodes.

BFS:

1. Start at the source node and enqueue it.

2. While the queue is not empty:

o Dequeue a node.
 34

o Visit and enqueue its unvisited neighbors.

c. Program

from collections import deque

class Graph:

def __init__(self):

self.graph = {}

def add_edge(self, u, v):

if u not in self.graph:

self.graph[u] = []

self.graph[u].append(v)

def dfs_util(self, v, visited):

visited.add(v)

print(v, end=' ')

for neighbor in self.graph.get(v, []):

if neighbor not in visited:

self.dfs_util(neighbor, visited)

def dfs(self, start):

visited = set()

print("DFS Traversal:")

self.dfs_util(start, visited)

print()

def bfs(self, start):

visited = set()

queue = deque([start])
 35

visited.add(start)

print("BFS Traversal:")

while queue:

v = queue.popleft()

print(v, end=' ')

for neighbor in self.graph.get(v, []):

if neighbor not in visited:

visited.add(neighbor)

queue.append(neighbor)

print()

g = Graph()

g.add_edge(0, 1)

g.add_edge(0, 2)

g.add_edge(1, 2)

g.add_edge(2, 0)

g.add_edge(2, 3)

g.add_edge(3, 3)

g.dfs(2)

g.bfs(2)

d. Output

DFS Traversal:

2013

BFS Traversal:

2031
 36

20. Linear Search

a. Aim
To search a desired element in an array using the Linear Search algorithm.

b. Algorithm

1. Traverse the array from the beginning.

2. If the element matches the key, return its index.

3. If not found, return -1.

c. Program

def linear_search(arr, key):

for i in range(len(arr)):

if arr[i] == key:

return i

return -1
 37

arr = [5, 8, 1, 6, 9]

key = 6

index = linear_search(arr, key)

print(f"Element {key} found at index: {index}" if index != -1 else

"Element not found")

d. Output

Element 6 found at index: 3

21. Binary Search

a. Aim
To search a desired element in a sorted array using Binary Search.

b. Algorithm

1. Set low = 0, high = n - 1.

2. Find mid = (low + high) // 2.

3. If arr[mid] == key, return mid.

4. If arr[mid] < key, search in the right half.

5. If arr[mid] > key, search in the left half.

6. Repeat until low > high.

c. Program

def binary_search(arr, key):

low = 0

high = len(arr) - 1

while low <= high:

 38

mid = (low + high) // 2

if arr[mid] == key:

return mid

elif arr[mid] < key:

low = mid + 1

else:

high = mid - 1

return -1

arr = [1, 3, 5, 7, 9, 11]

key = 7

index = binary_search(arr, key)

print(f"Element {key} found at index: {index}" if index != -1 else

"Element not found")

d. Output : Element 7 found at index: 3

22. Bubble Sort

Aim: To sort a list of items using the Bubble Sort algorithm.

Algorithm:

1. Start from the first element, compare it with the next element.

2. If the current element is greater than the next, swap them.

3. Repeat for all elements until the list is sorted.

4. Optimize by stopping if no swaps occur in a pass.

Program:

def bubble_sort(arr):

n = len(arr)

for i in range(n):

swapped = False

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]

 39

swapped = True

if not swapped:

break

# Test the function

arr = [64, 34, 25, 12, 22, 11, 90]

print("Original array:", arr)

bubble_sort(arr)

print("Sorted array:", arr)

Output:

Original array: [64, 34, 25, 12, 22, 11, 90]

Sorted array: [11, 12, 22, 25, 34, 64, 90]

23. Merge Sort

Aim: To sort an array using the Merge Sort algorithm.

Algorithm:

1. Divide the array into two halves.

2. Recursively sort each half.

3. Merge the two sorted halves into a single sorted array.

Program:

def merge_sort(arr):

if len(arr) > 1:

mid = len(arr) // 2

left = arr[:mid]

right = arr[mid:]

merge_sort(left)

merge_sort(right)

i=j=k=0
 40

while i < len(left) and j < len(right):

if left[i] < right[j]:

arr[k] = left[i]

i += 1

else:

arr[k] = right[j]

j += 1

k += 1

while i < len(left):

arr[k] = left[i]

i += 1

k += 1

while j < len(right):

arr[k] = right[j]

j += 1

k += 1

# Test the function

arr = [38, 27, 43, 3, 9, 82, 10]

print("Original array:", arr)

merge_sort(arr)

print("Sorted array:", arr)

Output:

Original array: [38, 27, 43, 3, 9, 82, 10]

Sorted array: [3, 9, 10, 27, 38, 43, 82]

 41

24. Selection Sort

Aim: To sort an array using the Selection Sort algorithm.

Algorithm:

1. Find the minimum element in the unsorted part of the array.

2. Swap it with the first unsorted element.

3. Repeat until the entire array is sorted.

Program:

def selection_sort(arr):

for i in range(len(arr)):

min_idx = i

for j in range(i+1, len(arr)):

if arr[j] < arr[min_idx]:

min_idx = j

arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Test the function

arr = [64, 25, 12, 22, 11]

print("Original array:", arr)

 42

selection_sort(arr)

print("Sorted array:", arr)

Output:

Original array: [64, 25, 12, 22, 11]

Sorted array: [11, 12, 22, 25, 64]

25. Insertion Sort

Aim: To sort an array using the Insertion Sort algorithm.

Algorithm:

1. Iterate from the second element to the end.

2. For each element, place it in the correct position in the sorted part
of the array.

Program:

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 -= 1

arr[j + 1] = key

# Test the function

arr = [12, 11, 13, 5, 6]

print("Original array:", arr)

 43

insertion_sort(arr)

print("Sorted array:", arr)

Output:

Original array: [12, 11, 13, 5, 6]

Sorted array: [5, 6, 11, 12, 13]

26. Shell Sort

Aim: To sort an array using the Shell Sort algorithm.

Algorithm:

1. Start with a large gap and reduce it in each iteration.

2. Perform insertion sort on subarrays defined by the gap.

Program:

def shell_sort(arr):

n = len(arr)

gap = n // 2

while gap > 0:

for i in range(gap, n):

temp = arr[i]

j=i

while j >= gap and arr[j - gap] > temp:

arr[j] = arr[j - gap]

j -= gap

arr[j] = temp

gap //= 2
 44

# Test the function

arr = [45, 67, 23, 12, 9, 34]

print("Original array:", arr)

shell_sort(arr)

print("Sorted array:", arr)

Output:

Original array: [45, 67, 23, 12, 9, 34]

Sorted array: [9, 12, 23, 34, 45, 67]

27. Quick Sort

Aim: To sort an array using the Quick Sort algorithm.

Algorithm:

1. Choose a pivot element.

2. Partition the array such that elements less than the pivot are on the
left and greater on the right.

3. Recursively sort the subarrays.

Program:

def quick_sort(arr):

if len(arr) <= 1:

return arr

pivot = arr[len(arr) // 2]

left = [x for x in arr if x < pivot]

middle = [x for x in arr if x == pivot]

right = [x for x in arr if x > pivot]

return quick_sort(left) + middle + quick_sort(right)

# Test the function

arr = [10, 7, 8, 9, 1, 5]

print("Original array:", arr)

 45

sorted_arr = quick_sort(arr)

print("Sorted array:", sorted_arr)

Output:

Original array: [10, 7, 8, 9, 1, 5]

Sorted array: [1, 5, 7, 8, 9, 10]

28. HashTable Demonstration

Aim: To demonstrate the working of a HashTable.

Algorithm:

1. Use a dictionary to simulate a HashTable.

2. Insert, delete, and search for key-value pairs.

Program:

# Create a HashTable

hash_table = {}

# Insert elements

hash_table['name'] = 'Alice'

hash_table['age'] = 25

hash_table['city'] = 'New York'

# Display the HashTable

print("HashTable:", hash_table)

# Search for a key

print("Age:", hash_table.get('age'))

# Delete a key

del hash_table['city']
 46

print("After deletion:", hash_table)

Output:

HashTable: {'name': 'Alice', 'age': 25, 'city': 'New York'}

Age: 25

After deletion: {'name': 'Alice', 'age': 25}

29. Collision Resolution using Quadratic Probing

Aim: To resolve hash collisions using quadratic probing.

Algorithm:

1. Compute the hash index for a key.

2. If a collision occurs, probe using quadratic increments (i²).

3. Insert the key in the next available slot.

Program:

class HashTable:

def __init__(self, size):

self.size = size

self.table = [None] * size

def hash_func(self, key):

return key % self.size

def quadratic_probing(self, key, i):

return (self.hash_func(key) + i * i) % self.size

def insert(self, key):

i=0

index = self.hash_func(key)

while self.table[index] is not None:

 47

i += 1

index = self.quadratic_probing(key, i)

self.table[index] = key

def display(self):

print("Hash Table:", self.table)

# Test the function

ht = HashTable(10)

keys = [15, 25, 35, 5, 85]

for key in keys:

ht.insert(key)

ht.display()

Output:

Hash Table: [None, None, 25, 35, 15, 5, 85, None, None, None]
 48

30. Bucket Hashing Demonstration

Aim: To demonstrate the working of Bucket Hashing.

Algorithm:

1. Use a list of lists (buckets) to store elements.

2. Distribute elements into buckets based on their hash value.

3. Handle collisions by appending to the bucket.

Program:

class BucketHash:

def __init__(self, size):

self.size = size

self.buckets = [[] for _ in range(size)]

def hash_func(self, key):

return key % self.size

def insert(self, key):

index = self.hash_func(key)

self.buckets[index].append(key)

def display(self):

print("Bucket Hashing Table:")

for i, bucket in enumerate(self.buckets):

print(f"Bucket {i}: {bucket}")

 49

# Test the function

bh = BucketHash(5)

keys = [10, 20, 30, 12, 22, 7]

for key in keys:

bh.insert(key)

bh.display()

Output:

Bucket Hashing Table:

Bucket 0: [10, 20, 30]

Bucket 1: [12, 22]

Bucket 2: [7]

Bucket 3: []

Bucket 4: []