Lab Assignment: -3.
(Recursive and non-recursive method)
3.1) Algorithm and Program for Selection Sort.
Non-Recursive Algorithm of selection Sort
1. Start with index i = 0.
2. Find the minimum element from index i to n-1.
3. Swap the minimum element with element at index i.
4. Increment i and repeat steps 2–3 until the array is sorted.
5. Stop.
Non-Recursive Program (Selection Sort)
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
printf("Abhay Kushwaha\n");
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Recursive Algorithm of selection Sort
1. If n == 1, return (base case).
2. Find the minimum element in the array (from index 0 to n-1).
3. Swap it with the first element.
4. Recursively call Selection Sort for the remaining array (from index 1 to n-1).
Recursive Program (Selection Sort)
#include <stdio.h>
int findMinIndex(int arr[], int start, int n) {
int minIndex = start;
for (int i = start + 1; i < n; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
return minIndex;
}
void selectionSortRecursive(int arr[], int start, int n) {
if (start >= n - 1) {
return;
}
int minIndex = findMinIndex(arr, start, n);
if (minIndex != start) {
int temp = arr[start];
arr[start] = arr[minIndex];
arr[minIndex] = temp;
}
selectionSortRecursive(arr, start + 1, n);
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
selectionSortRecursive(arr, 0, n);
printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
3.2) Algorithm and Program for Insertion Sort.
Non-Recursive Algorithm of Insertion Sort
1. Start from index 1 (second element).
2. Pick the element key = arr[i].
3. Compare key with all previous elements.
4. Shift all elements greater than key one position ahead.
5. Insert key at its correct position.
6. Repeat for all elements until the array is sorted.
Recursive Algorithm (Recursive Insertion Sort)
1. If n <= 1, return (base case).
2. Recursively sort the first n-1 elements.
3. Insert the last element (arr[n-1]) into the sorted subarray (arr[0..n-2]).
4. Stop when the whole array is sorted.
Program of Non- Recursive Insertion Sort
#include <stdio.h>
void insertionSortIterative(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--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Abhay Kushwaha\n");
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
insertionSortIterative(arr, n);
printf("\nSorted array (Iterative): ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Program of Recursive Insertion Sort
#include <stdio.h>
void insertionSortRecursive(int arr[], int n) {
if (n <= 1)
return;
insertionSortRecursive(arr, n - 1);
int last = arr[n - 1];
int j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Abhay Kushwaha\n");
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
insertionSortRecursive(arr, n);
printf("\nSorted array (Recursive): ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
3.3) Algorithm and Program for Quick Sort.
Non-Recursive Algorithm (Quick Sort)
1. Push initial indices (low = 0, high = n-1) onto a stack.
2. While stack is not empty:
a. Pop low and high.
b. Partition the array around a pivot → place pivot at correct position.
c. Push left subarray (low to pivot-1) onto stack if it has >1 element.
d. Push right subarray (pivot+1 to high) onto stack if it has >1 element.
3. Repeat until stack is empty.
Recursive Algorithm (Recursive Quick Sort)
1. If low < high:
a. Partition the array → pivot at correct position.
b. Recursively apply Quick Sort on left subarray (low to pivot-1).
c. Recursively apply Quick Sort on right subarray (pivot+1 to high).
2. Stop when subarray has one or zero elements.
Program Recursive Merge Sort
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int left[n1], right[n2];
for (int i = 0; i < n1; i++) left[i] = arr[l + i];
for (int j = 0; j < n2; j++) right[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (left[i] <= right[j])
arr[k++] = left[i++];
else
arr[k++] = right[j++];
}
while (i < n1) arr[k++] = left[i++];
while (j < n2) arr[k++] = right[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m); // Sort first half
mergeSort(arr, m + 1, r); // Sort second half
merge(arr, l, m, r); // Merge two halves
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Abhay Kushwaha\n");
printf("Original array: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
mergeSort(arr, 0, n - 1);
printf("\nSorted array (Recursive Merge Sort): ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Non-Recursive (Iterative) Merge Sort
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1, n2 = r - m;
int left[n1], right[n2];
for (int i = 0; i < n1; i++) left[i] = arr[l + i];
for (int j = 0; j < n2; j++) right[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (left[i] <= right[j])
arr[k++] = left[i++];
else
arr[k++] = right[j++];
}
while (i < n1) arr[k++] = left[i++];
while (j < n2) arr[k++] = right[j++];
}
void mergeSortIterative(int arr[], int n) {
int curr_size; // Size of subarrays to merge
int left_start; // Starting index of left subarray
for (curr_size = 1; curr_size < n; curr_size *= 2) {
for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
int mid = left_start + curr_size - 1;
int right_end = (left_start + 2 * curr_size - 1 < n - 1) ?
(left_start + 2 * curr_size - 1) : (n - 1);
if (mid < right_end)
merge(arr, left_start, mid, right_end);
}
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Abhay Kushwaha\n");
printf("Original array: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
mergeSortIterative(arr, n);
printf("\nSorted array (Iterative Merge Sort): ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
