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
Show answer & explanation
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.