S731BLH22 DATA STRUCTURES AND ALGORITHMS

1. FIND THE SUM OF ALL ELEMENTS IN AN ARRAY

AIM:
To develop a program in python that finds the sum of all elements in an
array.

PROGRAM:
arr = [1, 2, 3, 4, 5];
sum = 0;

for i in range(0, len(arr)):

sum = sum + arr[i];
print("Sum of all the elements of an array: " + str(sum));

OUTPUT:
Sum of all the elements of an array: 15
 2. FIND A STRING IN AN ARRAY CONSISTING OF CHARACTERS

AIM:
To develop a program in python that finds a string in an array consisting
of characters.

ALGORITHM:

1. Define a function find_series that takes two parameters: arr (the array of
characters) and series (the series of characters to find).
2. Use a loop to iterate through the array and check if any subarray of length
equal to the length of the series matches the given series.
3. If a match is found, return True; otherwise, return False.

PROGRAM:
def find_series(arr, series):
for i in range(len(arr) - len(series) + 1):
if arr[i:i+len(series)] == series:
return True
return False

arr = ['a', 'x', 'a', 'b', 'c']

series_to_find = ['a', 'b', 'c']

result = find_series(arr, series_to_find)

print(f"The array contains the series {series_to_find}: {result}") (arr,
series_to_find)
print(result)
OUTPUT:

The array contains the series ['a', 'b', 'c']: True

RESULT:
 3. FIND THE OCCURRENCE OF A PARTICULAR NUMBER IN AN
ARRAY

AIM:

To develop a program in python that determines the occurrence of a

specific number in an array.

ALGORITHM:

1. Define a function find_occurrence that takes two parameters: arr (the array of
numbers) and number_to_find (the number whose occurrence needs to be
found).
2. Initialize a counter variable to 0 to keep track of the occurrences.
3. Use a loop to iterate through the array and increment the counter whenever
the current element matches the number_to_find.
4. Return the final count of occurrences.

PROGRAM:
def find_occurrence(arr, number_to_find):
occurrence_count = 0
for num in arr:
if num == number_to_find:
occurrence_count += 1
return occurrence_count

numbers = [1, 3, 5, 2, 3, 7, 8, 3, 2, 1]
number_to_find = 3

result = find_occurrence(numbers, number_to_find)

print(f"The number {number_to_find} occurs {result} times in the array.")
OUTPUT:

The number 3 occurs 3 times in the array.

 4. FIND THE LARGEST ELEMENT IN AN ARRAY

AIM:
To develop a program in python that identifies the largest element in an
array.
ALGORITHM:

1. Define a function find_largest_element that takes one parameter: arr (the

array of numbers).
2. Initialize a variable max_element to the first element of the array.
3. Use a loop to iterate through the array. For each element, compare it with the
current max_element. If the element is greater than max_element, update
max_element with the current element.
4. After iterating through the entire array, max_element will contain the largest
element.
5. Return the value of max_element.

PROGRAM:
def find_largest_element(arr):
if not arr:
return None
max_element = arr[0]
for num in arr:
if num > max_element:
max_element = num
return max_element

numbers = [12, 5, 23, 8, 19, 42, 9, 17]

result = find_largest_element(numbers)
print(f"The largest element in the array is: {result}")
OUTPUT:
The largest element in the array is: 42
 5. PROGRAM FOR ARRAY ROTATION

AIM:

To develop a program in python to rotate the elements of an array.

ALGORITHM:

1. Choose the number of positions k by which to rotate the array.

2. Divide the array into two parts: the first part contains the last k elements,
and the second part contains the rest of the elements.
3. Swap the positions of the two parts to perform the rotation.

PROGRAM:
def rotate_array(arr, k):
n = len(arr)
k=k%n

arr[:k] = reversed(arr[:k])

arr[k:] = reversed(arr[k:])

arr.reverse()

numbers = [1, 2, 3, 4, 5, 6, 7]
rotation_positions = 3

print("Original array:", numbers)

