Week-9 (live interactive session)

22nd March 2025

Course: Problem Solving Through
Programming In C
(noc25-cs56)
by
Prof. Anupam Basu
Indian Institute of Technology Kharagpur

Present Live Interactive Session:

Ambuj
PMRF Research Scholar
Agriculture and Food Engineering Department
Indian Institute of Technology Kharagpur
1. What is the worst-case complexity of
selection sort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
1. What is the worst-case complexity of
selection sort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
The correct answer is d) O(n2)
Explanation
Let’s analyze the time complexity of the selection sort algorithm:
How Selection Sort Works
Selection sort works by repeatedly finding the minimum element from the unsorted part of the array and placing it at the beginning of the unsorted portion. This
process is repeated for the remaining unsorted part of the array.
[Link] Loop: The outer loop iterates n-1 times (where n is the number of elements in the array). Each pass of the outer loop, the smallest remaining element is
found and is placed into its correct position, so the remaining unsorted section is always 1 less than the previous pass.
[Link] Loop: The inner loop iterates through the remaining unsorted part of the array to find the smallest element. In the first iteration of the outer loop, it checks
every single item in the array. In the second pass, it checks n-1 items, in the third pass n-2 and so on.
Worst-Case Scenario
The worst-case scenario occurs when the array is in reverse order, because then on every single pass, the minimum element will have to be located from the end of
the array. However, the number of comparisons will still be the same as for any other scenario, with or without reverse ordered array.
Complexity Calculation
•Outer Loop: Iterates n-1 times.
•Inner Loop:
•In the first iteration of the outer loop, n-1 comparisons are made.
•In the second iteration, n-2 comparisons are made, and so on.
•In the last iteration, 1 comparison is made. This sums to (n-1) + (n-2) + ... + 1 = n(n-1)/2. This is approximately n2 / 2.
•Swaps: In each iteration of the outer loop there will be at most 1 swap. Thus the number of swaps will be linear with respect to n.
The overall complexity of the algorithm is thus O(n2/2) and because constants do not matter for asymptotic time complexity, the complexity can be expressed as
O(n2).
Why the other options are incorrect:
a) O(n log n): This is the time complexity of more efficient sorting algorithms like merge sort and quicksort. Selection sort does not divide the input into smaller
parts and then combine them back, so its complexity is not nlogn.
b) O(log n): This is usually the time complexity for search algorithms that have a divide and conquer strategy, and do not iterate through all of the items. Selection
sort is not a search algorithm, and it does iterate through all of the items.
c) O(n): This is the time complexity for algorithms that operate in a single pass, such as linear search. Selection sort requires multiple passes over the data.
Conclusion
The worst-case time complexity of selection sort is O(n2). The correct answer is d) O(n2).
Let’s break down the concept of Big O notation. It’s a crucial tool in computer science for understanding the efficiency of algorithms.
What is Big O Notation?
Big O notation is a mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. In
computer science, we use it to describe the time or space complexity of an algorithm as the input size grows.
Key Ideas:
[Link] on Growth: Big O notation doesn’t care about constant factors or lower-order terms. It’s all about how the algorithm’s performance scales with the input
size (often denoted as n). For example, 10n and n + 100 are both considered O(n) because their growth is dominated by the n term as n gets large.
[Link]-Case Scenario: By convention, Big O usually describes the worst-case performance of an algorithm. We want to know how bad things can get, which
guarantees an upper bound on the running time of the algorithm. However, sometimes people use it to refer to average and best case as well.
[Link] Analysis: Big O is an example of asymptotic analysis, meaning that we’re interested in what happens to an algorithm’s behavior as the input size
tends towards infinity, and not necessarily what happens for small inputs.
Common Big O Notations (Ordered from best to worst)
Here are some of the most common Big O notations you’ll encounter, with examples of algorithms that exhibit them:
•O(1) - Constant Time: The algorithm’s running time doesn’t depend on the input size. It always takes the same amount of time, no matter how big the input is.
•Example: Accessing an element in an array by its index.
•O(log n) - Logarithmic Time: The running time increases logarithmically with the input size. Typically, these algorithms divide the input problem into smaller
subproblems at each step.
•Example: Binary search on a sorted array.
•O(n) - Linear Time: The running time increases directly proportionally to the input size.
•Example: Linear search, iterating through an array once.
•O(n log n) - Linearithmic Time: The running time increases with n multiplied by a logarithmic term. Typically involves divide-and-conquer strategies.
•Example: Merge sort, quicksort.
•O(n^2) - Quadratic Time: The running time increases with the square of the input size. Often involves nested loops that compare all elements against each other.
•Example: Bubble sort, insertion sort, selection sort.
•O(2^n) - Exponential Time: The running time doubles with each addition to the input size. These algorithms are generally impractical for large inputs.
•Example: Some recursive solutions for problems like the traveling salesman problem or towers of hanoi.
•O(n!) - Factorial Time: The running time grows factorially to the size of the input. These algorithms are generally impractical for most applications.
How to Determine Big O Notation
[Link] the Dominant Operations: Look for the operations that are executed the most frequently as the input size grows. Usually,
loops and recursive calls determine the overall time complexity.
[Link] Constants and Lower-Order Terms: Only the dominant terms matter in asymptotic analysis.
•5n is O(n).
•n^2 + 3n + 10 is O(n^2).
[Link]: Count how many times the operation will be called as a function of n.
[Link] in Big O Notation: Use the notations above, based on how the function scales with n.
Example: Analyzing a Simple Loop
for (int i = 0; i < n; i++) { // Some constant-time operation printf("%d\n", i); }
•The loop runs n times.
•The operation inside the loop is O(1).
•Therefore, the overall time complexity is O(n).
Why is Big O Notation Important?
•Algorithm Comparison: It allows you to compare the efficiency of different algorithms.
•Performance Prediction: You can estimate how an algorithm’s performance will scale with increasing input sizes.
•Code Optimization: It helps you identify performance bottlenecks in your code.
•System Design: It allows you to reason about the complexity of large systems and data processing pipelines.
In summary:
Big O notation provides a high-level understanding of how an algorithm’s performance will change with input size. It allows
programmers and system designers to make informed choices about algorithms and data structures. Remember that it’s a tool for
describing asymptotic behavior and doesn’t tell you about performance for a specific small input.
2. What is the correct order of insertion
sort (in ascending order) of the array
arr[5]={8 3 5 9 4}?

a) {3 8 5 9 4} → {3 5 8 9 4} → {3 4 5 8 9}
b) {3 8 5 9 4} → {3 5 8 9 4} → {3 5 8 4 9} → {3
5 4 8 9} → {3 4 5 8 9}
c) {3 8 5 9 4} → {3 4 8 5 9} → {3 4 5 8 9} → {3
4 5 8 9}
d) {8 3 5 4 9} → {8 3 4 5 9} → {3 4 5 8 9}
2. What is the correct order of insertion
sort (in ascending order) of the array
arr[5]={8 3 5 9 4}?

