Searching and Sorting : MCQs & PYQs with Explanation

Option B

In Bubble Sort, elements are compared with their adjacent elements, and an interchange (swap) occurs whenever two adjacent elements are in the wrong order.
The number of interchanges required to sort a sequence is equal to the number of inversions in that sequence. 
An inversion is a pair of letters in which the earlier letter should come after the later letter in alphabetical order.

• The given sequence is: S O R T E D
• The correct alphabetical order is: D E O R S T

Now count the inversions. 

• S is greater than O, R, E, and D, giving 4 interchanges.
• O is greater than E and D, giving 2 interchanges. 
• R is greater than E and D, giving 2 interchanges. 
• T is greater than E and D, giving 2 interchanges. 
• E is greater than D, giving 1 interchange.

Total interchanges = 4+2+2+2+1 = 11.

Option C

Selection sort is a sorting algorithm in which the smallest element is repeatedly selected from the unsorted part of the array and placed at its correct position. 
For n elements, the algorithm performs comparisons approximately equal to [n(n−1)]/2. Since the dominant term is n², the time complexity of selection sort is O(n²).

Option A

The given array state is {25, 75, 95, 125, 80, 5, 10}. This indicates that the first four elements are already sorted, and insertion sort will now continue with the remaining elements.
First, 80 is inserted into the sorted part {25, 75, 95, 125}. It is compared with 125, 95, and 75 before being placed in its correct position. This takes 3 comparisons. The array becomes {25, 75, 80, 95, 125, 5, 10}.
Next, 5 is inserted. It is compared with 125, 95, 80, 75, and 25 before reaching the beginning of the array. This requires 5 comparisons. The array becomes {5, 25, 75, 80, 95, 125, 10}.
Finally, 10 is inserted. It is compared with 125, 95, 80, 75, 25, and then with 5 before being placed correctly. This takes 6 comparisons.
So,
For 80, 3 comparisons.
For 5, 5 comparisons.
For 10, 6 comparisons.
Therefore, total comparison, 3+5+6 =14.

Option D

The best-case time complexity of Quick Sort occurs when the pivot divides the array into two equal halves at every recursive step.

Option C

In Insertion Sort, the array is conceptually divided into two parts:

• Sorted Portion (Left Side)
• Unsorted Portion (Right Side)

During each iteration, the algorithm takes the next element from the unsorted part and inserts it into its correct position within the sorted part by shifting larger elements to the right.
Thus, after the Kth iteration, the first (K+1) elements become sorted.
Array Initially:
10, 5, 16, 2, 8, 9
Iteration 1:
Insert 5 into the sorted portion [10].
5, 10, 16, 2, 8, 9
Now first 2 elements are sorted.
Iteration 2:
Insert 16 into the sorted portion [5, 10].
Since 16 is larger than both, it stays at the end.
5, 10, 16, 2, 8, 9
Now first 3 elements are sorted.
Iteration 3:
Insert 2 into the sorted portion [5, 10, 16].
All elements shift right.
2, 5, 10, 16, 8, 9
This exactly matches the array given in the question after three iterations.

Option C

Quicksort is a popular sorting algorithm used to arrange elements in ascending or descending order. It is based on the Divide and Conquer technique.
In Divide and Conquer:

• The problem is divided into smaller subproblems.
• Each subproblem is solved separately.
• The solutions are combined to get the final result.

Option A

To arrange in increasing order, we compare time complexities of the given algorithms. Binary Search has time complexity O(log n), Merge Sort has O(n log n), and Bubble Sort has O(n²).
Since log n < n log n < n², the increasing order is Binary Search → Merge Sort → Bubble Sort.

Option A

A recurrence relation is an equation that expresses the running time of a problem in terms of smaller instances of the same problem. It is used in the analysis of recursive algorithms because recursion naturally breaks a large problem into smaller subproblems.

By writing and solving the recurrence relation, we can calculate the overall time complexity of the algorithm in an exact and systematic way.

In the best case of Quick Sort, each partition splits the array into two equal halves. The partitioning step itself requires scanning the entire array once, which takes Θ(n) time. After this step, two recursive calls are made on subarrays of size n/2 each, giving 2T(n/2). Therefore, the recurrence relation can be expressed as T(n) = 2T(n/2) + Θ(n). By applying the Master Theorem to this recurrence, we find that the solution is T(n) = Θ(n log n).

Option D

Binary search works only on a sorted list. It repeatedly divides the search space into halves, giving a time complexity of O(log₂ n). In an unsorted list, binary search cannot be applied.

Option D

The worst-case time complexity of Selection Sort is O(n²). This is because, in every pass of the algorithm, the smallest (if sort in ascending order) or largest (if sort in descending order) element is selected from the unsorted portion of the array by scanning all remaining elements. This requires (n−1) comparisons in the first pass, (n−2) in the second pass, and so on, until only one element is left.
The total number of comparisons becomes (n−1)+(n−2)+...+1=n(n−1)/2, which simplifies to O(n²).