rotate_array(numbers, rotation_positions)
print(f"Array after rotating {rotation_positions} positions:", numbers)

OUTPUT:
Original array: [1, 2, 3, 4, 5, 6, 7]
Array after rotating 3 positions: [5, 6, 7, 1, 2, 3, 4]
 6. PROGRAM TO IMPLEMENT THE OPERATIONS IN A SINGLY
LINKED LIST

AIM:

To develop a program in python that implements basic operations on a

singly linked list.

ALGORITHM:

1. Define a class Node to represent a node in the linked list. Each node has a
data element and a reference to the next node in the list.
2. Define a class LinkedList that contains methods to perform operations on
the linked list:
o __init__: Initialize an empty linked list.
o insert_at_end: Insert a new node at the end of the linked list.
o insert_at_beginning: Insert a new node at the beginning of the
linked list.
o delete_node: Delete a node with a given data value from the linked
list.
o display: Display the elements of the linked list.

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

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

def insert_at_end(self, data):

new_node = Node(data)
 if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node

def insert_at_beginning(self, data):

new_node = Node(data)
new_node.next = self.head
self.head = new_node

def delete_node(self, data):

current = self.head
if current and current.data == data:
self.head = current.next
return
while current.next:
if current.next.data == data:
current.next = current.next.next
return
current = current.next

def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
 print("None")

linked_list = LinkedList()

linked_list.insert_at_end(1)
linked_list.insert_at_end(2)
linked_list.insert_at_end(3)
linked_list.display()

linked_list.insert_at_beginning(0)
linked_list.display()

linked_list.delete_node(2)
linked_list.display()

SAMPLE OUTPUT:

1 -> 2 -> 3 -> None

0 -> 1 -> 2 -> 3 -> None
0 -> 1 -> 3 -> None

7. PROGRAM TO IMPLEMENT ALL OPERATIONS IN A DOUBLY

LINKED LIST
AIM:

To develop a program in python that implements basic operations on a

doubly linked list.

ALGORITHM:

1. Define a class Node to represent a node in the doubly linked list. Each
node has a data element, a reference to the next node, and a reference to
the previous node.
2. Define a class DoublyLinkedList that contains methods to perform
operations on the doubly linked list:
o __init__: Initialize an empty doubly linked list.
o insert_at_end: Insert a new node at the end of the doubly linked
list.
o insert_at_beginning: Insert a new node at the beginning of the
doubly linked list.
o delete_node: Delete a node with a given data value from the doubly
linked list.
o display_forward: Display the elements of the doubly linked list in
forward order.
o display_backward: Display the elements of the doubly linked list in
backward order.

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

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

def insert_at_end(self, data):

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

def insert_at_beginning(self, data):

