1.
write a program to implement merge sort and quick sort
# Python program for implementation of Quicksort Sort
# This implementation utilizes pivot as the last element in the nums list
# It has a pointer to keep track of the elements smaller than the pivot
# At the very end of partition() function, the pointer is swapped with the pivot
# to come up with a "sorted" nums relative to the pivot
# Function to find the partition position
def partition(array, low, high):
# choose the rightmost element as pivot
pivot = array[high]
# pointer for greater element
i = low - 1
# traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# If element smaller than pivot is found
# swap it with the greater element pointed by i
i = i + 1
# Swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# Swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# Return the position from where partition is done
return i + 1
# function to perform quicksort
def quickSort(array, low, high):
if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# Recursive call on the left of pivot
quickSort(array, low, pi - 1)
# Recursive call on the right of pivot
quickSort(array, pi + 1, high)
data = [1, 7, 4, 1, 10, 9, -2]
print("Unsorted Array")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)
Output
Unsorted Array
[1, 7, 4, 1, 10, 9, -2]
Sorted Array in Ascending Order:
[-2, 1, 1, 4, 7, 9, 10]
#Python program for implementation of MergeSort
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
# create temp arrays
L = [0] * (n1)
R = [0] * (n2)
# Copy data to temp arrays L[] and R[]
for i in range(0, n1):
L[i] = arr[l + i]
for j in range(0, n2):
R[j] = arr[m + 1 + j]
# Merge the temp arrays back into arr[l..r]
i =0 # Initial index of first subarray
j =0 # Initial index of second subarray
k =l # Initial index of merged subarray
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Copy the remaining elements of L[], if there
# are any
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# Copy the remaining elements of R[], if there
# are any
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr, l, r):
if l < r:
# Same as (l+r)//2, but avoids overflow for
# large l and h
m = l+(r-l)//2
# Sort first and second halves
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("Given array is")
for i in range(n):
print("%d" % arr[i],end=" ")
mergeSort(arr, 0, n-1)
print("\n\nSorted array is")
for i in range(n):
print("%d" % arr[i],end=" ")
# This code is contributed by Mohit Kumra
Output
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
2.write a program to implement for Bubble sort and
selection sort
def bubble_sort(arr):
# Outer loop to iterate through the list n times
for n in range(len(arr) - 1, 0, -1):
# Initialize swapped to track if any swaps occur
swapped = False
# Inner loop to compare adjacent elements
for i in range(n):
if arr[i] > arr[i + 1]:
# Swap elements if they are in the wrong order
arr[i], arr[i + 1] = arr[i + 1], arr[i]
# Mark that a swap has occurred
swapped = True
# If no swaps occurred, the list is already sorted
if not swapped:
break
# Sample list to be sorted
arr = [6,6,2]
print("Unsorted list is:")
print(arr)
bubble_sort(arr)
print("Sorted list is:")
print(arr)
Output
Unsorted list is:
[39, 12, 18, 85, 72, 10, 2, 18]
Sorted list is:
[2, 10, 12, 18, 18, 39, 72, 85]
3.write a program for linear search and binary search
# Python program for Linear Search using iterative approach
def linear_search(arr, target):
# Traverse through all elements in the arra
for index in range(len(arr)):
# If the element is found, return its index
if arr[index] == target:
return index
# If the element is not found, return -1
return -1
# Example usage:
arr = [10, 23, 45, 70, 11, 15]
target = 70
# Function call
result = linear_search(arr, target)
if result != -1:
print(f"Element found at index: {result}")
else:
print("Element not found in the array")
Output
Element found at index: 3
Binary search
def binary_search(arr, a, low, high):
# Repeat until low and high meet each other
while low <= high:
mid = low + (high - low)//2
if arr[mid] == a:
return mid
elif array[mid] < a:
low = mid + 1
else:
high = mid - 1
return -1
arr = [1, 2, 3, 4, 5, 6, 7]
a = 4
#printing the array
print("The given array is", arr)
#printing element to be found
print("Element to be found is ", a)
index = binary_search(arr, a, 0, len(arr)-1)
if index != -1:
print("The Index of the element is " + str(index))
else:
print("Element Not found")
out put
The given array is [1, 2, 3, 4, 5, 6, 7]
Element to be found is 4
The index of the element is 3
4.write a program to implement single linked list
# Python Program for traversal of Singly Linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
return new_node
def traverse(head):
current = head
while current:
# Print the current node's data followed by an
arrow and space
print(str(current.data) + " -> ", end=" ")
current = current.next
# At the end of the list, print None to indicate no
further nodes
print("None")
# Singly linked list created and its head stored in a
variable named "head"
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# To traverse and print the nodes:
traverse(head)
Output
1 -> 2 -> 3 -> 4 -> None
5. wr # Python Program for traversal of a doubly linked list
class Node:
def __init__(self, data):
# Initialize a new node with data, previous, and next
pointers
self.data = data
self.next = None
self.prev = None
def traverse(head):
# Traverse the doubly linked list and print its elements
current = head
while current:
# Print current node's data
print(current.data, end=" <-> ")
# Move to the next node
current = current.next
print("None")
def insert_at_beginning(head, data):
# Insert a new node at the beginning of the doubly linked
list
new_node = Node(data)
new_node.next = head
if head:
head.prev = new_node
return new_node
# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# To traverse and print the nodes:
traverse(head) ite a program to implement for doubly linked list
Output
1 <-> 2 <-> 3 <-> 4 <-> None
6.wtite a program to implement Binary search tree
# Python program to implement search operation in the binary search tree
# Creating a constructor class that will create the node object
class Node:
# Defining the method to create a new node and the left and right pointers of this node.
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# Defining a function that will search the given value of x in the tree
def search(root, x):
# The base conditions are
# If the given root is a Null Node # Or if the value we are searching for is present at the root only
if root is None or root.val == x:
return root.val
# If the value of x is greater than the value of the root node
if root.val < x:
# We will search in the right subtree
return search(root.right, x)
# If the value of x is smaller than the value of the root node
# We will search in the left subtree
return search(root.left, x)
# Creating a binary search tree and searching for x in the tree
root = Node(9)
root.left = Node(1)
root.right = Node(10)
root.left.left = Node(0)
root.left.right = Node(3)
root.left.right.right = Node(4) x = 4
v = search(root, x)
print("The node we are searching for is present in the given BST: ", v)
Output:
The node we are searching for is present in the given BST: 4
