Question 1:
Discuss recursion in brief and write down its generic algorithm.
Recursion is a programming technique where a function calls itself directly or indirectly to solve
a problem. The problem is divided into smaller sub-problems of the same type, and these sub-
problems are solved individually. Recursion is commonly used in problems that can be broken
down into simpler, repetitive tasks.
Key components of recursion:
1. Base Case:
The condition under which the recursion ends. This prevents infinite recursion and
typically handles the simplest instance of the problem.
2. Recursive Case:
The part of the function where it calls itself with a subset of the original problem.
Generic Algorithm for Recursion:
void recursiveFunction(parameters) {
if (baseCaseCondition(parameters)) {
// Handle base case
return baseCaseResult;
} else {
// Perform some operation
recursiveFunction(modifiedParameters);
}
}
Question 2:
Code the following algorithms and simulate (dry-run) these by taking an unsorted
array with 05 elements:
Let's take the unsorted array: [5, 3, 8, 4, 2]
1. Insertion Sort
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
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 = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Let's simulate the dry run of the Insertion Sort algorithm for the given array `[5, 3, 8, 4, 2]`.
Initial Array:
[5, 3, 8, 4, 2]
Iteration 1:
-i=1
- key = arr[1] = 3
-j=i-1=0
- Compare key (3) with arr[j] (5):
- Since 3 < 5, move 5 to the right: arr[j + 1] = arr[j]
- Decrement j: j = -1
- Place key in the correct position: arr[j + 1] = 3
Array after iteration 1:
[3, 5, 8, 4, 2]
Same process repeats for the rest of code.
Output:
23458
2. Selection Sort
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(arr[min_idx], arr[i]);
}
}
int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Iteration 1:
Step 1: Initialize min_idx
-i=0
- min_idx = i = 0
- Initial arr[min_idx] = arr[0] = 5
Step 2: Find the minimum element in the unsorted portion of the array
- j = 1: Compare arr[j] = 3 with arr[min_idx] = 5
- 3 < 5, so update min_idx = j = 1
- j = 2: Compare arr[j] = 8 with arr[min_idx] = 3
- 8 > 3, so min_idx remains 1
- j = 3: Compare arr[j] = 4 with arr[min_idx] = 3
- 4 > 3, so min_idx remains 1
- j = 4: Compare arr[j] = 2 with arr[min_idx] = 3
- 2 < 3, so update min_idx = j = 4
Step 3: Swap the found minimum element with the first element**
- Swap arr[min_idx] = arr[4] = 2 with arr[i] = arr[0] = 5
- After swapping: arr[0] = 2, arr[4] = 5
Array after Iteration 1:
[2, 3, 8, 4, 5]
Output:
23458
3. 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 j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
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[] = {5, 3, 8, 4, 2};
int arr_size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, arr_size - 1);
for (int i = 0; i < arr_size; i++)
cout << arr[i] << " ";
return 0;
}
Output:
23458
4. 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 - 1; 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[] = {5, 3, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output:
23458