Assignment 1
a. Sort the sequence 3, 7, 4, 1, 5, 2, 8, 6, 9 using Insertion sort (show the steps on your
paper)
Answer:
Initial list:
[3, 7, 4, 1, 5, 2, 8, 6, 9]
Step 1:
Compare 7 with 3 → 7 is in correct position
[3, 7, 4, 1, 5, 2, 8, 6, 9]
Step 2:
Compare 4 with 7 → move 7 right
Compare 4 with 3 → insert after 3
[3, 4, 7, 1, 5, 2, 8, 6, 9]
Step 3:
Compare 1 with 7 → move 7
Compare 1 with 4 → move 4
Compare 1 with 3 → move 3
Insert 1 at beginning
[1, 3, 4, 7, 5, 2, 8, 6, 9]
Step 4:
Compare 5 with 7 → move 7
Compare 5 with 4 → insert after 4
[1, 3, 4, 5, 7, 2, 8, 6, 9]
Step 5:
Compare 2 with 7 → move 7
Compare 2 with 5 → move 5
Compare 2 with 4 → move 4
Compare 2 with 3 → move 3
Insert after 1
[1, 2, 3, 4, 5, 7, 8, 6, 9]
Step 6:
8 is in correct position
[1, 2, 3, 4, 5, 7, 8, 6, 9]
Step 7:
Compare 6 with 8 → move 8
Compare 6 with 7 → move 7
Insert after 5
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Step 8:
9 is in correct position
[1, 2, 3, 4, 5, 6, 7, 8, 9]
✅ Final sorted list:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
b. // Insertion Sort
void insertionSort(int arr[], int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
Assignment 2
a. Answer: Similar to Assignment 1, I believe you can do it or you can ask google or chatgpt.
b. Answer: I believe you can write the C code for this sorting algorithm or you can ask the
google or chatgpt
c. Here is a C program for Merge sort without using recursion
#include <stdio.h>
// Function to merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int temp1[n1], temp2[n2];
for (int i = 0; i < n1; i++)
temp1[i] = arr[left + i];
for (int j = 0; j < n2; j++)
temp2[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (temp1[i] <= temp2[j]) {
arr[k++] = temp1[i++];
} else {
arr[k++] = temp2[j++];
}
}
while (i < n1)
arr[k++] = temp1[i++];
while (j < n2)
arr[k++] = temp2[j++];
}
// Iterative Merge Sort function
void mergeSortIterative(int arr[], int n) {
int currSize;
int leftStart;
// Merge subarrays in bottom-up manner
for (currSize = 1; currSize < n; currSize *= 2) {
for (leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
int mid = leftStart + currSize - 1;
int rightEnd = (leftStart + 2 * currSize - 1 < n - 1)
? (leftStart + 2 * currSize - 1)
: (n - 1);
if (mid < rightEnd)
merge(arr, leftStart, mid, rightEnd);
}
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Main function
int main() {
int arr[] = {3, 7, 4, 1, 5, 2, 8, 6, 9};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, n);
mergeSortIterative(arr, n);
printf("Sorted array:\n");
printArray(arr, n);
return 0;
}
d. Please modify the program of question b as following:
– In practical, if the sub-lists are less than some threshold length (cutoff), use an algorithm
like insertion sort to sort the lists
– Otherwise, use Merge sort, again
– Modify your program with cutoff = 5
Answer:
#include <stdio.h>
#define CUTOFF 5 // Cutoff for switching to insertion sort
// Merge function to merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int temp1[n1], temp2[n2];
for (int i = 0; i < n1; i++)
temp1[i] = arr[left + i];
for (int j = 0; j < n2; j++)
temp2[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (temp1[i] <= temp2[j])
arr[k++] = temp1[i++];
else
arr[k++] = temp2[j++];
}
while (i < n1)
arr[k++] = temp1[i++];
while (j < n2)
arr[k++] = temp2[j++];
}
// Hybrid Merge Sort using cutoff for insertion sort
void hybridMergeSort(int arr[], int n) {
int currSize;
int leftStart;
// First sort small subarrays using insertion sort
for (leftStart = 0; leftStart < n; leftStart += CUTOFF) {
int right = (leftStart + CUTOFF - 1 < n - 1) ? (leftStart + CUTOFF - 1) : (n - 1);
insertionSort(arr, leftStart, right);
}
// Then merge sorted subarrays using iterative merge
for (currSize = CUTOFF; currSize < n; currSize *= 2) {
for (leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
int mid = leftStart + currSize - 1;
int rightEnd = (leftStart + 2 * currSize - 1 < n - 1) ? (leftStart + 2 * currSize - 1) : (n - 1);
if (mid < rightEnd)
merge(arr, leftStart, mid, rightEnd);
}
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Main function
int main() {
int arr[] = {3, 7, 4, 1, 5, 2, 8, 6, 9};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
printArray(arr, n);
hybridMergeSort(arr, n);
printf("Sorted array:\n");
printArray(arr, n);
return 0;
}
Assignment 3
Answer: I believe you can do it or you can ask google or chatgpt.
Assignment 4
Answer: I believe you can do it or you can ask google or chatgpt.
Assignment 5
a. Sort an array of 0’s, 1’s and 2’s: Given an array A[] consisting of 0’s, 1’s and 2’s, give an
algorithm for sorting A[]. The algorithm should put all 0’s first, then all 1’s and all 2’s last.
Example: Input = {0,1,1,0,1,2,1,2,0,0,0,1}, Output = {0,0,0,0,0,1,1,1,1,1,2,2}
b. Is there any other way of solving question a with the same time complexity.
Answer:
a. You can use bin sort or counting sort for this question. Time complexity: O(n).
b. Using Quick sort. Since we know that there are only 3 elements, 0,1 and 2 in the array,
we can select 1 as a pivot element for Quick sort. Quick sort finds the correct place for 1
by moving all 0’s to the left of 1 and all 2’s to the right of 1. For doing this it uses only
one scan. Time complexity: O(n).
Assignment 6
Determine the running time of merge sort and quicksort for
a. sorted input
b. reverse-ordered input
c. random input
Answer:
Merge sort: O(nlogn) for all questions
Quick sort: O(nlogn) for all questions
Assignment 7 (Searching)
Given an array A[0...n– 1] of n numbers containing the repetition of some number. Give an
algorithm for checking whether there are repeated elements or not. Assume that we are not
allowed to use additional space but we can use recursive algorithm. (We can use few temporary
variables and recursive function)
Hint: you should give an algorithm with O(nlogn)
Answer:
You can sort this array using Quick sort then linear checking whether there are repeated
elements or not. Time complexity: O(nlogn).
