Project ForgeLet P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t₁ and t₂ be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
- At₁ = 5
- Bt₁ < t₂
- t₁ > t₂
- Dt₁ = t₂
Explanation
For the already-sorted input [1,2,3,4,5], choosing the first element as pivot is the worst case: it never splits the array, so comparisons = 4+3+2+1 = 10. For [4,1,5,3,2]: partitioning around pivot 4 takes 4 comparisons and yields [1,3,2 | 4 | 5], then the left part [1,3,2] partitions around 1 (2 comparisons, no smaller elements) giving [1 | 3,2], then [3,2] partitions around 3 (1 comparison); the right part (just [5]) needs none. Total t₂ = 4+2+1 = 7. Since t₁=10 and t₂=7, t₁ > t₂.
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.