new_node = Node(data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node

def delete_node(self, data):

current = self.head
while current:
if current.data == data:
if current.prev:
current.prev.next = current.next
else:
self.head = current.next
if current.next:
current.next.prev = current.prev
return
current = current.next
 def display_forward(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")

def display_backward(self):
current = self.head
while current and current.next:
current = current.next
while current:
print(current.data, end=" <-> ")
current = current.prev
print("None")

doubly_linked_list = DoublyLinkedList()

doubly_linked_list.insert_at_end(1)
doubly_linked_list.insert_at_end(2)
doubly_linked_list.insert_at_end(3)
doubly_linked_list.display_forward()
doubly_linked_list.display_backward()

doubly_linked_list.insert_at_beginning(0)
doubly_linked_list.display_forward()
doubly_linked_list.display_backward()
doubly_linked_list.delete_node(2)
doubly_linked_list.display_forward()
doubly_linked_list.display_backward()

SAMPLE OUTPUT:
1 <-> 2 <-> 3 <-> None
3 <-> 2 <-> 1 <-> None
0 <-> 1 <-> 2 <-> 3 <-> None
3 <-> 2 <-> 1 <-> 0 <-> None
0 <-> 1 <-> 3 <-> None
3 <-> 1 <-> 0 <-> None

8. PROGRAM TO IMPLEMENT STACK USING AN ARRAY

AIM:
 To develop a program in python that implements a stack data structure
using an array.

ALGORITHM:

1. Define a class Stack

2. Perform the following stack operations:
o is_empty: Check if the stack is empty.
o push: Add an element to the top of the stack.
o pop: Remove and return the element from the top of the stack.
o peek: Return the element at the top of the stack without removing
it.
o size: Return the current size of the stack

PROGRAM:

class Stack:
def __init__(self):
self.items = []

def is_empty(self):
return len(self.items) == 0

def push(self, item):

self.items.append(item)

def pop(self):
if not self.is_empty():
return self.items.pop()
else:
return "Stack is empty"

def peek(self):
if not self.is_empty():
 return self.items[-1]
else:
return "Stack is empty"

def size(self):
return len(self.items)

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Top of the stack:", stack.peek())

print("Size of the stack:", stack.size())

popped_item = stack.pop()
print("Popped item:", popped_item)

print("Top of the stack after pop:", stack.peek())

print("Size of the stack after pop:", stack.size())

OUTPUT:
Top of the stack: 3
Size of the stack: 3
Popped item: 3
Top of the stack after pop: 2
Size of the stack after pop: 2
9. PROGRAM TO IMPLEMENT STACK USING LINKED LIST
AIM:

To develop a program in python that implements a stack data structure

using a linked list.

ALGORITHM:

1. Define a class Node to represent a node in the linked list. Each node has a
data element and a reference to the next node.
2. Define a class Stack with methods to perform stack operations:
o __init__: Initialize an empty stack with a head pointing to None.
o is_empty: Check if the stack is empty.
o push: Add an element to the top of the stack by creating a new
node.
o pop: Remove and return the element from the top of the stack.
o peek: Return the element at the top of the stack without removing
it.
o size: Return the current size of the stack.

PROGRAM:

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

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

def is_empty(self):
return self.head is None
def push(self, item):
new_node = Node(item)
new_node.next = self.head
self.head = new_node

def pop(self):
if not self.is_empty():
popped_item = self.head.data
self.head = self.head.next
return popped_item
else:
return "Stack is empty"

def peek(self):
if not self.is_empty():
return self.head.data
else:
return "Stack is empty"

def size(self):
current = self.head
count = 0
while current:
count += 1
current = current.next
return count
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Top of the stack:", stack.peek())

print("Size of the stack:", stack.size())

popped_item = stack.pop()
print("Popped item:", popped_item)

print("Top of the stack after pop:", stack.peek())

print("Size of the stack after pop:", stack.size())

OUTPUT:
Top of the stack: 3
Size of the stack: 3
Popped item: 3
Top of the stack after pop: 2
Size of the stack after pop: 2

10.PROGRAM TO IMPLEMENT QUEUE USING AN ARRAY

AIM:

To develop a program in python that implements a queue data structure

using an array.

ALGORITHM:

1. Define a class Queue with the required methods.

2. Perform the quweuw operations queue operations:
o is_empty: Check if the queue is empty.
o enqueue: Add an element to the rear of the queue.
o dequeue: Remove and return the element from the front of the
queue.
o peek: Return the element at the front of the queue without
removing it.
o size: Return the current size of the queue.

PROGRAM:
class Queue:
def __init__(self):
self.items = []

def is_empty(self):
return len(self.items) == 0

def enqueue(self, item):

self.items.append(item)

def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
else:
return "Queue is empty"
 def peek(self):
if not self.is_empty():
return self.items[0]
else:
return "Queue is empty"

def size(self):
return len(self.items)

queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print("Front of the queue:", queue.peek())

print("Size of the queue:", queue.size())

dequeued_item = queue.dequeue()
print("Dequeued item:", dequeued_item)

print("Front of the queue after dequeue:", queue.peek())

print("Size of the queue after dequeue:", queue.size())

OUTPUT:
Front of the queue: 1
Size of the queue: 3
Dequeued item: 1
Front of the queue after dequeue: 2
Size of the queue after dequeue: 2

11.PROGRAM TO IMPLEMENT QUEUE USING A LINKED LIST

AIM:

To develop a program in python that implements a queue data structure

using a linked list.

ALGORITHM:

1. Define a class Node to represent a node in the linked list. Each node has a
data element and a reference to the next node.
2. Define a class Queue with methods to perform queue operations:
o __init__: Initialize an empty queue with front and rear pointing to
None.
o is_empty: Check if the queue is empty.
o enqueue: Add an element to the rear of the queue by creating a new
node.
o dequeue: Remove and return the element from the front of the
queue.
o peek: Return the element at the front of the queue without
removing it.
o size: Return the current size of the queue.

PROGRAM:

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

class Queue:
def __init__(self):
self.front = None
self.rear = None

def is_empty(self):
return self.front is None

def enqueue(self, item):

new_node = Node(item)
if self.is_empty():
self.front = new_node
self.rear = new_node
else:
 self.rear.next = new_node
self.rear = new_node

def dequeue(self):
if not self.is_empty():
dequeued_item = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
return dequeued_item
else:
return "Queue is empty"

def peek(self):
if not self.is_empty():
return self.front.data
else:
return "Queue is empty"

def size(self):
current = self.front
count = 0
while current:
count += 1
current = current.next
return count

# Example usage:
queue = Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print("Front of the queue:", queue.peek())

print("Size of the queue:", queue.size())

dequeued_item = queue.dequeue()
print("Dequeued item:", dequeued_item)
print("Front of the queue after dequeue:", queue.peek())
print("Size of the queue after dequeue:", queue.size())

OUTPUT:

Front of the queue: 1

Size of the queue: 3
Dequeued item: 1
Front of the queue after dequeue: 2
Size of the queue after dequeue: 2

12.IMPLEMENT THE CIRCULAR QUEUE

AIM:

To develop a program in python that implements a circular queue data structure.

ALGORITHM:

1. Define a class CircularQueue with methods to perform circular queue

operations:
2. Perform the following operations:
o is_empty: Check if the circular queue is empty.
o is_full: Check if the circular queue is full.
o enqueue: Add an element to the rear of the circular queue.
o dequeue: Remove and return the element from the front of the
circular queue.
o peek: Return the element at the front of the circular queue without
removing it.

PROGRAM:

class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.front = self.rear = -1
self.size = 0

def is_empty(self):
return self.size == 0

def is_full(self):
return self.size == self.capacity

def enqueue(self, item):

if self.is_full():
print("Queue is full. Cannot enqueue.")
return

if self.is_empty():
self.front = self.rear = 0
else:
 self.rear = (self.rear + 1) % self.capacity

self.queue[self.rear] = item
self.size += 1

def dequeue(self):
if self.is_empty():
print("Queue is empty. Cannot dequeue.")
return None

dequeued_item = self.queue[self.front]

if self.front == self.rear:
self.front = self.rear = -1
else:
self.front = (self.front + 1) % self.capacity

self.size -= 1
return dequeued_item

def peek(self):
if self.is_empty():
print("Queue is empty. Cannot peek.")
return None
return self.queue[self.front]

cq = CircularQueue(5)

cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)
cq.enqueue(6)

print("Front of the queue:", cq.peek())

print("Size of the queue:", cq.size)

dequeued_item = cq.dequeue()
print("Dequeued item:", dequeued_item)

print("Front of the queue after dequeue:", cq.peek())

print("Size of the queue after dequeue:", cq.size)

OUTPUT:

Queue is full. Cannot enqueue.

Front of the queue: 1
Size of the queue: 5
Dequeued item: 1
Front of the queue after dequeue: 2
Size of the queue after dequeue: 4

RESULT:

13.PROGRAM TO CONVERT AN INFIX EXPRESSION INTO POSTFIX

EXPRESSION
AIM:
To develop a program in python that converts an infix expression to a
postfix expression.

ALGORITHM:

1. Create an empty stack to store operators.

2. Initialize an empty string to store the postfix expression.
3. Iterate through each character in the infix expression:
o If the character is an operand, append it to the postfix expression.
o If the character is an operator:
 While the stack is not empty and the precedence of the
operator at the top of the stack is greater than or equal to the
current operator, pop operators from the stack and append
them to the postfix expression.
 Push the current operator onto the stack.
o If the character is an open parenthesis '(', push it onto the stack.
o If the character is a close parenthesis ')':
 Pop operators from the stack and append them to the postfix
expression until an open parenthesis '(' is encountered.
 Pop the open parenthesis from the stack.
4. Pop any remaining operators from the stack and append them to the
postfix expression.
5. The final string is the postfix expression.

PROGRAM:
def infix_to_postfix(infix_expression):
stack = []
postfix_expression = ""
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

for char in infix_expression:

if char.isalnum():
 postfix_expression += char
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
postfix_expression += stack.pop()
stack.pop()
else:
while stack and precedence.get(stack[-1], 0) >= precedence.get(char, 0):
postfix_expression += stack.pop()
stack.append(char)
while stack:
postfix_expression += stack.pop()

return postfix_expression
infix_expr = "a + b * (c ^ d - e) / f"
postfix_expr = infix_to_postfix(infix_expr)
print("Infix Expression:", infix_expr)
print("Postfix Expression:", postfix_expr)

OUTPUT:
Infix Expression: a + b * (c ^ d - e) / f
Postfix Expression: abcd^e-f*/+

RESULT:

14.PROGRAM TO IMPLEMENT BREADTH FIRST SEARCH(BFD)

AND DEPTH FIRST SEARCH(DFS)
Aim:

To develop a program in python for Breadth-First Search (BFS) and

Depth-First Search (DFS) algorithms to traverse a graph.

ALGORITHM:

Breadth-First Search (BFS) Algorithm:

1. Create an empty queue and enqueue the starting node.

2. While the queue is not empty:
o Dequeue a node from the queue.
o Process the node (e.g., visit or print the node).
o Enqueue all unvisited neighbors of the node.
3. Continue until the queue is empty.

Depth-First Search (DFS) Algorithm:

1. Create a recursive function or use a stack to perform DFS.

2. Start from the initial node.
3. Process the current node (e.g., visit or print the node).
4. Recursively call DFS for each unvisited neighbor of the current node.

PROGRAM:
from collections import defaultdict

class Graph:
def __init__(self):
self.graph = defaultdict(list)

def add_edge(self, u, v):

self.graph[u].append(v)
self.graph[v].append(u)

def bfs(self, start):

 visited = set()
queue = [start]
result_bfs = []

while queue:
node = queue.pop(0)
if node not in visited:
result_bfs.append(node)
visited.add(node)
queue.extend(self.graph[node])

return result_bfs

def dfs(self, start, visited=None):

if visited is None:
visited = set()
result_dfs = []

visited.add(start)
result_dfs.append(start)

for neighbor in self.graph[start]:

if neighbor not in visited:
result_dfs.extend(self.dfs(neighbor, visited))

return result_dfs
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)

