The GATE Grind

GATE 2014 CS (CS1) – Question 24

Algorithms · Searching, Sorting and Hashing · 1 mark · Multiple choice

Quicksort P sorts ascending using the first element as pivot. Let t₁ and t₂ count its comparisons on [1,2,3,4,5] and [4,1,5,3,2] respectively. Which holds?

  1. t₁ = 5
  2. t₁ < t₂
  3. t₁ > t₂
  4. t₁ = t₂

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) t₁ > t₂

Explanation

For sorted input [1,2,3,4,5], first-pivot quicksort repeatedly selects the minimum; the usual partition model uses 4+3+2+1=10 comparisons. For [4,1,5,3,2], the first pivot splits into [1,3,2] and [5]. The left side needs 2 comparisons and then 1, giving 4+2+1=7. Thus t₁ > t₂. **Answer: C.**