a) {3 8 5 9 4} → {3 5 8 9 4} → {3 4 5 8 9}
b) {3 8 5 9 4} → {3 5 8 9 4} → {3 5 8 4 9} → {3
5 4 8 9} → {3 4 5 8 9}
c) {3 8 5 9 4} → {3 4 8 5 9} → {3 4 5 8 9} → {3
4 5 8 9}
d) {8 3 5 4 9} → {8 3 4 5 9} → {3 4 5 8 9}
3. When the Binary search is best applied
to an array?
a) For very large size array

b) When the array is sorted

c) When the array elements are mixed data type

d) When the array is unsorted

3. When the Binary search is best applied
to an array?
a) For very large size array

b) When the array is sorted

c) When the array elements are mixed data type

d) When the array is unsorted

The correct answer is b) When the array is sorted when the array is sorted, as if the elements are not ordered, it is
Explanation not possible to guarantee that the target value is in the lower or
Binary search is an efficient search algorithm, but it relies on a upper half of the current search space. For example, if the array is
crucial prerequisite: unsorted, and a mid point is chosen, it is not possible to know
•Sorted Data: Binary search requires the data to be sorted in a whether a value that is larger than the mid point is located to the
particular order (ascending or descending) to work correctly. left or right of it.
How Binary Search Works (and Why it Needs Sorted Data) Why the other options are incorrect:
[Link] and Conquer: Binary search works by repeatedly dividing a) For very large size array: While binary search is efficient for large
the search interval in half. arrays, the size of the array does not matter, as much as the sort
[Link]: It finds the middle element of the current search order. Binary search can be used on small, medium, and large size
interval. arrays. However, it requires that the array is sorted.
[Link]: It compares the target value with the middle c) When the array elements are mixed data type: The data type of
element: the array elements is not related to the requirement that the array
1. If the target matches the middle element, the search is needs to be sorted. Binary search can be used for an array
complete. containing any data type, as long as the data type has a comparison
2. If the target is less than the middle element, it discards the operator and as long as the data is sorted.
right half of the interval (because elements to the right will d) When the array is unsorted: Binary search will not work
be larger than the mid point). correctly on an unsorted array. It will not be able to perform the
3. If the target is greater than the middle element, it discards divide and conquer, as the mid point is meaningless. It will not be
the left half of the interval (because elements to the left able to reliably find the value.
will be smaller than the mid point). Conclusion
[Link]: Steps 2 and 3 are repeated until the target is found or the Binary search is best applied to an array b) When the array is
search interval becomes empty. sorted. If the array is unsorted, it will not be able to locate the value
Why Sorting is Essential correctly, and if the array is not sorted, another search algorithm
The efficiency of binary search comes from its ability to discard half (such as linear search) would be preferred.
of the remaining search space at each step. This is only possible
4. Select the code snippet which performs unordered linear search
iteratively?
a) int unorderedLinearSearch(int arr[], int size, int data) c) int unorderedLinearSearch(int arr[], int size, int data)
{ {
int index; int index;
for(int i = 0; i < size; i++) for(int i = 0; i <= size; i++)
{ {
if(arr[i] == data) if(arr[i] == data)
{ {
index = i; index = i;
break; continue;
} }
} }
return index; return index;
} }
b) int unorderedLinearSearch(int arr[], int size, int data) d) None of the above
{
int index;
for(int i = 0; i < size; i++)
{
if(arr[i] == data)
{
break;
}
}
return index;
}
4. Select the code snippet which performs unordered linear search
iteratively?
a) int unorderedLinearSearch(int arr[], int size, int data) c) int unorderedLinearSearch(int arr[], int size, int data)
{ {
int index; int index;
for(int i = 0; i < size; i++) for(int i = 0; i <= size; i++)
{ {
if(arr[i] == data) if(arr[i] == data)
{ {
index = i; index = i;
break; continue;
} }
} }
return index; return index;
} }
b) int unorderedLinearSearch(int arr[], int size, int data) d) None of the above
{
int index;
for(int i = 0; i < size; i++)
{
if(arr[i] == data)
{
break;
}
}
return index;
}
The correct answer is a) int unorderedLinearSearch(int arr[], int size, int data) { uninitialized garbage value. This behavior is acceptable as a return value
int index; for(int i = 0; i < size; i++) { if(arr[i] == data) { index = i; break; } } return and will be a good enough indicator to inform the caller that the value was
index; } not found.
Explanation b) (Incorrect):
Let’s analyze each code snippet and why option (a) is the correct implementation int unorderedLinearSearch(int arr[], int size, int data) { int index; for (int i = 0; i <
for an iterative unordered linear search: size; i++) { if (arr[i] == data) { break; } } return index; }
Understanding Linear Search •Incorrect Index Tracking: This code will exit the loop if the element is
•Linear Traversal: Linear search (or sequential search) works by checking each found, but it will not assign the index to a variable. Thus the value of the
element of an array sequentially until the target element is found or the end of variable index will be uninitialized and thus will be a garbage value.
the array is reached. Therefore, it is not possible to determine if a value was found using the
•Unordered: It doesn’t require the array to be sorted; it works on any type of returned value.
array. c) (Incorrect):
•Iterative: This means using a loop to go through the elements instead of int unorderedLinearSearch(int arr[], int size, int data) { int index; for (int i = 0; i <=
recursion. size; i++) { if (arr[i] == data) { index = i; continue; } } return index; }
•Time Complexity: The time complexity of a linear search is O(n) in the worst •Loop Condition: The loop condition i <= size will cause an out-of-bounds
case, because the algorithm has to potentially check every single item. access because valid indices range from 0 to size - 1. This will cause a crash.
Analyzing the Code Snippets •continue Statement: The use of the continue statement means that the
a) (Correct): function will continue iterating after the element is found, instead of
int unorderedLinearSearch(int arr[], int size, int data) { int index; for (int i = 0; i < returning after the first match is located. If there are multiple matches,
size; i++) { if (arr[i] == data) { index = i; break; } } return index; } only the last match index will be returned. If no matches, then index is
•Iteration: This code uses a for loop to traverse the array from index 0 up never initialized, which means that the return value is a garbage value.
to, but not including, the size of the array, incrementing one index at a d) None of the above: Incorrect as option (a) is a valid implementation.
time. Conclusion
•Comparison: Inside the loop, it compares the current element arr[i] with The code snippet that correctly implements an iterative unordered linear search
the target data. is a). It iterates through the array, checks if each element matches the target,
•Index Tracking: If the target is found, it stores the index i in the stores the index if a match is found, and uses break to exit the loop when the first
variable index and uses break to exit the loop. match is located, and returns the index where the element was found (or a
•Return Value: It returns the index. Note that if the element is not found, garbage value if not found).
the index variable is never assigned a value, and the return will be an
5. What is the best case and worst case complexity of
ordered linear search?