start_node = 2

print("BFS starting from node {}: {}".format(start_node, g.bfs(start_node)))

print("DFS starting from node {}: {}".format(start_node, g.dfs(start_node)))

OUTPUT:

BFS starting from node 2: [2, 0, 3, 1]

DFS starting from node 2: [2, 0, 1, 3]

RESULT:

15.PROGRAM TO IMPLEMENT N QUEENS PROBLEM

AIM:
 To develop a program in python to find a solution to the N-Queens
problem.

ALGORITHM:

1. Initialize an empty N×N chessboard.

2. Start placing queens one by one in different columns, starting from the
leftmost column.
3. For each column, try placing the queen in each row and check if it
conflicts with already placed queens.
4. If a safe spot is found, mark the position on the chessboard and move to
the next column.
5. If a safe spot is not found, backtrack to the previous column and try a
different row for the queen.
6. Repeat steps 3-5 until all queens are placed or a solution is found.

PROGRAM:
def is_safe(board, row, col, n):
for i in range(col):
if board[row][i] == 1:
return False

for i, j in zip(range(row, -1, -1), range(col, -1, -1)):

if board[i][j] == 1:
return False

for i, j in zip(range(row, n, 1), range(col, -1, -1)):

if board[i][j] == 1:
return False

return True

def solve_n_queens_util(board, col, n, solutions):

 if col == n:
solutions.append([row[:] for row in board])
return

for i in range(n):
if is_safe(board, i, col, n):
board[i][col] = 1
solve_n_queens_util(board, col + 1, n, solutions)
board[i][col] = 0 # Backtrack

def solve_n_queens(n):
board = [[0] * n for _ in range(n)]
solutions = []
solve_n_queens_util(board, 0, n, solutions)
return solutions

def print_solution(solution):
for row in solution:
print(' '.join('Q' if cell == 1 else '.' for cell in row))
print()

n = int(input("Enter the value of N for the N-Queens problem: "))

solutions = solve_n_queens(n)

print("\nSolutions for N-Queens problem (N = {}):".format(n))

for idx, solution in enumerate(solutions):
print("Solution {}: ".format(idx + 1))
 print_solution(solution)

OUTPUT:
Enter the value of N for the N-Queens problem: 4
Solutions for N-Queens problem (N = 4):
Solution 1:
.Q..
...Q
Q...
..Q.

Solution 2:
..Q.
Q...
...Q
.Q..

RESULT:

16.PROGRAM TO IMPLEMENT THE BINARY TREE TRAVERSAL TO

IMPLEMENT TRAVELLING SALESMAN PROBLEM
AIM:

To develop a program in to implement a basic version of the Traveling

