1.

An array A has 22, 7, 2, 19, 10, 18, 15, 13, 8, 24

elements. Demonstrate steps of Shell sorting
algorithm using the gap sequence [3, 1].

#include <iostream>
using namespace std;

void shellSort(int arr[], int n, int gaps[], int g) {

for (int k = 0; k < g; k++) { // For each gap
int gap = gaps[k];
for (int i = gap; i < n; i++) { // Perform gapped
insertion sort
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}

int main() {
 int arr[] = {22, 7, 2, 19, 10, 18, 15, 13, 8, 24};
int n = sizeof(arr) / sizeof(arr[0]);
int gaps[] = {3, 1}; // Given gap sequence
int g = sizeof(gaps) / sizeof(gaps[0]);

shellSort(arr, n, gaps, g);

cout << "Sorted array: ";

for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;

return 0;
}

Step-by-Step Demonstration (Gap Sequence [3,

1])
Initial array:
[22, 7, 2, 19, 10, 18, 15, 13, 8, 24]
Gap = 3 → Compare elements 3 positions apart:
 Indices (0,3,6,9): [22,19,15,24] → after gapped
insertion → [19,22,15,24]
 Indices (1,4,7): [7,10,13] → [7,10,13]
  Indices (2,5,8): [2,18,8] → [2,8,18]
Array after gap 3:
[19,7,2,22,10,8,15,13,18,24]
Gap = 1 → Normal insertion sort on whole array:
 Step by step → Final sorted array:
[2, 7, 8, 10, 13, 15, 18, 19, 22, 24] ✅
Develop a function F_Sort( ) that takes an array
of integers as an argument and sorts it in
ascending order of the frequency of the values. If
multiple values have the same frequency, sort
them in decreasing order of values. Example:
Input A = [9, 9, 1, 1, 2, 3, 3, 3] Output: A = [2, 9,
9, 1, 1, 3, 3, 3]

#include <iostream>
using namespace std;

// Function to sort array based on frequency and value

void F_Sort(int arr[], int n) {
int freq[100] = {0}; // Frequency array (assume
elements <= 99)

// Count frequency of each element

for (int i = 0; i < n; i++) {
freq[arr[i]] = freq[arr[i]] + 1; // Increment
frequency separately
}

// Simple bubble-style sort based on frequency and

value
for (int i = 0; i < n - 1; i++) {
 for (int j = i + 1; j < n; j++) {
if (freq[arr[i]] > freq[arr[j]] ||
(freq[arr[i]] == freq[arr[j]] && arr[i] < arr[j]))
{

// Swap arr[i] and arr[j]

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}

int main() {
int arr[] = {9, 9, 1, 1, 2, 3, 3, 3};
int n = sizeof(arr) / sizeof(arr[0]);

F_Sort(arr, n);

cout << "Sorted array: ";

for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
 cout << endl;

return 0;}
Construct an algorithm that takes an array of
integers and an target integer as arguments,
return indices of the two numbers such that they
add up to target. You may assume that each
input would have exactly one solution, and you
may not use the same element twice. You can
return the answer in any order. Discuss the
complexity of your solution. Example 1: Input:
nums = [2,7,11,15], target = 9 Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9,
we return [0, 1]. Example 2: Input: nums =
[3,2,4], target = 6 Output: [1,2] Example 3:
Input: nums = [3,3], target = 6 Output: [0,1]

#include <iostream>
using namespace std;

// Function to find indices of two numbers that add up

to target
void TwoSum(int arr[], int n, int target) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
 cout << "Indices: [" << i << "," << j << "]"
<< endl;
return; // Return after finding the first solution
}
}
}
}

int main() {
int arr[] = {2, 7, 11, 15};
int target = 9;
int n = sizeof(arr) / sizeof(arr[0]);

TwoSum(arr, n, target);

return 0;
}

 Time Complexity: O(n²) → Two nested loops

 Space Complexity: O(1) → Extra space only for
indices
4 Construct a function to return the third distinct
maximum number of an integer array. If the third
maximum does not exist, return the maximum
number.

#include <iostream>
using namespace std;

int thirdMax(int arr[], int n) {

long max1 = LONG_MIN, max2 = LONG_MIN, max3 =
LONG_MIN;

for (int i = 0; i < n; i++) {

int num = arr[i];
// Skip duplicates
if (num == max1 || num == max2 || num ==
max3)
continue;
 if (num > max1) {
max3 = max2; // Shift second to third
max2 = max1; // Shift first to second
max1 = num; // Update first max
} else if (num > max2) {
max3 = max2; // Shift second to third
max2 = num; // Update second max
} else if (num > max3) {
max3 = num; // Update third max
}
}

if (max3 != LONG_MIN)
return max3; // Third maximum exists
else
return max1; // Otherwise return maximum
}

int main() {
int arr[] = {3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);

int result = thirdMax(arr, n);

 cout << "Third maximum: " << result << endl;

return 0;
}

5.A professor attends a party and wants to

classify it based on the robe colors of the
attendees. If all the attendees are wearing
different colored robes, he calls it a girls' only
party. If any robe color is repeated, it is a boys'
party. Construct an algorithm which takes the
number of people and their robe colors as input
and prints "GIRLS" if all robe colors are unique,
or "BOYS" if there are any duplicates. Example:
Input: (3, [1, 2, 3]), output: GIRLS Input: (4, [1, 2,
2, 4]), output: BOYS

#include <iostream>
using namespace std;

void classifyParty(int n, int robes[]) {

bool duplicate = false;

for (int i = 0; i < n - 1; i++) {

for (int j = i + 1; j < n; j++) {
if (robes[i] == robes[j]) {
 duplicate = true;
break;
}
}
if (duplicate)
break;
}

if (duplicate)
cout << "BOYS" << endl;
else
cout << "GIRLS" << endl;
}

int main() {
int robes1[] = {1, 2, 3};
int n1 = sizeof(robes1) / sizeof(robes1[0]);
classifyParty(n1, robes1); // Output: GIRLS

int robes2[] = {1, 2, 2, 4};

int n2 = sizeof(robes2) / sizeof(robes2[0]);
classifyParty(n2, robes2); // Output: BOYS

return 0;
}

6 For the array [22, 7, 2, 19, 10, 18, 15, 13],

apply the Quick Sort algorithm using the middle
element as the pivot. Illustrate each step of the
sorting process clearly.

#include <iostream>
using namespace std;

// Function to partition the array using middle element

as pivot
int partition(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
int pivot = arr[mid]; // Middle element as pivot
int i = low;
int j = high;

while (i <= j) {
while (arr[i] < pivot) {
i++; // Increment i separately
}
 while (arr[j] > pivot) {
j--; // Decrement j separately
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
return i;
}

// Quick Sort function

void quickSort(int arr[], int low, int high) {
if (low < high) {
int index = partition(arr, low, high);
quickSort(arr, low, index - 1);
quickSort(arr, index, high);
}
}

// Function to print array

void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int arr[] = {22, 7, 2, 19, 10, 18, 15, 13};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";

printArray(arr, n);

quickSort(arr, 0, n - 1);

cout << "Sorted array: ";

printArray(arr, n);

return 0;
}

Step-by-Step Illustration (Middle Pivot)

Initial array: [22, 7, 2, 19, 10, 18, 15, 13]
Step 1: Pivot = middle = 19 → Partition → [7, 2, 10, 18,
13, 15, 19, 22]
Step 2: Left subarray [7,2,10,18,13,15] → pivot = 10 →
Partition → [7,2,10,18,13,15]
Step 3: Right subarray [18,13,15] → pivot = 13 →
Partition → [13,15,18]
Step 4: Combine → Final sorted array → [2, 7, 10, 13,
15, 18, 19, 22] ✅
[Link] are a software engineer in a startup
developing a real-time messaging app. The app
maintains a chat history for each user and also
supports temporary notifications that appear for
a few seconds before disappearing. The system
needs to handle the following requirements: Chat
History: Users can scroll back to see older
messages. Messages are mostly appended at the
end in the order they are received. Occasionally,
a user deletes a message from the middle of the
history. Random access to a specific message by
index is common (e.g., show the 10th last
message). Temporary Notifications: Notifications
arrive frequently and are removed as soon as
they expire. Insertions and deletions occur at
both ends of the sequence. The total number of
notifications is small and varies dynamically.
Select the most suitable linear data structure for
each requirement and justify.

1. Chat History:
 Data Structure: Dynamic Array (vector / custom
class)
 Reason:
o Append at end → O(1)
o Random access by index → O(1)
o Occasional middle deletion → O(n), acceptable
2. Temporary Notifications:
 Data Structure: Deque (deque)
 Reason:
o Insertions/deletions at both ends → O(1)
o Flexible size for small, dynamic number of
notifications
Given an array Numbers of integers 0, 1, or 2,
where each element represents a color — 0 for
red, 1 for white, and 2 for blue — construct a
function to sort the array in-place so that all
elements of the same color are grouped together
in the order red → white → blue.

#include <iostream>
using namespace std;

void sortColors(int arr[], int n) {

int low = 0, mid = 0, high = n - 1; // three pointers

while (mid <= high) {

if (arr[mid] == 0) { // red (0)
int temp = arr[low];
arr[low] = arr[mid];
arr[mid] = temp;
low++;
mid++;
}
 else if (arr[mid] == 1) { // white (1)
mid++;
}
else { // blue (2)
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
high--;
}
}
}

int main() {
int arr[] = {2, 0, 2, 1, 1, 0};
int n = 6;

sortColors(arr, n);

cout << "Sorted Colors: ";

for (int i = 0; i < n; i++)
cout << arr[i] << " ";

return 0;
}
Given an array of 10,000 integers, which sorting
algorithm
would you select among Insertion Sort, Shell
Sort, Radix
Sort, Quick Sort, and Merge Sort to achieve the
best
performance and why?

For an array of 10,000 integers, the most efficient

sorting algorithm is Quick Sort.
Justification:
1. Insertion Sort
o Time complexity: O(n²)
o Suitable only for small or nearly sorted
datasets.
o ❌ Not efficient for large arrays like 10,000
elements.
2. Shell Sort
o Improvement over Insertion Sort but still not
optimal.
o Average complexity ≈ O(n¹·⁵).
o ❌ Slower compared to Quick Sort for large
datasets.
3. Radix Sort
 o Works efficiently for integers but needs extra
memory and depends on the number range.
o ⚠️Not always the best for general-purpose
sorting.
4. Merge Sort
o Time complexity: O(n log n), stable sorting.
o ❌ Requires additional O(n) space, which
increases memory usage.
5. Quick Sort
o Average time complexity: O(n log n)
o Space complexity: O(log n)
o Performs in-place sorting, needs minimal
memory.
o Shows excellent performance for large
datasets like 10,000 elements.
o ✅ Hence, it is the most suitable algorithm in
this case.

Conclusion:
Therefore, among Insertion Sort, Shell Sort, Radix Sort,
Quick Sort, and Merge Sort —
Quick Sort provides the best performance for sorting an
array of 10,000 integers,
due to its O(n log n) average complexity and in-place
implementation
[Link](int n) { int x = 1, k; if (n == 1) return x; for
(k = 1; k < n; ++k) x = x + fun(k) * fun(n - k);
return x; } Solve and explain the output of the
above function for n = 5.

The function fun(n) is recursive:

 Base case: fun(1) = 1
 Recursive case: fun(n) = 1 + Σ (fun(k) * fun(n - k))
for k = 1 to n-1.
Step-by-step calculation for n = 5:
1. fun(1) = 1
2. fun(2) = 1 + fun(1)*fun(1) = 1 + 1*1 = 2
3. fun(3) = 1 + fun(1)*fun(2) + fun(2)*fun(1) = 1 +
1*2 + 2*1 = 5
4. fun(4) = 1 + fun(1)*fun(3) + fun(2)*fun(2) +
fun(3)*fun(1) = 1 + 5 + 4 + 5 = 15
5. fun(5) = 1 + fun(1)*fun(4) + fun(2)*fun(3) +
fun(3)*fun(2) + fun(4)*fun(1) = 1 + 15 + 10 + 10
+ 15 = 51
Output:
fun(5) = 51
Explanation for exam:
 The function recursively computes sums of
products of all partitions of n.
 For n = 5, after evaluating all partitions, the final
output is 51

Given the array [3, 6, 8, 10, 1, 2, 1], demonstrate

how Merge Sort works showing all steps

Given Array: [3, 6, 8, 10, 1, 2, 1]

Step 1: Split the array recursively

[3, 6, 8, 10, 1, 2, 1]
→ Left: [3, 6, 8]
→ Right: [10, 1, 2, 1]

Step 2: Split and sort Left Half [3, 6, 8]

[3, 6, 8] → [3] & [6, 8]
[6, 8] → [6] & [8] → merge → [6, 8]
Merge [3] & [6, 8] → [3, 6, 8]

Step 3: Split and sort Right Half [10, 1, 2, 1]

[10, 1, 2, 1] → [10, 1] & [2, 1]
[10, 1] → [10] & [1] → merge → [1, 10]
[2, 1] → [2] & [1] → merge → [1, 2]

Merge [1, 10] & [1, 2] → compare stepwise:

1 ≤ 1 → pick 1
Next 1 ≤ 10 → pick 1
2 ≤ 10 → pick 2
Then 10 → pick 10
Result → [1, 1, 2, 10]

Step 4: Merge Left & Right Halves

Left: [3, 6, 8]
Right: [1, 1, 2, 10]

Compare stepwise:
1 ≤ 3 → pick 1
1 ≤ 3 → pick 1
2 ≤ 3 → pick 2
3 ≤ 10 → pick 3
6 ≤ 10 → pick 6
8 ≤ 10 → pick 8
10 → pick 10

Final Sorted Array → [1, 1, 2, 3, 6, 8, 10]

Step 5: Final Answer
[1, 1, 2, 3, 6, 8, 10]
Explanation (short for exam):
 Merge Sort works by recursively splitting the array
until single elements.
 Then it merges subarrays step by step in sorted
order.
 Time Complexity: O(n log n), Space Complexity:
O(n).
14 Given an integer array numbers, Construct a
function to return true if any value appears at
least twice in the array, and return false if every
element is distinct

#include <iostream>
using namespace std;

bool hasDuplicate(int arr[], int n) {

for(int i = 0; i < n-1; i++) {
for(int j = i+1; j < n; j++) {
if(arr[i] == arr[j]) // duplicate found
return true;
}
}
return false; // all elements distinct
}
int main() {
int arr[] = {1, 2, 3, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);

if(hasDuplicate(arr, n))
cout << "True";
else
cout << "False";

return 0;
}
Given an array numbers containing n distinct
numbers in the range [0, n], construct a function
to return the only number in the range that is
missing from the array.

#include <iostream>
using namespace std;

int missingNumber(int arr[], int n) {

int totalSum = n*(n+1)/2;
int sumArr = 0;
for(int i = 0; i < n; i++)
sumArr += arr[i];
return totalSum - sumArr;
}

int main() {
int arr[] = {3, 0, 1};
int n = sizeof(arr)/sizeof(arr[0]);
 cout << "Missing Number: " << missingNumber(arr,
n) << endl;
return 0;
}
15 Given an array numbers containing n distinct
numbers in the range [0, n], construct a function
to return the only number in the range that is
missing from the array.

#include <iostream>
using namespace std;

int missingNumber(int arr[], int n) {

int totalSum = n*(n+1)/2;
int sumArr = 0;
for(int i = 0; i < n; i++)
sumArr += arr[i];
return totalSum - sumArr;
}

int main() {
int arr[] = {3, 0, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Missing Number: " << missingNumber(arr,
n) << endl;
 return 0;
}

16 Illustrate working of Radix Sort for the array

[170, 45, 75, 90, 802, 24, 2, 66]

Given Array:
[170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Sort by 1’s place (Least Significant Digit)

Look at last digit of each number:
Numb 1’s
er Digit
170 0
45 5
75 5
90 0
802 2
24 4
2 2
66 6
Sorting by 1’s digit → [170, 90, 802, 2, 24, 45, 75,
66]

Step 2: Sort by 10’s place

Look at tens digit of each number (0 if no tens place):
Numb 10’s
er Digit
170 7
90 9
802 0
2 0
24 2
45 4
75 7
66 6
Sorting by 10’s digit → [802, 2, 24, 45, 66, 170, 75,
90]

Step 3: Sort by 100’s place (Most Significant

Digit)
Look at hundreds digit (0 if no hundreds place):
Numb 100’s
er Digit
802 8
2 0
24 0
45 0
66 0
Numb 100’s
er Digit
170 1
75 0
90 0
Sorting by 100’s digit → [2, 24, 45, 66, 75, 90, 170,
802] ✅

Step 4: Final Sorted Array

[2, 24, 45, 66, 75, 90, 170, 802]

Stepwise Exam Explanation (8 Marks Ready)

1. Radix Sort processes numbers digit by digit
starting from LSD to MSD.
2. At each step, use Counting Sort to sort numbers
according to current digit.
3. After sorting by all digits, array becomes fully
sorted.
4. Works best for integers and has Time
Complexity: O(d*(n+k)) where d=number of
digits, k=range of digit (0-9)
5. Space Complexity: O(n+k)
17 Consider the below program, interpret the
operation it performs. Justify. void fun(int arr[],
int n) { if (n == 1) return; int count = 0; for (int
i=0; i arr[i+1]){ swap(arr[i], arr[i+1]); count+
+; } return; fun(arr, n-1); }

The given function fun() performs the operation of a

Recursive Bubble Sort.
In every call, the loop compares each pair of adjacent
elements in the array.
If arr[i] > arr[i+1], the elements are swapped — this
moves the largest element to the end in each pass.
Then the function is recursively called for the first
(n-1) elements, sorting the remaining part of the
array.
The recursion stops when n == 1, which is the base
case.
Hence, this function sorts the array in ascending
order using the Bubble Sort technique
implemented recursively.
Time Complexity: O(n²)
Space Complexity: O(n) (due to recursion)
18 Construct a function that takes a string 's'
representing an attendance record for a student
as input. Each character in the string signifies
whether the student was absent, late, or present
on that day. The record only contains the
following three characters: 'A': Absent, 'L': Late,
'P': Present. Construct a function that returns a
boolean value indicating the student is eligible
for an attendance award or not. Eligible is
decided as per the following criteria: 1. The
student was absent ('A') for strictly fewer than 2
days total. 2. The student was never late ('L') for
3 or more consecutive days

#include <iostream>
using namespace std;

bool checkRecord(string s) {
int absent = 0, late = 0;

for (int i = 0; i < [Link](); i++) {

 if (s[i] == 'A') {
absent++;
if (absent >= 2)
return false;
}
if (s[i] == 'L') {
late++;
if (late >= 3)
return false;
} else {
late = 0; // reset if 'P' or 'A'
}
}
return true;
}

int main() {
string s = "PPALLP";
if (checkRecord(s))
cout << "Eligible for Attendance Award";
else
cout << "Not Eligible for Attendance Award";
return 0;
}
Explanation:
1. The function checkRecord() takes a string s as
input.
2. It counts how many times the student was absent
('A').
o If absent ≥ 2 → immediately return false (not
eligible).
3. It also tracks consecutive late ('L') days.
o If late ≥ 3 continuously → return false (not
eligible).
4. If both conditions are satisfied → return true
(eligible)
Construct a function to sort students' grades to
determine ranks. The system should sort
students by their average grades and, in case of
ties, by their names. your solution should be
efficient wrt time complexity. Discuss the
complexity.

#include <iostream>
#include <string>
using namespace std;

class Student {
public:
string name;
float avg;
};
int main() {
int n;
cout << "Enter number of students: ";
cin >> n;

Student s[100];

for (int i = 0; i < n; i++) {

cout << "Enter name and average marks: ";
cin >> s[i].name >> s[i].avg;
}

// Sort by average (descending), then by name

(ascending)
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (s[i].avg < s[j].avg ||
(s[i].avg == s[j].avg && s[i].name >
s[j].name)) {
Student temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
 }

cout << "\n--- Student Rank List ---\n";

for (int i = 0; i < n; i++) {
cout << "Rank " << i + 1 << ": " << s[i].name
<< " (" << s[i].avg << ")\n";
}

return 0;}
[Link] event management system needs to sort a
list of scheduled events by their start times to
create a daily agenda. The system must ensure
that events are ordered correctly and efficiently.
Construct an algorithm for the same.

Step-by-Step Algorithm
1. Start
2. Input number of events n.
3. For each event i, read:
• Event_Name[i]
• Start_Time[i]
4. Apply Merge Sort (since it is stable and efficient).
5. Divide the event list into two halves recursively.
6. Sort each half by comparing Start_Time.
7. Merge the two halves by arranging events in
increasing order of Start_Time.
 8. Output the sorted list of events.
9. Stop

Pseudocode
Algorithm Sort_Events_By_StartTime(Event[],
StartTime[], n)
Begin
If n > 1 then
mid ← n / 2
left ← first half of array
right ← second half of array
Sort_Events_By_StartTime(left, mid)
Sort_Events_By_StartTime(right, n - mid)
Merge(left, right, Event, StartTime)
End If
End

Example
Event Start
Name Time
Seminar 1400
Meeting 900
Workshop 1100
Event Start
Name Time
Lunch 1300
After Sorting (by start time):
Event Start
Name Time
Meeting 900
Workshop 1100
Lunch 1300
Seminar 1400

Justification (Why Merge Sort)

 Merge Sort is stable (maintains order of equal
start times).
 Efficient for large event lists.
 Works in O(n log n) time, better than O(n²)
methods.
 Predictable performance (not affected by data
order).

Complexity Analysis
 Time Complexity: O(n log n)
 Space Complexity: O(n)
 Best for large, dynamic event lists
Conclusion
Hence, using Merge Sort efficiently arranges all
events by their start time,
helping the system to generate an accurate daily
agenda in minimal time.

[Link] a function to merge two sorted

arrays to get a new sorted array having unique
elements of both the arrays in sorted order.

#include <iostream>
using namespace std;

void mergeUnique(int A[], int n, int B[], int m) {

int C[100];
int i = 0, j = 0, k = 0;

// Step 1: Merge both arrays

while ((i < n) && (j < m)) {
if (A[i] < B[j]) {
C[k++] = A[i++];
}
else if (A[i] > B[j]) {
C[k++] = B[j++];
}
else {
C[k++] = A[i];
i++;
j++;
}
}

// Step 2: Copy remaining elements

while (i < n) {
C[k++] = A[i++];
}
while (j < m) {
C[k++] = B[j++];
}

// Step 3: Display unique elements

cout << "Merged Unique Sorted Array: ";
 for (int x = 0; x < k; x++) {
if ((x == 0) || (C[x] != C[x - 1])) {
cout << C[x] << " ";
}
}
}

int main() {
int A[] = {1, 3, 5, 7};
int B[] = {2, 3, 6, 7, 8};
int n = 4;
int m = 5;

mergeUnique(A, n, B, m);

return 0;
}
[Link] an algorithm to sort a set of names
using Shell Sort

Algorithm: Shell Sort for Names

1. Start
2. Input the number of names and store them in an
array names[].
3. Set gap = n / 2.
4. Repeat while gap > 0
a. For each i from gap to n - 1:
• Set temp = names[i]
• Set j = i
• While j >= gap and names[j - gap] > temp
→ Set names[j] = names[j - gap]
→ Set j = j - gap
• Set names[j] = temp
b. Reduce the gap → gap = gap / 2
5. Display the sorted list of names.
 6. Stop

Time Complexity:
 Best: O(n log n)
 Average: O(n^(3/2))
 Worst: O(n²)

[Link] Sort has a worst-case time complexity

of O(n²). Demonstrate under what condition this
occurs and suggest a method to avoid it.
Condition for Worst Case:
 The worst case (O(n²)) occurs when the pivot
element chosen is always the smallest or
largest element in the array.
 This makes the partition highly unbalanced, with
one sub-array having (n–1) elements and the other
having 0.
 Example:
o If the input array is already sorted (ascending
or descending),
and we always pick the first or last element
as the pivot,
Quick Sort repeatedly divides it into
unbalanced parts.
o Hence, number of comparisons becomes:
n + (n–1) + (n–2) + ... + 1 = O(n²).
🔹 Example:
For array [1, 2, 3, 4, 5]
If pivot = first element each time →
Partitions become:
 [ ] and [2,3,4,5] → [ ] and [3,4,5] → …
This leads to worst-case recursion.

🔹 How to Avoid It:

1. Choose a Better Pivot:
o Use “Median-of-Three” method — pick the
median of first, middle, and last elements
as pivot.
2. Randomized Quick Sort:
o Choose the pivot randomly to minimize the
chance of unbalanced partitions.
3. Hybrid Approach:
o For small subarrays, switch to Insertion Sort.

🔹 Complexity Summary:
Time
Case
Complexity
Best Case O(n log n)
Average
O(n log n)
Case
Worst Case O(n²)
[Link] the step-by-step process to sort the
given array of months in alphabetical order using
using Quick Sort considering the last element as
pivot. {Jan, Feb, Mar, Apr, May, Jun, Jul, Aug,
Sep}

Step-by-Step Process:

Initial Array:
{Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep}

---

Step 1:

Pivot = Sep
→ All other months come before "Sep"
alphabetically.
✅ So, pivot “Sep” stays at the end (no swap).
Left part to sort = {Jan, Feb, Mar, Apr, May, Jun,
Jul, Aug}

---

Step 2:

Pivot = Aug (last element of left part)

Compare all with “Aug” alphabetically:

“Apr” < “Aug” → left

“Jan, Feb, Mar, May, Jun, Jul” > “Aug” → right

After placing pivot correctly:

➡ {Apr, Aug, Jan, Feb, Mar, May, Jun, Jul, Sep}

---
Step 3:

Now sort right part {Jan, Feb, Mar, May, Jun, Jul}
Pivot = Jul
All (Jan, Feb, Mar, May, Jun) < Jul
➡ Pivot stays in place.
Array = {Apr, Aug, Jan, Feb, Mar, May, Jun, Jul,
Sep}

---

Step 4:

Sort {Jan, Feb, Mar, May, Jun}

Pivot = Jun
All (Jan, Feb, Mar, May) < Jun
➡ Pivot stays in place.

---

Step 5:
Sort {Jan, Feb, Mar, May}
Pivot = May
All (Jan, Feb, Mar) < May
➡ Pivot stays in place.

---

Step 6:

Sort {Jan, Feb, Mar}

Pivot = Mar
All (Jan, Feb) < Mar
➡ Pivot fixed.

---

Step 7:

Sort {Jan, Feb}

Pivot = Feb
Compare:
“Jan” < “Feb” ✅
➡ No swap needed, already in correct order.
(Sorted part = {Jan, Feb})

---

✅ Final Sorted Array:

{Apr, Aug, Feb, Jan, Jul, Jun, Mar, May, Sep}

(Alphabetical order based on first 3 letters)

---

Time Complexity:

Best / Average Case: O(n log n)

Worst Case: O(n²) (when pivot is

smallest or largest)
[Link] the given array using merge sort and
determine the total number of comparisons
made. Show the step-by-step process. {E, A, S, Y,
Q, U, E, S, T, I, O, N}

Step 1: Divide the Array

We divide until single elements remain.

{E, A, S, Y, Q, U, E, S, T, I, O, N}

→ Left half: {E, A, S, Y, Q, U}

→ Right half: {E, S, T, I, O, N}

Further divide:
→ {E, A, S}, {Y, Q, U}, {E, S, T}, {I, O, N}

Now divide again:

→ {E, A, S} → {E, A}, {S} → {E}, {A}, {S}
→ {Y, Q, U} → {Y, Q}, {U} → {Y}, {Q}, {U}
→ {E, S, T} → {E, S}, {T} → {E}, {S}, {T}
→ {I, O, N} → {I, O}, {N} → {I}, {O}, {N}

Now all are single elements: {E}, {A}, {S}, {Y}, {Q},
{U}, {E}, {S}, {T}, {I}, {O}, {N}

---

Step 2: Start Merging in Sorted Order

⿡ Merge {E} & {A} → {A, E} → (1 comparison)

⿢ Merge {Y} & {Q} → {Q, Y} → (1 comparison)
⿣ Merge {E} & {S} → {E, S} → (1 comparison)
⿤ Merge {I} & {O} → {I, O} → (1 comparison)

---

Step 3: Merge Next Level

⿥ Merge {A, E} & {S} → {A, E, S} → (2 comparisons)

⿦ Merge {Q, Y} & {U} → {Q, U, Y} → (2 comparisons)
⿧ Merge {E, S} & {T} → {E, S, T} → (2 comparisons)
⿨ Merge {I, O} & {N} → {I, N, O} → (2 comparisons)

---

Step 4: Merge Halves

⿩ Merge {A, E, S} & {Q, U, Y} → {A, E, Q, S, U, Y} → (5

comparisons)
🔟 Merge {E, S, T} & {I, N, O} → {E, I, N, O, S, T} → (5
comparisons)

---

Step 5: Final Merge

1⿡ Merge {A, E, Q, S, U, Y} & {E, I, N, O, S, T} →

✅ {A, E, E, I, N, O, Q, S, S, T, U, Y}
→ (9 comparisons)

---
Step 6: Total Comparisons

= 1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 5 + 5 + 9 = 31
comparisons

---

Final Answer:

Sorted Array: {A, E, E, I, N, O, Q, S, S, T, U, Y}

Total Comparisons: 31
Time Complexity: O(n log n)
Space Complexity: O(n)
32 Construct a recursive version of Insertion Sort
and illustrate
its execution on an array of 5 integers.

#include <iostream>
using namespace std;

void recInsertion(int a[], int n) {

if (n <= 1)
return;

recInsertion(a, n - 1);

int key = a[n - 1];

int j = n - 2;

while (j >= 0 && a[j] > key) {

a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}

int main() {
int a[5] = {5, 2, 4, 6, 1};
recInsertion(a, 5);

cout << "Sorted array: ";

for (int i = 0; i < 5; i++)
cout << a[i] << " ";
return 0;
}
Illustration of Execution:
Initial Array: {5, 2, 4, 6, 1}
1️⃣ Call 1: recInsertion(a, 5)
→ Sort first 4 elements (recursive call)
2️⃣ Call 2: recInsertion(a, 4)
→ Sort first 3 elements
3️⃣ Call 3: recInsertion(a, 3)
→ Sort first 2 elements
4️⃣ Call 4: recInsertion(a, 2)
→ Sort first 1 element → base case reached
Now insertion happens while returning back 👇
➡ After Call 4: Insert 2 in {5} → {2, 5}
➡ After Call 3: Insert 4 → {2, 4, 5}
➡ After Call 2: Insert 6 → {2, 4, 5, 6}
➡ After Call 1: Insert 1 → {1, 2, 4, 5, 6}
Final Sorted Array:
{1, 2, 4, 5, 6}