a) O(nlogn), O(logn)

b) O(logn), O(nlogn)

c) O(n), O(1)

d) O(1), O(n)
5. What is the best case and worst case complexity of
ordered linear search?

a) O(nlogn), O(logn)

b) O(logn), O(nlogn)

c) O(n), O(1)

d) O(1), O(n)
The correct answer is d) O(1), O(n)
Explanation
Let’s analyze the time complexity of an ordered linear search in both best-case and worst-case scenarios.
Understanding Ordered Linear Search
•Sorted Array: Ordered linear search implies that the array is sorted, either in ascending or descending order.
•Linear Traversal: Like regular linear search, it checks elements sequentially.
•Optimization: The key difference is that it can potentially terminate early if the target element is not found (if the target is smaller than the current item during
an ascending sorted search, or if the target is bigger than the current item during a descending sorted search).
•Time Complexity The overall time complexity is still O(n).
Best-Case Scenario
•The best case occurs when the target element is found at the very beginning of the array (i.e., at index 0). In this scenario, only one comparison is needed. Thus,
the time complexity is O(1).
Worst-Case Scenario
•The worst case occurs when the target element is either not present in the array, or it is present at the very end of the array. In these scenarios, the search has
to traverse all n elements. The time complexity is therefore O(n).
•If we consider an array sorted in ascending order, and the target is bigger than all of the values, we have to check all of the items before finding that it is not
there.
•If we consider an array sorted in ascending order, and the target is smaller than the first item, we only have to check the first item before we can stop the
search.
•Therefore, we can see how in the worst case, we have to check all of the items, or the array and in the best case we only have to check the first item of the
array.
Why the other options are incorrect:
a) O(n log n), O(log n): These complexities are generally associated with more efficient sorting or search algorithms (like merge sort, quicksort, or binary search).
The ordered linear search is still a linear traversal, although it can potentially stop earlier than an unordered linear search.
b) O(log n), O(n log n): Same as above, not related to the linear traversal.
c) O(n), O(1): The worst case is O(n), not O(1).
Conclusion
The best-case complexity of an ordered linear search is O(1), and the worst-case complexity is O(n). Therefore, the correct answer is d) O(1), O(n).
6. Binary Search can be categorized into which of the
following?

