Skip to content
GATEiit

GATE CSE 2021 Set 1 Q19: Fewest comparisons to sort an already sorted array

Question

Consider the following array.

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

2332456972738997

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2021 final answer key)

Concept used: On sorted input insertion sort hits its best case of n−1n - 1 comparisons; quicksort with the last pivot hits its worst case.

First step: Note the array is already sorted, then count the comparisons each algorithm makes on sorted input.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2021 Set 1 questions →