Salesman Problem using binary tree traversal.

ALGORITHM:

1. Create a binary tree with cities as nodes.

2. Perform a depth-first traversal of the binary tree to generate all possible
routes.
3. Calculate the total distance for each route.
4. Keep track of the shortest route found.

PROGRAM:

class TreeNode:

def __init__(self, city, distance):

self.city = city

self.distance = distance

self.left = None

self.right = None

def build_sample_tree():

root = TreeNode("A", 0)

root.left = TreeNode("B", 5)

root.right = TreeNode("C", 10)

root.left.left = TreeNode("D", 8)

root.left.right = TreeNode("E", 6)

root.right.left = TreeNode("F", 15)

root.right.right = TreeNode("G", 12)

 return root

def tsp_binary_tree(root, current_distance, path, shortest_path):

if not root:

return

path.append(root.city)

current_distance += root.distance

if root.left is None and root.right is None:

if current_distance < shortest_path[1]:

shortest_path[0] = list(path)

shortest_path[1] = current_distance

tsp_binary_tree(root.left, current_distance, path, shortest_path)

tsp_binary_tree(root.right, current_distance, path, shortest_path)

path.pop()

current_distance -= root.distance

def traveling_salesman_problem(root):

if not root:

return None
 shortest_path = [None, float('inf')] # [Shortest Path, Shortest Distance]

tsp_binary_tree(root, 0, [], shortest_path)

return shortest_path[0], shortest_path[1]

tree_root = build_sample_tree()

shortest_path, shortest_distance = traveling_salesman_problem(tree_root)

print("Shortest Path:", shortest_path)

print("Shortest Distance:", shortest_distance)

OUTPUT:
Shortest Path: ['A', 'B', 'E', 'C', 'G', 'F', 'D']
Shortest Distance: 36

RESULT:

17.PROGRAM TO SORT THE ELEMETS USING INSERTION SORT

AIM:
 To develop a program in python that sorts a list of elements using the
Insertion Sort algorithm.

ALGORITHM

