Register

GO Classes DPP | GATE CS, DA | Algorithms | Implementation Choices

137 views
1 1 vote

Which of the following are important design choices rather than arbitrary choices?

  1. In binary search, compute the middle index using $\texttt{(lo + hi) >>> 1}$ instead of $\texttt{(lo + hi) / 2}$.
     
  2. When equal keys are encountered during merging, copy the element from the left subarray before the equal element from the right subarray.
     
  3. During $2$-way quicksort partitioning, stop both scans when they encounter keys equal to the pivot.
     
  4. In quicksort, always recursively process the left subarray before processing the right subarray.

1 Answer

1 1 vote
  1. Important
    Using the unsigned right-shift calculation protects the middle-index computation when $\texttt{lo + hi}$ exceeds the maximum positive signed integer value.
    Therefore, this choice helps avoid an overflow-related error.
     
  2. Important
    When equal elements are taken from the left subarray first, their original relative order is preserved.
    This property makes mergesort stable.
    Therefore, B is important.
     
  3. Important
    Suppose an array contains many elements equal to the pivot.
    If both scans skip all equal keys, partitioning can repeatedly produce poor subproblems and lead to quadratic behaviour.
    Stopping on equal keys distributes equal elements across the partition more safely.
    Therefore, C is important.
     
  4. Arbitrary
    Both recursive subarrays must eventually be sorted, but their processing order does not affect the final sorted result.
    Processing the right side first would also be correct.
    Therefore, D is not an important design requirement.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
1 1 answer
180
180 views
GO Classes asked Aug 5
180 views
GO Classes DPP | GATE CS, DA | Algorithms | Quicksort Partition
The standard $2$-way quicksort partition procedure uses the first element as the pivot and stops both scans when they encounter an element equal to the pivot.It is applie...
5 5 votes
1 1 answer
183
183 views
GO Classes asked Aug 5
183 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide and Conquer
Suppose $n$ elements are divided into groups of $r$ elements. The median of each group is found, and the median of these group medians is used as the selection pivot.For ...
4 4 votes
1 1 answer
130
130 views
GO Classes asked Aug 5
130 views
GO Classes DPP | GATE CS, DA | Algorithms | Randomized Quicksort
An array contains $n\geq 8$ distinct elements:$a_1<a_2<\cdots<a_n$The array is sorted using randomized quicksort.What is the probability that $a_7$ and $a_8$ are compared...
1 1 vote
1 1 answer
154
154 views
GO Classes asked Aug 5
154 views
GO Classes DPP | GATE CS, DA | Algorithms | Merge Comparison
Two sorted subarrays, each containing $n/2$ elements, are merged into one sorted array of length $n$.What is the possible range for the number of key comparisons made dur...