OA. free
Free
Qualcomm Embedded Systems & Hardware Embedded Systems & Hardware Medium

Which one of the sorting techniques given in the options is/are in-place comparison-based...

Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.

Which one of the sorting techniques given in the options is/are in-place comparison-based algorithms?

I) Selection sort
II) Insertion sort

Choose one option.
Show answer & explanation
Answer: D. Both (I) and (II)

Both selection sort and insertion sort are in-place comparison-based algorithms. Selection sort repeatedly finds the minimum element and swaps it into position, using only O(1) extra space. Insertion sort builds the sorted array by inserting each element into its correct position with comparisons, also using O(1) extra space. Both satisfy the in-place requirement (constant extra space) and rely on element comparisons for ordering.

Step-by-step Derivation:
Analysis of each algorithm:

I) Selection Sort:

  • Comparison-based: Uses comparisons to find minimum elements
  • In-place: Only uses a constant amount of extra memory (variables for indices and temp swaps)
  • Space complexity: O(1)
    ✓ Meets both criteria

II) Insertion Sort:

  • Comparison-based: Uses comparisons to find insertion positions
  • In-place: Only uses a constant amount of extra memory (variables for indices and shifts)
  • Space complexity: O(1)
    ✓ Meets both criteria

Conclusion: Both (I) and (II) are in-place comparison-based sorting algorithms.