LAB FILE: ANALYSIS AND DESIGN OF
ALGORITHM
NAME: LAVYA KUMAR BERIWAL
2301010012
Q1. Linear Search
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) return i;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int result = linearSearch(arr, n, key);
if (result != -1)
cout << "Element found at index " << result;
else
cout << "Element not found";
return 0;
}
Output of Linear Search
Element found at index 2
Q2. Binary Search
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int key) {
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] < key) l = mid + 1;
else r = mid - 1;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int result = binarySearch(arr, 0, n - 1, key);
if (result != -1)
cout << "Element found at index " << result;
else
cout << "Element not found";
return 0;
}
Output of Binary Search
Element found at index 2
Q3. Bubble Sort (Step Count)
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
int step_count = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
step_count++;
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
cout << "Total Steps: " << step_count << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output of Bubble Sort
Sorted array: 11 12 22 25 34 64 90
Total Steps: 21
Q4. Selection Sort (Step Count)
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
int step_count = 0;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
step_count++;
if (arr[j] < arr[minIdx]) minIdx = j;
}
swap(arr[minIdx], arr[i]);
}
cout << "Total Steps: " << step_count << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output of Selection Sort
Sorted array: 11 12 22 25 34 64 90
Total Steps: 21
Q5. Insertion Sort (Step Count)
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
int step_count = 0;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
step_count++;
}
arr[j + 1] = key;
step_count++;
}
cout << "Total Steps: " << step_count << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output of Insertion Sort
Sorted array: 5 6 11 12 13
Total Steps: 7
Q6. Merge Sort
#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int i = 0; i < n2; i++)
R[i] = arr[m + 1 + i];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output of Merge Sort
Sorted array: 5 6 7 11 12 13
Q7. Quick Sort
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output of Quick Sort
Sorted array: 1 5 7 8 9 10
Q8. Job Sequencing Problem
#include <iostream>
#include <algorithm>
using namespace std;
struct Job {
char id;
int deadline;
int profit;
};
bool compare(Job a, Job b) {
return (a.profit > b.profit);
}
void jobSequencing(Job jobs[], int n) {
sort(jobs, jobs + n, compare);
int max_deadline = 0;
for (int i = 0; i < n; i++)
max_deadline = max(max_deadline, jobs[i].deadline);
char result[max_deadline];
bool slot[max_deadline] = {false};
int total_profit = 0;
for (int i = 0; i < n; i++) {
for (int j = min(jobs[i].deadline - 1, max_deadline - 1); j >= 0; j--) {
if (!slot[j]) {
result[j] = jobs[i].id;
slot[j] = true;
total_profit += jobs[i].profit;
break;
}
}
}
cout << "Scheduled Jobs: ";
for (int i = 0; i < max_deadline; i++)
if (slot[i]) cout << result[i] << " ";
cout << "
Total Profit: " << total_profit << endl;
}
int main() {
Job jobs[] = {{'A', 2, 100}, {'B', 1, 50}, {'C', 2, 10}, {'D', 1, 20}, {'E', 3, 30}};
int n = sizeof(jobs) / sizeof(jobs[0]);
jobSequencing(jobs, n);
return 0;
}
Output of Job Sequencing
Scheduled Jobs: A B E
Total Profit: 180
Q7. Knapsack Problem
#include <iostream>
#include <algorithm>
using namespace std;
int knapsack(int W, int wt[], int val[], int n) {
int dp[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
cout << "Maximum value in Knapsack = " << knapsack(W, wt, val, n);
return 0;
}
Output of Knapsack Problem
Maximum value in Knapsack = 220