1. Start with the second element (index 1) and compare it with the first
element.
2. If the second element is smaller, swap it with the first element.
3. Move to the third element (index 2) and compare it with the second
element and then with the first element. Swap if necessary.
4. Repeat this process for each element in the list until the entire list is
sorted.

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

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

print("Original list:", numbers)

insertion_sort(numbers)
print("Sorted list:", numbers)
OUTPUT:
Original list: [12, 11, 13, 5, 6]
Sorted list: [5, 6, 11, 12, 13]

RESULT:

18.PROGRAM TO SORT THE ELEMETS USING QUICK SORT

AIM:

To develop a program in python that sort a list of elements using the

Quick Sort algorithm.

ALGORITHM:

1. Choose a "pivot" element from the array. The choice of the pivot can be
random, or it can be the middle or the last element.
2. Partition the array into two sub-arrays: elements less than the pivot and
elements greater than the pivot.
3. Recursively apply the Quick Sort algorithm to the two sub-arrays.
4. Combine the sorted sub-arrays and the pivot to get the final sorted array.

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)

numbers = [12, 4, 5, 6, 7, 3, 1, 15]

print("Original list:", numbers)
sorted_numbers = quick_sort(numbers)
print("Sorted list:", sorted_numbers)
OUTPUT:
Original list: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted list: [1, 3, 4, 5, 6, 7, 12, 15]
RESULT:

19.PROGRAM TO SORT THE ELEMETS USING MERGE SORT

AIM:
To develop a program in python to sort a list of elements using the Merge Sort
algorithm.

ALGORITHM:

1. Divide the unsorted list into n sub-lists, each containing one element (a
list of one element is considered sorted).
2. Repeatedly merge sub-lists to produce new sorted sub-lists until there is
only one sub-list remaining.

PROGRAM:
def merge_sort(arr):
if len(arr) <= 1:
return arr

mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]

left = merge_sort(left)
right = merge_sort(right)

return merge(left, right)

def merge(left, right):

result = []
i=j=0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
 else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])

return result
numbers = [12, 4, 5, 6, 7, 3, 1, 15]

print("Original list:", numbers)

sorted_numbers = merge_sort(numbers)
print("Sorted list:", sorted_numbers)

OUTPUT:
Original list: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted list: [1, 3, 4, 5, 6, 7, 12, 15]

RESULT:

20.PROGRAM TO FIND AN ELEMENT USING LINEAR SEARCH

AIM:

To develop a program in python to find an element in a list using Linear Search.

ALGORITHM:

1. Start from the beginning of the list.

2. Compare the target element with each element in the list sequentially.
3. If the target element is found, return its index. If not found, return -1.

PROGRAM:

def linear_search(arr, target):

for i in range(len(arr)):
if arr[i] == target:
return i
return -1

numbers = [1, 5, 8, 12, 16, 23, 42]

target_element = 16

index = linear_search(numbers, target_element)

if index != -1:
print(f"Linear Search: Element {target_element} found at index {index}.")
else:
print(f"Linear Search: Element {target_element} not found.")

OUTPUT:
Linear Search: Element 16 found at index 4.

RESULTS:
21.PROGRAM TO FIND AN ELEMENT USING BINARY SEARCH
AIM:

To develop a program in python to find an element in a sorted list using

Binary Search.

ALGORITHM:

1. Start with the entire sorted list.

2. Compare the target element with the middle element of the list.
3. If the target element is equal to the middle element, return its index.
4. If the target element is less than the middle element, search in the left
half; otherwise, search in the right half.
5. Repeat the process until the target element is found or the search space
becomes empty.

PROGRAM:
def binary_search(arr, target):
low, high = 0, len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1

return -1
numbers = [1, 5, 8, 12, 16, 23, 42]
target_element = 16

index = binary_search(numbers, target_element)

if index != -1:
print(f"Binary Search: Element {target_element} found at index {index}.")
else:
print(f"Binary Search: Element {target_element} not found.")

OUTPUT:
Binary Search: Element 16 found at index 4.

RESULT: