Experiment No:01
Experiment Name: Insertion Sort
An array of integers is almost sorted in ascending order, except that exactly two elements are
misplaced.
Task:
1. Show how insertion sort will fix the array.
2. Count the number of shifts performed during sorting.
3. Explain why insertion sort is suitable for this case.
Task:1 Insertion Sort Fixes the Array.
Let's trace through the insertion sort process on the example array [1, 2, 4, 3, 5, 6]:
Initial array: [1, 2, 4, 3, 5, 6]
Pass 1 (i=1): Element at index 1 is 2
Compare with previous elements: 1 < 2, so no shift needed
Array remains: [1, 2, 4, 3, 5, 6]
Pass 2 (i=2): Element at index 2 is 4
Compare with previous: 2 < 4, so no shift needed
Array remains: [1, 2, 4, 3, 5, 6]
Pass 3 (i=3): Element at index 3 is 3 (misplaced)
1
Compare with 4: 3 < 4, so shift 4 to the right
Compare with 2: 3 > 2, so stop shifting
Insert 3 at position index 2
Array after insertion: [1, 2, 3, 4, 5, 6]
Pass 4 (i=4): Element at index 4 is 5
Compare with previous: 4 < 5, so no shift needed
Array remains: [1, 2, 3, 4, 5, 6]
Pass 5 (i=5): Element at index 5 is 6
Compare with previous: 5 < 6, so no shift needed
Array remains: [1, 2, 3, 4, 5, 6]
Final sorted array: [1, 2, 3, 4, 5, 6]
Task:2 Count the number of shifts performed during sorting.
Code:
public class InsertionSortShiftCount {
public static void main(String[] args) {
int[] arr = {1, 2, 4, 3, 5, 6};
int n = [Link];
2
int shifts = 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];
shifts++;
j--;
}
arr[j + 1] = key;
}
[Link]("Sorted array: ");
for (int num : arr) {
[Link](num + " ");
}
[Link]("\nNumber of shifts: " + shifts);
}
}
Output:
3
Task:3 Insertion Sort is Suitable
1. Near-Linear Time Complexity: For an array that's almost sorted, insertion sort
performs exceptionally well. In the best case (already sorted), it runs in O(n) time. For an
array with only two misplaced elements, it will run in near O(n) time.
2. Minimal Shifts Required: With only two misplaced elements, insertion sort will only
need to shift elements in the local vicinity of the misplaced items. In the example, only 1
shift was needed to fix the array.
3. Adaptive Algorithm: Insertion sort is adaptive - it takes advantage of existing order in
the input. When it encounters an element that's already in the correct position relative to
previous elements, it performs no comparisons or shifts for that element.
4. In-Place Sorting: It sorts the array without requiring additional memory, which is
efficient for memory-constrained systems.
5. Stable Sorting: Insertion sort maintains the relative order of equal elements, which can
be beneficial in certain applications.
6. Low Overhead: For small or nearly-sorted arrays, insertion sort often outperforms more
complex algorithms like quicksort or mergesort due to its low constant factors and simple
implementation.
In the given example, only one misplaced element was fixed, and it required just one shift.
In general, with exactly two misplaced elements, insertion sort will perform at most O(k) shifts
where k is the distance between the misplaced elements, making it highly efficient for this
specific scenario.
4
Experiment No:02
Experiment Name: Merge Sort
You are given an array of student records containing (ID, CGPA).
Task:
1. Sort the students by CGPA (descending).
2. If two students have the same CGPA, keep their original order unchanged.
3. Explain which property of merge sort makes this possible.
Task:1 Sort the students by CGPA
Code:
class Student {
int id;
double cgpa;
Student(int id, double cgpa) {
[Link] = id;
[Link] = cgpa;
public class MergeSortStudents {
public static void merge(Student[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
5
Student[] L = new Student[n1];
Student[] R = new Student[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i].cgpa > R[j].cgpa) {
arr[k] = L[i];
i++;
} else if (L[i].cgpa < R[j].cgpa) {
arr[k] = R[j];
j++;
} else {
arr[k] = L[i];
i++;
k++;
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
public static void mergeSort(Student[] arr, int left, int right) {
6
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
public static void main(String[] args) {
Student[] students = {
new Student(101, 3.5),
new Student(102, 3.8),
new Student(103, 3.5),
new Student(104, 3.9),
new Student(105, 3.7)
};
mergeSort(students, 0, [Link] - 1);
[Link]("Sorted by CGPA (Descending):");
for (Student s : students) {
[Link]("ID: " + [Link] + " CGPA: " + [Link]);
7
Output:
Task:2 Keeping Original Order for Equal CGPA
When two students have the same CGPA, we need to preserve their original relative order. This
is achieved through a property called stability in sorting algorithms.
The Key Rule During Merging:
When merging two sorted subarrays and encountering students with equal CGPAs, we always
take the student from the left subarray first:
if ([Link] >= [Link]) {
result[k] = leftStudent;
} else {
result[k] = rightStudent;
Works:
8
1. Left subarray contains elements that appeared earlier in the original array
2. Right subarray contains elements that appeared later in the original array
3. When CGPAs are equal, taking from left first preserves the original order
Example:
Original order of students with same CGPA (3.8):
text
Index in original array: 0 4 6
Students: [101] → [105] → [107] (order: 101, then 105, then 107)
During merge sort:
When merging subarrays containing these students
Each time two students with 3.8 are compared
The one from the left subarray (earlier position) is chosen first
Final sorted order (by CGPA descending):
text
[103(3.9), 101(3.8), 105(3.8), 107(3.8), 104(3.7), ...]
↑ ↑ ↑
Original order preserved: 101 → 105 → 107
Simple Analogy:
Think of students standing in a line with numbered tickets:
Student 101 has ticket #1
Student 105 has ticket #2
9
Student 107 has ticket #3
All have same CGPA (3.8)
When sorting by CGPA, students with same CGPA keep their ticket order. Student 101 (ticket
#1) will always appear before 105 (ticket #2), who appears before 107 (ticket #3).
The original order for equal CGPAs is preserved because merge sort is a stable sorting algorithm
- it respects the input order when sorting keys are equal by always prioritizing elements
from the left subarray during the merge process.
Task:3 Property of Merge Sort Makes This Possible
STABILITY is the property of merge sort that makes this possible.
Stability in Sorting:
A sorting algorithm is stable if it maintains the relative order of records with equal keys (i.e.,
values). In other words, if two items have the same sorting key, they appear in the sorted
output in the same order as they appeared in the input.
Merge Sort Stable:
Merge sort achieves stability through three key aspects of its implementation:
1. Divide Phase: The array is divided into left and right subarrays based on original
positions, preserving the natural order.
2. Merge Phase: When merging two sorted subarrays and encountering equal elements, the
algorithm always takes the element from the left subarray first (the one that appeared
earlier in the original array).
3. Non-destructive Merging: Elements are never swapped out of order; they're only moved
to temporary arrays and merged back in a controlled manner.
Stability Condition in Code:
10
if (leftArray[i].getCgpa() >= rightArray[j].getCgpa()) {
Stability Matters for Student Records:
Secondary Sorting: If students were previously sorted by ID, stability ensures that
within the same CGPA, they remain sorted by ID
Fairness: Maintains the original submission/registration order for students with the
same academic performance
Traceability: Makes the sorting process deterministic and reproducible
In this implementation, merge sort's stability guarantees that students with the same CGPA
(like IDs 101, 105, and 107) will appear in the sorted output exactly in the same order they
appeared in the input array.
Experiment No:03
Experiment Name: Quick Sort
An array is sorted using quick sort, where the first element is always chosen as pivot.
Task:
1. Show the partition steps for the array.
2. Identify whether this pivot strategy gives best, average, or worst case for the given input.
3. Suggest a small modification to improve performance.
Task:1 Partition Steps – Quick Sort Code (First Element Pivot)
11
Code:
public class QuickSortPivotFirst {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low + 1;
int j = high;
while (true) {
while (i <= j && arr[i] <= pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i >= j) break;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
arr[low] = arr[j];
arr[j] = pivot;
return j;
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
12
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
public static void main(String[] args) {
int[] arr = {10, 9, 8, 7, 6};
quickSort(arr, 0, [Link] - 1);
[Link]("Sorted array:");
for (int num : arr) [Link](num + " ");
Output:
Partition Steps (Illustration)
Input: [10, 9, 8, 7, 6]
13
Pivot: First element = 10
Step 1 – Partition first call:
Pivot = 10
Compare 9, 8, 7, 6 → all ≤ pivot → no swaps inside loop
Swap pivot with last smaller → 10 stays in place
Array after first partition:
[6, 9, 8, 7, 10] (pivot 10 at end)
Step 2 – Recur left [6, 9, 8, 7], pivot = 6
Compare 9, 8, 7 → all > pivot → pivot moves to first index → no real split
Array becomes:
[6, 9, 8, 7, 10] (pivot 6 at start)
Step 3 – Continue recursion
Each recursive call produces highly unbalanced partitions, always one side empty
Task:2 This pivot strategy gives best, average, or worst case for the
given input.
Input Array:
[10, 9, 8, 7, 6]
Pivot Strategy: First element of the array is always chosen as pivot.
Analysis
1. First-element pivot on this array:
14
The array is in descending order, which is completely opposite of ascending
order.
Every time the first element is chosen as pivot:
The pivot is always the largest element in the subarray.
Partitioning produces highly unbalanced subarrays:
Left subarray: empty
Right subarray: all other elements
Effect on Quick Sort:
Instead of dividing the array into roughly equal halves (which is ideal), each
partition only reduces the array size by 1 element.
This leads to maximum number of comparisons and swaps.
Time Complexity:
Worst-case number of comparisons: O(n²)
Space complexity: O(n) due to recursive calls
Conclusion
Using the first element as pivot on an already descending array produces the worst-case scenario
for Quick Sort.
Task:3 Suggest a small modification to improve performance.
Problem with First-Element Pivot
Using the first element as pivot on a sorted or reverse-sorted array produces highly
unbalanced partitions.
This causes Quick Sort to reach its worst-case time complexity O(n²).
15
Small Modification to Improve Performance
1. Random Pivot Selection
Instead of always picking the first element, choose a random element as pivot.
This prevents consistently poor partitions.
On average, partitions become more balanced → time complexity improves to O(n log
n).
Example in Java:
int pivotIndex = low + (int)([Link]() * (high - low + 1));
swap(arr, low, pivotIndex);
2. Median-of-Three Pivot
Pick the median of the first, middle, and last elements as pivot.
This ensures the pivot is closer to the “middle” value of the subarray.
Reduces chances of worst-case performance on already sorted or reverse-sorted arrays.
Example:
int mid = (low + high) / 2;
int pivotIndex = medianOfThree(arr[low], arr[mid], arr[high]);
swap(arr, low, pivotIndex);
This Improves Performance
Avoids highly unbalanced partitions.
Ensures both left and right subarrays are roughly equal in size.
Average-case time complexity becomes O(n log n) even for sorted or reverse-sorted
arrays.
Experiment No:04
Experiment Name: Fractional Knapsack
A delivery drone can carry up to 20 kg. It can carry fractions of items.
16
Item Weight (kg) Profit
A 10 60
B 5 30
C 15 45
Task:
1. Decide the order of selection.
2. Calculate the maximum profit.
3. Justify why fractional selection is better than full selection here.
Task:1 Decide the order of selection.
To maximize profit, we need to select items based on their profit-to-weight ratio (value per kg),
picking the highest ratio first.
Profit-to-Weight Ratios Calculation:
Item A: Weight = 10 kg, Profit = 60
Profit/Weight Ratio = 60 ÷ 10 = 6.0
Item B: Weight = 5 kg, Profit = 30
Profit/Weight Ratio = 30 ÷ 5 = 6.0
17
Item C: Weight = 15 kg, Profit = 45
Profit/Weight Ratio = 45 ÷ 15 = 3.0
Selection Order Decision:
Step 1: Compare ratios
Items A and B both have ratio 6.0 (tie for highest)
Item C has ratio 3.0 (lowest)
Step 2: For items with equal ratios, we can choose either order
Both A and B give same value per kg (6.0)
The order between A and B doesn't matter for total profit
We'll select: B → A → C (or A → B → C)
Final Selection Order: B (6.0), A (6.0), C (3.0)
Task:2 Calculate the maximum profit.
Code:
import [Link].*;
class Item {
String name;
int weight;
int profit;
18
double profitPerKg;
Item(String name, int weight, int profit) {
[Link] = name;
[Link] = weight;
[Link] = profit;
[Link] = (double)profit / weight;
public class FractionalKnapsack {
public static void main(String[] args) {
int capacity = 20;
Item[] items = {
new Item("A", 10, 60),
new Item("B", 5, 30),
new Item("C", 15, 45)
};
[Link](items, (i1, i2) -> [Link]([Link], [Link]));
double totalProfit = 0;
int remainingCapacity = capacity;
19
[Link]("Items selected (with fraction if needed):");
for (Item item : items) {
if ([Link] <= remainingCapacity) {
totalProfit += [Link];
remainingCapacity -= [Link];
[Link]([Link] + " (full)");
} else {
double fraction = (double) remainingCapacity / [Link];
totalProfit += [Link] * fraction;
[Link]([Link] + " (" + fraction + " fraction)");
remainingCapacity = 0;
break;
[Link]("Maximum profit = " + totalProfit);
Output:
20
Task:3 Justify why fractional selection is better than full selection
here.
1. Given:
o Drone capacity = 20 kg
o Items: A(10, 60), B(5, 30), C(15, 45)
2. If only full items are allowed (0/1 knapsack):
o The drone can carry only complete items, no fractions.
o Possible combinations within 20 kg:
A + B = 10 + 5 = 15 kg → Profit = 60 + 30 = 90
B + C = 5 + 15 = 20 kg → Profit = 30 + 45 = 75
A + C = 10 + 15 = 25 kg → exceeds capacity → not allowed
o Maximum profit with full items = 90
3. With fractional selection (fractional knapsack):
o After taking A (10 kg) and B (5 kg), remaining capacity = 5 kg
o Take 1/3 of C (5/15 kg) → Profit = 45 × 1/3 = 15
o Total profit = 60 + 30 + 15 = 105
4. Conclusion:
o Fractional selection allows the drone to use remaining capacity efficiently.
21
o Full selection leaves unused capacity and reduces profit.
o Therefore, fractional selection maximizes total profit.
Experiment No:05
Experiment Name: Fractional Knapsack
Job Scheduling (Greedy with Twist)
Each job has a deadline and profit, but two jobs cannot be scheduled consecutively (machine
cooling constraint).
Job Deadline Profit
J1 2 50
J2 1 40
J3 2 20
J4 1 10
Task:
1. Select jobs to maximize profit.
2. Show the schedule timeline.
3. Explain how this constraint affects the greedy choice.
Task:1 Select jobs to maximize profit.
22
Code:
import [Link].*;
class Job {
String name;
int deadline;
int profit;
Job(String name, int deadline, int profit) {
[Link] = name;
[Link] = deadline;
[Link] = profit;
public class JobSchedulingCooling {
public static void main(String[] args) {
Job[] jobs = {
new Job("J1", 2, 50),
new Job("J2", 1, 40),
new Job("J3", 2, 20),
new Job("J4", 1, 10)
23
};
[Link](jobs, (a, b) -> [Link] - [Link]);
int maxDeadline = 0;
for (Job job : jobs) maxDeadline = [Link](maxDeadline, [Link]);
String[] schedule = new String[maxDeadline * 2]; // Double slots to account for cooling
[Link](schedule, "-");
int totalProfit = 0;
int lastScheduled = -2;
for (Job job : jobs) {
for (int t = [Link] * 2 - 1; t >= 0; t--) {
if (schedule[t].equals("-") && t - lastScheduled >= 2) {
schedule[t] = [Link];
totalProfit += [Link];
lastScheduled = t;
break;
[Link]("Schedule timeline:");
24
for (int i = 0; i < [Link]; i++) {
[Link](schedule[i] + " ");
[Link]("\nMaximum Profit = " + totalProfit);
Output:
Task:2 Show the schedule timeline.
1. Sort jobs by profit: J1(50), J2(40), J3(20), J4(10)
2. Schedule with cooling constraint:
o Slot 0: J2 (profit 40) → first available
o Slot 2: J1 (profit 50) → cannot schedule consecutively → leave one empty after
J2
o Slot 4: J3 (profit 20) → next available after cooling
25
Schedule timeline (slots):
Time slots: 0 1 2 3 4
Schedule: J2 - J1 - J3
-represents idle slot (cooling period)
Maximum Profit = 40 + 50 + 20 = 110
Task:3 Explain how this constraint affects the greedy choice.
1. Without cooling constraint:
o We can pick the highest profit jobs and fill all slots before their deadlines.
o Simple greedy works: schedule highest profit first in the latest possible slot.
2. With cooling constraint:
o Cannot schedule jobs in consecutive slots.
o Greedy selection must skip a slot after scheduling a job.
o Some high-profit jobs might need to be moved to later available slots or even left
unscheduled.
o This reduces flexibility and can slightly alter the order of jobs selected.
Conclusion:
Greedy still works but must consider the cooling gap, otherwise the schedule may violate
the machine constraint.
Experiment No:06
Experiment Name: 0/1 Knapsack (Reasoning-Based)
A backpack has capacity 8 kg. Items cannot be broken.
Item Weight Value
26
P 3 40
Q 4 50
R 5 60
Task:
1. List all valid combinations.
2. Choose the best one.
3. Explain why greedy by value/weight fails in this case.
Task:1 List all valid combinations.
Code:
public class ZeroOneKnapsack {
public static void main(String[] args) {
String[] items = {"P", "Q", "R"};
int[] weight = {3, 4, 5};
int[] value = {40, 50, 60};
int capacity = 8;
int n = [Link];
[Link]("Valid combinations within capacity:");
27
for (int i = 0; i < (1 << n); i++) {
int totalWeight = 0;
int totalValue = 0;
String combination = "";
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
totalWeight += weight[j];
totalValue += value[j];
combination += items[j] + " ";
if (totalWeight <= capacity) {
[Link]("Items: " + combination +
"| Weight: " + totalWeight +
" | Value: " + totalValue);
28
Output:
Task:2 Choose the best one.
Code:
public class BestZeroOneKnapsack {
public static void main(String[] args) {
String[] items = {"P", "Q", "R"};
int[] weight = {3, 4, 5};
int[] value = {40, 50, 60};
int capacity = 8;
int n = [Link];
int maxValue = 0;
29
String bestCombination = "";
for (int i = 0; i < (1 << n); i++) {
int totalWeight = 0;
int totalValue = 0;
String combination = "";
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
totalWeight += weight[j];
totalValue += value[j];
combination += items[j] + " ";
if (totalWeight <= capacity && totalValue > maxValue) {
maxValue = totalValue;
bestCombination = combination;
[Link]("Best combination: " + bestCombination);
[Link]("Maximum value: " + maxValue);
30
}
Output:
Task:3 Explain why greedy by value/weight fails in this case.
For item P:
Value = 40, Weight = 3
Value/Weight = 40 ÷ 3 = 13.33
For item Q:
Value = 50, Weight = 4
Value/Weight = 50 ÷ 4 = 12.5
For item R:
Value = 60, Weight = 5
Value/Weight = 60 ÷ 5 = 12
31
Greedy Strategy:
Pick highest ratio first.
1. Pick P (13.33)
2. Remaining capacity = 5
3. Next highest ratio = Q
4. Pick Q → Total weight = 7
5. Remaining capacity = 1 (cannot add R)
Greedy result:
P+Q
Value = 90
But Optimal is:
P+R
Value = 100
Greedy Fails
Greedy makes local optimal choice (highest ratio first).
It does not check all combinations.
Because items cannot be divided (0/1 restriction),
choosing Q blocks the better combination (P + R).
Therefore, greedy does not always give global optimum in 0/1 Knapsack.
Conclusion
All valid combinations were listed.
Best combination is P + R with value 100.
Greedy by value/weight fails because 0/1 Knapsack requires checking combinations, not
just local best choices.
32
33