GATE CS 2014 Set 1 Q14 — Searching, Sorting, Hashing

For a quicksort implementation that uses the first element as the pivot:

Case 1: Input $[1, 2, 3, 4, 5]$
Since the input is already sorted, choosing the first element as the pivot results in the worst-case partitioning:
• Pivot $1$: compared with $2, 3, 4, 5$ ($4$ comparisons). Remaining: $[2, 3, 4, 5]$.
• Pivot $2$: compared with $3, 4, 5$ ($3$ comparisons). Remaining: $[3, 4, 5]$.
• Pivot $3$: compared with $4, 5$ ($2$ comparisons). Remaining: $[4, 5]$.
• Pivot $4$: compared with $5$ ($1$ comparison).
Total comparisons $t_1 = 4 + 3 + 2 + 1 = 10$.

Case 2: Input $[4, 1, 5, 3, 2]$
• Pivot $4$: compared with $1, 5, 3, 2$ ($4$ comparisons). Partitions into $[1, 3, 2]$ and $[5]$.
• For $[5]$: $0$ comparisons.
• For $[1, 3, 2]$: Pivot $1$ is compared with $3, 2$ ($2$ comparisons). Partitions into $[]$ and $[3, 2]$.
• For $[3, 2]$: Pivot $3$ is compared with $2$ ($1$ comparison).
Total comparisons $t_2 = 4 + 2 + 1 = 7$.

Since $t_1 = 10$ and $t_2 = 7$, we have $t_1 > t_2$.