Sorting – GATE CSE AlgorithmsPractice Questions & PYQs

Derivation

To solve for $k$, we can test the growth rate of the options typically provided for this question:

• If $k = \Theta(\log n)$:
  $T(k) = (\log n) \cdot \log(\log n)$, which is greater than $\log n$.
• If $k = \Theta\left(\frac{\log n}{\log \log n}\right)$:
  Substitute $k$ into the complexity formula:
  $T(k) = \left( \frac{\log n}{\log \log n} \right) \cdot \log \left( \frac{\log n}{\log \log n} \right)$
  $T(k) = \left( \frac{\log n}{\log \log n} \right) \cdot [ \log (\log n) - \log (\log \log n) ]$
  As $n \to \infty$, the term $\log(\log \log n)$ becomes negligible compared to $\log(\log n)$:
  $T(k) \approx \left( \frac{\log n}{\log \log n} \right) \cdot \log (\log n)$
  $T(k) \approx \log n$

Conclusion

The number of elements that can be sorted is $\Theta\left(\frac{\log n}{\log \log n}\right)$.

For the best-case scenario, Insertion sort achieves a time complexity of $O(n)$ when the array is already sorted, which is more efficient than Quick sort's best-case complexity of $O(n \log n)$. In the average-case scenario, Quick sort maintains an efficient average complexity of $O(n \log n)$, whereas Insertion sort performs at $O(n^2)$. Consequently, Insertion sort is the optimal choice for the best case, and Quick sort is the optimal choice for the average case. Matching these findings to the provided options confirms that the correct sequence is (Insertion sort, Quick sort).

To determine the worst-case running time of merge sort for $n$ strings, each of length $n$, we need to consider both the number of comparisons and the time taken for each comparison.

1. Merge Sort Complexity: A standard merge sort algorithm performs $O(N \log N)$ comparisons, where $N$ is the number of elements being sorted. In this case, $N = n$ strings.
2. String Comparison Complexity: Comparing two strings, each of length $n$, in the worst case, takes $O(n)$ time (as we might need to compare all characters).
3. Total Time Complexity: Multiplying the number of comparisons by the cost of each comparison gives the total worst-case running time.
   Total time = (Number of comparisons) $\times$ (Time per comparison)
   Total time = $O(n \log n) \times O(n)$
   Total time = $O(n^2 \log n)$

Therefore, the worst-case running time for sorting $n$ strings of length $n$ using merge sort is $O(n^2 \log n)$.

Merge Sort operates by recursively splitting an unsorted array of size $n$ into two halves of size $n/2$ until each subarray consists of a single element. This process follows the Divide and Conquer paradigm, which consists of three distinct phases: dividing the problem into smaller independent subproblems, conquering them by recursively sorting the subarrays, and combining (merging) the results into a single sorted array. Because it breaks the problem into independent, non-overlapping subproblems, it fits the definition of Divide and Conquer rather than Dynamic Programming, Greedy, or Backtracking.

Selection sort works by identifying the minimum element in the remaining unsorted array and performing a single swap per iteration to place it in the correct position. This results in at most $n-1$ swaps, yielding a worst-case complexity of $O(n)$. In contrast, Quick sort and Heap sort require $O(n \log n)$ swaps on average to reorganize partitions or maintain the heap structure. While Insertion sort primarily utilizes element shifts, it performs significantly more operations than Selection sort when restricted to swaps. Therefore, Selection sort minimizes the absolute number of swaps among these in-place sorting algorithms.

Selection sort proceeds in $n-1$ passes.

1. In each pass, it finds the minimum element from the unsorted portion of the array.
2. It then performs exactly one swap to place this minimum element at the beginning of the unsorted portion.
3. This process repeats for $n-1$ passes, ensuring the correct element is placed in its sorted position in each pass.

Thus, for $n$ elements, selection sort performs exactly $n-1$ swaps.
In asymptotic notation, $n-1$ is $\theta(n)$.

The number of swaps is $n-1$.
$\text{Total Swaps} = n-1$
In Big-Theta notation, this is $\theta(n)$.

The quick sort algorithm's time complexity depends on the pivot selection strategy.

1. Pivot Selection: The problem states that the $(n/4)$-th smallest element is selected as the pivot using an $O(n)$ time algorithm.
2. Partitioning: Choosing the $(n/4)$-th smallest element guarantees that the array is partitioned into two sub-arrays: one with approximately $n/4 - 1$ elements (smaller than the pivot) and another with approximately $n - n/4 = 3n/4$ elements (larger than the pivot). The partitioning step itself takes $O(n)$ time.
3. Recurrence Relation: The worst-case recurrence relation for this specific pivot strategy is given by:
   $T(n) = T(n/4) + T(3n/4) + O(n)$
4. Solving the Recurrence: This recurrence relation can be solved using a recursion tree or by recognizing it as a standard form. Each level of the recursion tree sums to $O(n)$ work. The depth of the tree is logarithmic, determined by the longest branch (i.e., $3n/4$), which is $\log_{4/3} n$.
   Therefore, the total time complexity is $O(n \log n)$.
5. Worst Case: Since this pivot selection guarantees a split of at least $n/4$ and $3n/4$, it prevents the highly unbalanced partitions (e.g., $1$ and $n-1$) that lead to an $O(n^2)$ worst case in standard Quicksort implementations with naive pivot choices. Thus, for this specific pivot strategy, $O(n \log n)$ is indeed the worst-case time complexity.

The time complexity of Radix Sort is $\Theta(d \cdot (n + b))$, where $n$ is the number of integers, $d$ is the number of digits, and $b$ is the base.
Given the range $(n^{k/2}, n^k)$, the maximum value $U$ is $n^k$.
The number of digits $d$ required to represent numbers up to $U$ in a fixed base $b$ is $d = \log_b(U) = \log_b(n^k) = k \log_b n$.
Since $k$ and $b$ are constants independent of $n$, the number of digits is $d = \Theta(\log n)$.
Substituting this into the complexity formula yields $\Theta(\log n \cdot (n + b)) = \Theta(n \log n)$.

Selection sort performs a fixed number of comparisons regardless of the input array's initial order. For an array of size $n$, the total number of comparisons is determined by the sum $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$. For an array of length $n=5$, the calculation is $\frac{5(5-1)}{2} = \frac{5 \times 4}{2} = 10$. Specifically, the algorithm performs 4 comparisons in the first pass, 3 in the second, 2 in the third, and 1 in the final pass, totaling $4 + 3 + 2 + 1 = 10$ comparisons.

Quicksort sorts an array of size $n$ by partitioning it into two sub-lists and then recursively sorting them, which requires $n$ comparisons.
Given that the pivot selection rule ensures each sub-list contains at least $1/5$ of the elements, the sizes of the sub-lists are bounded.
The most unbalanced split allowed under this constraint results in one sub-list of size $n/5$ and the other of size $4n/5$.
Therefore, the recurrence relation for the number of comparisons $T(n)$ is the sum of the comparisons for the two sub-problems plus the $n$ comparisons for partitioning.
This yields $T(n) \leq T(n/5) + T(4n/5) + n$.

The worst-case time complexities for the given sorting algorithms are:

• Merge Sort: $O(n \log n)$
• Bubble Sort: $O(n^2)$
• Quick Sort: $O(n^2)$ (occurs with already sorted or nearly sorted input for naive pivot selection)
• Selection Sort: $O(n^2)$

Comparing these complexities, $O(n \log n)$ is asymptotically lower than $O(n^2)$. Therefore, Merge Sort has the lowest worst-case complexity among the options.

Selection Sort operates by repeatedly finding the minimum element from the unsorted portion of an array. At each iteration $i$, the algorithm makes a locally optimal decision by selecting the smallest element from the remaining unsorted subarray $A[i \dots n-1]$ and swapping it into the $i$-th position. Since the algorithm constructs the final sorted solution through a sequence of these locally optimal greedy choices without ever reconsidering previous steps, it adheres to the greedy method paradigm. This approach differs from divide-and-conquer, which recursively splits problems, and dynamic programming, which relies on solving overlapping sub-problems.

Merge sort utilizes a divide-and-conquer approach, defined by the recurrence relation $T(n) = 2T(n/2) + O(n)$.
The recursive tree has a depth of $\log_2 n$, and at each level, the algorithm performs $O(n)$ operations to merge the sub-arrays.
Applying the Master Theorem, the total time complexity for any input distribution is $O(n \log_2 n)$.
Because the splitting and merging logic is independent of the initial element order, the average case and worst case complexities are identical.
Therefore, both are $O(n \log_2 n)$.

Selection sort works by finding the minimum element in the unsorted portion and swapping it into its correct position, requiring at most $N-1$ swaps for an array of size $N$. In contrast, Insertion sort involves $O(N^2)$ data movements (shifts) to maintain order during the insertion process. Furthermore, both Quick-sort and Heap sort require $O(N \log N)$ swaps on average to partition the array or maintain the heap structure, respectively. Therefore, Selection sort is the algorithm that guarantees the minimum number of swaps.

When the median is selected as the pivot using an $O(n)$ algorithm, the array is guaranteed to be partitioned into two sub-problems of size approximately $\frac{n}{2}$. This leads to the following recurrence relation for the time complexity:
$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$
Here, $\Theta(n)$ accounts for both finding the median and partitioning the array. Applying the Master Theorem where $a=2$, $b=2$, and $f(n) = n$, we observe that $n^{\log_b a} = n^1 = n$. Since $f(n) = \Theta(n^{\log_b a})$, the recurrence resolves to $\Theta(n \log n)$. Thus, this pivot selection strategy ensures optimal Quick Sort performance.

A comparison-based sorting algorithm forms a binary decision tree where each of the $n!$ possible permutations of the input must be a reachable leaf.
For a binary tree of height $h$, which represents the worst-case number of comparisons, the number of leaves is at most $2^h$.
This leads to the inequality $2^h \geq n!$.
Taking the base-2 logarithm of both sides yields $h \geq \log_2(n!)$.
Applying Stirling's approximation, $\log_2(n!) \approx n \log_2 n - n \log_2 e$, which implies $h = \Omega(n \log n)$.

The time complexity of the Insertion Sort algorithm is given by $O(n + I)$, where $n$ is the number of elements and $I$ is the number of inversions in the input permutation. Given the restriction that the input permutations have at most $n$ inversions, we have $I \le n$. Substituting this into the complexity expression, we get $T(n) = O(n + n) = O(n)$. Since $I$ can be as large as $n$, the worst-case complexity for this restricted input set is $\Theta(n)$.

Insertion sort consists of two primary operations per element: searching for the correct insertion position and shifting existing elements to make space. While binary search reduces the time complexity of finding the insertion position from $\Theta(i)$ to $\Theta(\log i)$, it does not change the time complexity of the shifting process. In the worst case, shifting elements $A[j \dots i-1]$ to $A[j+1 \dots i]$ in a contiguous array still requires $\Theta(i)$ operations. Thus, the total worst-case time complexity is governed by $\sum_{i=1}^{n-1} (\Theta(\log i) + \Theta(i))$, which simplifies to $\sum_{i=1}^{n-1} \Theta(i) = \Theta(n^2)$. Consequently, the overall asymptotic worst-case running time remains $\Theta(n^2)$.

Quicksort's worst-case time complexity occurs when the pivot consistently results in highly unbalanced partitions, dividing the array into sizes of $0$ and $n-1$. Even with randomized pivot selection, there remains a non-zero probability that the random choice consistently picks the extreme elements at every step. In this worst-case scenario, the recurrence relation is $T(n) = T(n-1) + \Theta(n)$. Solving this recurrence yields $T(n) = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, which simplifies to $\Theta(n^2)$. Therefore, the worst-case complexity remains $O(n^2)$.

A sorting algorithm is classified as stable if, for any input array containing elements with equivalent keys, the relative order of these equal elements remains unchanged in the output. Formally, if two elements $A[i]$ and $A[j]$ have equal values with original indices $i < j$, the algorithm guarantees their sorted indices $i'$ and $j'$ satisfy $i' < j'$. This property ensures that the relative ordering of non-distinct elements is preserved, which is essential when sorting objects by multiple criteria. Other options like time complexity ($O(n \log n)$), algorithmic design (divide and conquer), or space complexity ($O(n)$) are independent of this specific definition. Therefore, stability is strictly defined by the maintenance of relative order for identical keys.