BUBBLE SORT IMPLEMENTATION :

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]

if __name__ == “__main__”:

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

print(“Original Array:”, sample_array)

bubble_sort(sample_array)

print(“Sorted Array:”, sample_array)

 

Implement Stack with all the possible operations

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

def push(self, item):
self.items.append(item)

def pop(self):
if not self.is_empty():
return self.items.pop()
else:
raise IndexError(“pop from an empty stack”)

def peek(self):
if not self.is_empty():
return self.items[-1] else:
raise IndexError(“peek from an empty stack”)

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

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

# Example usage:
if __name__ == “__main__”:
stack = Stack()

print(“Is stack empty?”, stack.is_empty())
stack.push(10)
stack.push(20)
stack.push(30)

print(“Stack:”, stack.items)
print(“Top element:”, stack.peek())
print(“Pop:”, stack.pop())
print(“Stack after pop:”, stack.items)
print(“Stack size:”, stack.size())
print(“Is stack empty?”, stack.is_empty())

Create a single linked list

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

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

def append(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

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

# Example usage:
if __name__ == “__main__”:
linked_list = LinkedList()

# Appending elements to the linked list
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)

# Displaying the linked list
print(“Linked List:”)
linked_list.display()

Insert a node at the beginning of the single linked list

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

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

def append(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

def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node

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

# Example usage:
if __name__ == “__main__”:
linked_list = LinkedList()

# Appending elements to the linked list
linked_list.append(20)
linked_list.append(30)

# Adding a node at the beginning
linked_list.prepend(10)

# Displaying the linked list
print(“Linked List:”)
linked_list.display()

Quick Sort

def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0] less_than_pivot = [x for x in arr[1:] if x <= pivot] greater_than_pivot = [x for x in arr[1:] if x > pivot] return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)

# Example usage:
if __name__ == “__main__”:
# Sample array to be sorted
sample_array = [64, 25, 12, 22, 11]

print(“Original Array:”, sample_array)

# Perform Quick Sort
sorted_array = quick_sort(sample_array)

print(“Sorted Array:”, sorted_array)

Binary Tree

class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None

def insert(root, key):
if root is None:
return TreeNode(key)
else:
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root

def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.key, end=” “)
inorder_traversal(root.right)

# Example usage:
if __name__ == “__main__”:
# Creating a binary tree
root = None
keys = [50, 30, 20, 40, 70, 60, 80]

for key in keys:
root = insert(root, key)

# Performing in-order traversal
print(“In-order Traversal:”)
inorder_traversal(root)

FIFO Queue

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

def enqueue(self, item):
self.items.append(item)

def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
else:
raise IndexError(“dequeue from an empty queue”)

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

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

# Example usage:
if __name__ == “__main__”:
# Creating a FIFO queue
fifo_queue = Queue()

# Enqueueing elements
fifo_queue.enqueue(10)
fifo_queue.enqueue(20)
fifo_queue.enqueue(30)

# Displaying the queue
print(“Queue:”, fifo_queue.items)

# Dequeueing elements
dequeued_item = fifo_queue.dequeue()
print(“Dequeued item:”, dequeued_item)

# Displaying the updated queue
print(“Updated Queue:”, fifo_queue.items)
print(“Is the queue empty?”, fifo_queue.is_empty())
print(“Queue size:”, fifo_queue.size())

Stack Using Array

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

def push(self, item):
self.items.append(item)

def pop(self):
if not self.is_empty():
return self.items.pop()
else:
raise IndexError(“pop from an empty stack”)

def peek(self):
if not self.is_empty():
return self.items[-1] else:
raise IndexError(“peek from an empty stack”)

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

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

# Example usage:
if __name__ == “__main__”:
# Creating a stack using an array
stack = Stack()

# Pushing elements onto the stack
stack.push(10)
stack.push(20)
stack.push(30)

# Displaying the stack
print(“Stack:”, stack.items)

# Popping elements from the stack
popped_item = stack.pop()
print(“Popped item:”, popped_item)

# Displaying the updated stack
print(“Updated Stack:”, stack.items)

# Peeking at the top element
top_element = stack.peek()
print(“Top element:”, top_element)

# Checking if the stack is empty
print(“Is the stack empty?”, stack.is_empty())

# Checking the size of the stack
print(“Stack size:”, stack.size())

Doubled linked list

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

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

def append(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 prepend(self, data):
new_node = Node(data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node

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”)

# Example usage:
if __name__ == “__main__”:
# Creating a doubly linked list
dll = DoublyLinkedList()

# Appending elements
dll.append(10)
dll.append(20)
dll.append(30)

# Displaying the list forward
print(“Doubly Linked List (Forward):”)
dll.display_forward()

# Displaying the list backward
print(“Doubly Linked List (Backward):”)
dll.display_backward()

# Prepending an element
dll.prepend(5)

# Displaying the updated list forward
print(“Updated Doubly Linked List (Forward):”)
dll.display_forward()

Append a node in the existing linked list

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

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

def append(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 prepend(self, data):
new_node = Node(data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node

def append_node(self, node):
if not self.head:
self.head = node
else:
current = self.head
while current.next:
current = current.next
current.next = node
node.prev = current

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”)

# Example usage:
if __name__ == “__main__”:
# Creating a doubly linked list
dll = DoublyLinkedList()

# Appending elements
dll.append(10)
dll.append(20)
dll.append(30)

# Displaying the list forward
print(“Doubly Linked List (Forward):”)
dll.display_forward()

# Displaying the list backward
print(“Doubly Linked List (Backward):”)
dll.display_backward()

# Prepending an element
dll.prepend(5)

# Displaying the updated list forward
print(“Updated Doubly Linked List (Forward):”)
dll.display_forward()

# Appending a new node
new_node = Node(40)
dll.append_node(new_node)

# Displaying the list after appending the new node
print(“Doubly Linked List after Appending Node:”)
dll.display_forward()

Sparse Matrix

class SparseMatrix:
def __init__(self, rows, cols):
self.rows = rows
self.cols = cols
self.data = []

def add_element(self, row, col, value):
if 0 <= row < self.rows and 0 <= col < self.cols:
self.data.append((row, col, value))
else:
print(“Invalid indices. Element not added.”)

def display(self):
for row in range(self.rows):
for col in range(self.cols):
found = False
for item in self.data:
if item[:2] == (row, col):
print(item[2], end=”\t”)
found = True
break
if not found:
print(0, end=”\t”)
print()

# Example usage:
if __name__ == “__main__”:
# Creating a sparse matrix with 4 rows and 5 columns
sparse_matrix = SparseMatrix(4, 5)

# Adding non-zero elements
sparse_matrix.add_element(0, 1, 5)
sparse_matrix.add_element(1, 2, 8)
sparse_matrix.add_element(2, 3, 3)
sparse_matrix.add_element(3, 0, 2)

# Displaying the sparse matrix
print(“Sparse Matrix:”)
sparse_matrix.display()

Linear Search

def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1

# Example usage:
if __name__ == “__main__”:
# Creating a sample list
my_list = [4, 2, 8, 1, 7, 3, 5]

# Element to search for
target_element = 3

# Performing linear search
result = linear_search(my_list, target_element)

# Displaying the result
if result != -1:
print(f”Element {target_element} found at index {result}.”)
else:
print(f”Element {target_element} not found in the list.”)

🙂