a) Brute Force technique

b) Divide and conquer

c) Greedy algorithm

d) Dynamic programming
6. Binary Search can be categorized into which of the
following?

a) Brute Force technique

b) Divide and conquer

c) Greedy algorithm

d) Dynamic programming
The correct answer is b) Divide and conquer
Explanation
Let’s understand why binary search falls under the divide-and-conquer paradigm:
Understanding Divide and Conquer
Divide and conquer is an algorithmic paradigm where a problem is solved by:
[Link]: Breaking the problem down into smaller subproblems of the same type.
[Link]: Solving the subproblems recursively. If a subproblem is small enough, it’s solved directly.
[Link]: Combining the solutions to the subproblems to solve the original problem.
How Binary Search Fits
Binary search perfectly exemplifies the divide-and-conquer strategy:
[Link]: The search space (the array) is repeatedly divided in half.
[Link]: The search continues in only one half of the array (either the left half or the right half). The other half is discarded, meaning that no more
effort will be placed on the other half. This can be thought of as a smaller search problem.
[Link]: There is no explicit combining step in binary search. The recursive search reduces the search problem until the solution is found (or not
found).
Why the other options are incorrect:
•a) Brute Force technique: Brute force algorithms check all possible solutions. Binary search, in contrast, systematically reduces the search space
without examining every item.
•c) Greedy algorithm: Greedy algorithms make locally optimal choices at each step with the hope of finding a globally optimal solution. Binary search
does not make locally optimal choices; it will choose either the left or right half, depending on whether the target value is greater or smaller than the
mid point.
•d) Dynamic programming: Dynamic programming solves problems by breaking them into subproblems and storing the results of those subproblems
to avoid recomputation. Dynamic programming is used to solve problems that can have overlapping subproblems, and is not a good way to solve
problems that do not have such overlapping subproblems. Binary search does not use overlapping subproblems.
Conclusion
Binary search is a prime example of a divide-and-conquer algorithm. The key is that the algorithm divides the problem (search space) into half, until it
solves the problem (find the value or not). Therefore the correct answer is b) Divide and conquer.
7. Given an array arr = {45, 77, 89, 91, 94, 98,100} and
key = 100; what are the mid values (corresponding array
elements) generated in the first and second iterations?

