SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
PRACTICAL-1
AIM: Implementation and Time analysis of sorting algorithms.
Bubble sort, Selection sort, Insertion sort, Merge sort and Quicksort.
Code (Bubble Sort):
# Bubble Sort
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
x = [10, 30, 1, 5, 6]
# Outer loop: Iterate through each element of the list
for i in range(len(x)):
# Inner loop: Iterate through the list up to the unsorted section
# Each pass through the list places the next largest element in its correct
position
for j in range(len(x) - i - 1):
# Compare adjacent elements
if x[j] > x[j + 1]:
# Swap elements if the current element is greater than the next element
tmp = x[j]
x[j] = x[j + 1]
x[j + 1] = tmp
print(x)
Output:
Time Complexity : n²
ENROLLMENT NO.: 220410107084 Page|1
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
Code (Selection Sort):
# Selection Sort
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
x = [3, 6, 5, 2, 0, 1]
# Iterate through each element in the list
for i in range(len(x)):
# Assume the current index is the minimum
min = i
# Find the index of the smallest element in the remaining unsorted portion of
the list
for j in range(i + 1, len(x)):
# Compare the current minimum with the next element
if x[min] > x[j]:
# Update the index of the minimum element if a smaller element is found
min = j
# Swap the smallest found element with the element at the current index
tmp = x[i]
x[i] = x[min]
x[min] = tmp
print(x)
Output:
Time Complexity : n²
ENROLLMENT NO.: 220410107084 Page|2
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
Code (Insertion Sort):
# Insertion Sort
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
l = [10, 5, 3, 6, 2]
# Iterate over the list starting from the second element
for i in range(1, len(l)):
# Store the current element (the one to be inserted into the sorted portion)
tmp = l[i]
# Initialize the index of the element before the current one
j=i-1
# Move elements of the sorted segment that are greater than 'tmp' one position
to the right
while j >= 0 and l[j] > tmp:
l[j + 1] = l[j] # Shift the element to the right
j = j - 1 # Move to the next element in the sorted segment
# Insert 'tmp' into its correct position
l[j + 1] = tmp
print(l)
Output:
Time Complexity : n²
ENROLLMENT NO.: 220410107084 Page|3
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
Code (Merge Sort):
# Merge Sort
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
def merge_sort(l):
# Base case: if the list has 1 or 0 elements, it's already sorted
if len(l) <= 1:
return l
# Find the middle point to divide the list into two halves
mid = len(l) // 2
# Divide the list into two halves
left_half = l[:mid]
right_half = l[mid:]
# Recursively sort both halves
left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)
# Merge the sorted halves and return the result
return merge(left_sorted, right_sorted)
# Define the merge function to combine two sorted lists into a single sorted list
def merge(left, right):
sorted_list = [] # This will store the merged result
i = j = 0 # Initialize pointers for left and right lists
# Compare elements from both lists and merge them in sorted order
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_list.append(left[i]) # Append smaller element to sorted_list
i += 1 # Move pointer in the left list
else:
sorted_list.append(right[j]) # Append smaller element to sorted_list
j += 1 # Move pointer in the right list
# Append any remaining elements from left list (if any)
sorted_list.extend(left[i:])
# Append any remaining elements from right list (if any)
sorted_list.extend(right[j:])
return sorted_list # Return the merged and sorted list
ENROLLMENT NO.: 220410107084 Page|4
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
l = [0, 3, 2, 55, 1]
sorted_list = merge_sort(l)
print(sorted_list)
Output:
Time Complexity : n log n
Code (Quick Sort):
# Quick Sort
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
def quick_sort(l):
if len(l) <= 1:
return l
# Choose the pivot element (first element in this case)
pivot = l[0]
# Partition the list into two sublists:
# 1. Elements less than or equal to the pivot
# 2. Elements greater than the pivot
less_than_pivot = [x for x in l[1:] if x <= pivot]
greater_than_pivot = [x for x in l[1:] if x > pivot]
# Recursively apply quick_sort to both sublists and combine them with the
pivot
return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)
l = [10, 2, 4, 5, 6, 1, 0]
sorted_list = quick_sort(l) # Call quick_sort to sort the list
print(sorted_list)
Output:
Time Complexity : n²
ENROLLMENT NO.: 220410107084 Page|5
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
PRACTICAL-2
AIM: Implementation and Time analysis of linear and binary search
algorithm.
Code (Linear Search):
# Linear Search
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
l = [10, 20, 30, 40, 50]
# Input from the user: the value to search for in the list
x = int(input("Enter value to search: "))
# Iterate through the list to find the target value
for i in range(len(l)):
# Check if the current element matches the target value
if l[i] == x:
print(x)
break
else:
# Print "not found" if the target value is not in the list
print("not found")
Output:
Time Complexity : n
ENROLLMENT NO.: 220410107084 Page|6
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
Code (Binary Search):
# Binary Search
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
l = [10, 20, 30, 40, 50]
# Input from the user: the value to search for in the list
x = int(input("Enter value to search: "))
# Initialize pointers for the search range
low = 0
high = len(l) - 1
# Perform binary search while the search range is valid
while low <= high:
# Calculate the middle index of the current search range
mid = (low + high) // 2
# Check if the middle element is the target value
if l[mid] == x:
# If a match is found, print the value and its index, then exit the loop
print(x, "at index", mid)
break
# If the target value is greater than the middle element, search in the right half
elif l[mid] < x:
low = mid + 1
# If the target value is less than the middle element, search in the left half
else:
high = mid - 1
else:
print("not found")
Output:
Time Complexity : log n
ENROLLMENT NO.: 220410107084 Page|7
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
PRACTICAL-3
AIM: Implementation of max-heap sort algorithm.
Code:
#include <stdio.h>
// Function to maintain the max-heap property
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// Check if left child exists and is greater than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// Check if right child exists and is greater than root
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root, swap and continue heapifying
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest); // Recursively heapify the affected subtree
}
}
// Function to perform heap sort
void heapSort(int arr[], int n) {
// Build a max-heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from the heap one by one
for (int i = n - 1; i > 0; i--) {
// Move current root to end
ENROLLMENT NO.: 220410107084 Page|8
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify the root element to maintain the heap property
heapify(arr, i, 0);
}
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Main function
int main() {
printf("Name: Nishil Pathak");
printf("\nEnrollment No.: 220410107084");
int arr[] = {4, 10, 3, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: ");
printArray(arr, n);
heapSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Output:
ENROLLMENT NO.: 220410107084 Page|9
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
PRACTICAL-4
AIM: Implementation and Time analysis of factorial program using
iterative and recursive method.
Code (Iterative Method):
# Factorial Calculation-Iterative Method
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
n = int(input("Enter value of n: "))
fact = 1
# Iterate from 1 to n (inclusive)
for i in range(1, n + 1):
# Multiply the current value of fact by i
fact = fact * i
# Print the result which is the factorial of n
print(fact)
Output:
Time Complexity : n
ENROLLMENT NO.: 220410107084 Page|10
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
Code (Recursive Method):
# Factorial Calculation-Recursion
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
def fact(n):
# Base case: the factorial of 0 is 1
if n == 0:
return 1
# Recursive case: n * factorial of (n-1)
else:
return n * fact(n - 1)
# Prompt the user to enter the value of n
n = int(input("Enter value of n: "))
# Compute and print the factorial of n using the recursive function
print(fact(n))
Output:
Time Complexity : n
ENROLLMENT NO.: 220410107084 Page|11
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
PRACTICAL-5
AIM: Implementation of a knapsack problem using dynamic
programming.
Code:
def knapsack(W, wt, val, n):
"""
Solve the knapsack problem using dynamic programming.
Args:
W: Maximum weight capacity of the knapsack.
wt: List of weights of items.
val: List of values of items.
n: Number of items.
Returns:
The maximum value that can be obtained.
"""
print("Name: Nishil Pathak")
print("Enrollment No.: 220410107084")
# Create a 2D list K with dimensions (n+1) x (W+1)
# K[i][w] will hold the maximum value of the knapsack with capacity w using
the first i items.
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
# Build the table K[][] in a bottom-up manner
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
# If there are no items or capacity is 0, the maximum value is 0
K[i][w] = 0
elif wt[i - 1] <= w:
# If the weight of the current item is less than or equal to the capacity
w
# Consider including the item or not including it
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
else:
# If the weight of the current item is more than the capacity w
# Do not include the item
K[i][w] = K[i - 1][w]
ENROLLMENT NO.: 220410107084 Page|12
SARDAR VALLABHBHAI PATEL INSTITUTE OF TECHNOLOGY
SUB NAME: ADA SUBJECT CODE: 3150703
# The value in K[n][W] is the maximum value that can be obtained with n items
and capacity W
return K[n][W]
# Example usage
val = [60, 100, 120] # Values of the items
wt = [10, 20, 30] # Weights of the items
W = 50 # Maximum weight capacity of the knapsack
n = len(val) # Number of items
# Call the knapsack function and print the result
result = knapsack(W, wt, val, n)
print("Maximum value that can be obtained:", result)
Output:
ENROLLMENT NO.: 220410107084 Page|13