a) 91 and 98

b) 91 and 100

c) 91 and 94

d) 94 and 98
7. Given an array arr = {45, 77, 89, 91, 94, 98,100} and
key = 100; what are the mid values (corresponding array
elements) generated in the first and second iterations?

a) 91 and 98

b) 91 and 100

c) 91 and 94

d) 94 and 98
The correct answer is a) 91 and 98 •Since 91 < 100, we update low = 3 + 1 = 4.
Explanation [Link] 2:
Let’s trace the execution of the binary search algorithm on the given •low = 4
array and target value: •high = 6
Array and Key: •mid = (4 + 6) / 2 = 5
•arr = {45, 77, 89, 91, 94, 98, 100} •arr[5] = 98
•key = 100 •Since 98 < 100, we update low = 5+ 1 = 6.
Understanding Binary Search [Link] 3:
Recall how binary search operates: •low = 6
[Link]: Initialize low to the first index (0) and high to the last index (size •high = 6
- 1). •mid = (6 + 6) / 2 = 6
[Link]: Calculate the middle index mid = (low + high) / 2. •arr[6] = 100
[Link]: Compare arr[mid] with the key: •Since arr[6] == 100, we return the index.
•If arr[mid] equals the key, the element is found. Mid Values
•If arr[mid] is less than the key, search in the right half (low = mid The mid values generated in the first and second iterations are 91 and
+ 1). 98 respectively.
•If arr[mid] is greater than the key, search in the left half (high = Why the other options are incorrect:
mid - 1). •b) 91 and 100: The mid value in the second iteration is 98, and not
[Link]: Go to step 2 until low > high. 100.
Step-by-Step Iterations •c) 91 and 94: The mid value in the second iteration is 98, and not 94.
[Link] 1: •d) 94 and 98: The mid value in the first iteration is 91 and not 94.
•low = 0 Conclusion
•high = 6 The correct answer is a) 91 and 98.
•mid = (0 + 6) / 2 = 3
•arr[3] = 91
8. Select the appropriate pseudo code that performs selection sort
a) int min; c) int min;
for(int j=0; j<[Link]-1; j++) for(int j=0; j<[Link]-1; j++)
{ {
min = j; min = j;
for(int k=j+1; k<=[Link]-1; k++) for(int k=j+1; k<=[Link]-1; k++)
{ {
if(arr[k] < arr[min]) if(arr[k] > arr[min])
min = k; min = k;
} }
int temp = arr[min]; int temp = arr[min];
arr[min] = arr[j]; arr[min] = arr[j];
arr[j] = temp; arr[j] = temp;
} }
b) int min; d) int min;
for(int j=0; j<[Link]-1; j++) for(int j=0; j<[Link]-1; j++)
{ {
min = j; min = j;
for(int k=j+1; k<=[Link]; k++) for(int k=j+1; k<=[Link]; k++)
{ {
if(arr[k] < arr[min]) if(arr[k] > arr[min])
min = k; min = k;
} }
int temp = arr[min]; int temp = arr[min];
arr[min] = arr[j]; arr[min] = arr[j];
arr[j] = temp; arr[j] = temp;
} }
8. Select the appropriate pseudo code that performs selection sort
a) int min; c) int min;
for(int j=0; j<[Link]-1; j++) for(int j=0; j<[Link]-1; j++)
{ {
min = j; min = j;
for(int k=j+1; k<=[Link]-1; k++) for(int k=j+1; k<=[Link]-1; k++)
{ {
if(arr[k] < arr[min]) if(arr[k] > arr[min])
min = k; min = k;
} }
int temp = arr[min]; int temp = arr[min];
arr[min] = arr[j]; arr[min] = arr[j];
arr[j] = temp; arr[j] = temp;
} }
b) int min; d) int min;
for(int j=0; j<[Link]-1; j++) for(int j=0; j<[Link]-1; j++)
{ {
min = j; min = j;
for(int k=j+1; k<=[Link]; k++) for(int k=j+1; k<=[Link]; k++)
{ {
if(arr[k] < arr[min]) if(arr[k] > arr[min])
min = k; min = k;
} }
int temp = arr[min]; int temp = arr[min];
arr[min] = arr[j]; arr[min] = arr[j];
arr[j] = temp; arr[j] = temp;
} }
The correct answer is a) int min; for(int j=0; j<="[Link]-1;" k++)="" Swap: Correctly swaps the element at the current index j with the
if(arr[k]="" <="" arr[min])="" }="" int="" temp="arr[min];" identified minimum value.
arr[min]="arr[j];" arr[j]="temp;" }<="" strong="" style="box-sizing: b) (Incorrect):
border-box;"> int min; for(int j=0; j<[Link]-1; j++) { min = j; for(int k=j+1;
Explanation k<=[Link]; k++) { if(arr[k] < arr[min]) min = k; } int temp = arr[min];
Let’s analyze each code snippet and understand how selection sort arr[min] = arr[j]; arr[j] = temp; }
works: Inner Loop Error: The inner loop iterates up to k <= [Link] this
Understanding Selection Sort will cause an out of bounds error since valid indexes
[Link] Loop: The outer loop iterates through the array, one element at are 0 to [Link]-1.
a time, and identifies the minimum value to put in that spot. c) (Incorrect):
[Link] Index: In each iteration of the outer loop, it assumes that the int min; for(int j=0; j<[Link]-1; j++) { min = j; for(int k=j+1;
current index has the minimum value. The inner loop then iterates k<=[Link]-1; k++) { if(arr[k] > arr[min]) // Incorrect comparison min =
through the remaining unsorted portion of the array to find the actual k; } int temp = arr[min]; arr[min] = arr[j]; arr[j] = temp; }
minimum value. If a smaller value is found, the index is updated. Incorrect Comparison: The condition arr[k] > arr[min] will cause the
[Link]: After the inner loop finds the minimum element, it swaps the code to identify the largest value in the unsorted portion of the
minimum element with the element at the current index of the outer array instead of the smallest.
loop. d) (Incorrect):
Analyzing the Pseudo-Code int min; for(int j=0; j<[Link]-1; j++) { min = j; for(int k=j+1;
a) (Correct): k<=[Link]; k++) { if(arr[k] > arr[min]) // Incorrect comparison min = k;
int min; for(int j=0; j<[Link]-1; j++) { min = j; for(int k=j+1; } int temp = arr[min]; arr[min] = arr[j]; arr[j] = temp; }
k<=[Link]-1; k++) { if(arr[k] < arr[min]) min = k; } int temp = arr[min]; Incorrect Comparison and Inner Loop Error: The condition arr[k] >
arr[min] = arr[j]; arr[j] = temp; } arr[min] will cause the code to identify the largest value in the
Correct Logic: This code accurately implements selection sort. unsorted portion of the array instead of the smallest, and the inner
Outer Loop: Correctly iterates to [Link] - 1 loop iterates up to k <= [Link] causing an out of bounds error.
Inner Loop: Correctly iterates from j+1 to the end of the array. Conclusion
Minimum Update: Correctly identifies the minimum value in the The pseudo-code that correctly implements selection sort is a).
remaining unsorted portion of the array.
9. Consider the array A[] = {7, 2, 6, 1, 5}. Apply Insertion
Sort to sort the array in ascending order. The cost
associated with each swap operation is 20 rupees. What
is the total cost when element 1 reaches the first
position of the array?

a) 20
b) 40
c) 60
d) 80
9. Consider the array A[] = {7, 2, 6, 1, 5}. Apply Insertion
Sort to sort the array in ascending order. The cost
associated with each swap operation is 20 rupees. What
is the total cost when element 1 reaches the first
position of the array?

a) 20
b) 40
c) 60
d) 80
10. Find the output of
the following C program

a) 12 5 8 3 10
b) 5 8 3 10 12
c) 3 5 8 10 12
d) 3 8 5 10 12
10. Find the output of
the following C program

a) 12 5 8 3 10
b) 5 8 3 10 12
c) 3 5 8 10 12
d) 3 8 5 10 12