GATE CSE 2014 Set 1 | Question: 14

Question

Let $P$ be quicksort program to sort numbers in ascending order using the first element as the pivot. Let $t_1$ and $t_2$ 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?

• A. $t_1 = 5$
• B. $t_1 < t_2$
• C. $t_1>t_2$
• D. $t_1 = t_2$

Comments

so both the methods are correct right?

---

yup

---

12345 sequence requires total 10 comparisions

41532 sequence requires only 6 comparisions

Answer 1

it would be $t_1>t_2$, because the first case is the worst case of quicksort i.e. minimum number is chosen as pivot. Hence in the worst case the comparisons are high.

The splitting occurs as
$[1] [2345]$
$[2] [345]$
$[3] [45]$
$[4] [5]$

and

$[123] [45]$
$[1] [23] [4][5]$
$[2] [3]$

Number of recursive calls remain the same, but in second case the number of elements passed for the recursive call is less and hence the number of comparisons also less.

Correct Answer: $C$

Comments

Kushagra, your partitioning algo considers right element of the unsorted part/array as pivot. If you consider left element as pivot then working procedure might be different..so exact number of comparisons will depend on the implementation.. 

Quick sort using first element as pivot

---

@Verma Ashish

I think the algorithm shared by @Kushagra गुप्ता is from CLRS book. It uses the first element as pivot element. Even I think there are only (n-1) comparisons required at each partition.

Below is the screenshot of the slide from MIT-OCW. This is the lecture slide of Charles E. Leiserson(CLRS) himself :)

Reference: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-4-quicksort-randomized-algorithms/lec4.pdf

---

@SomeEarth

Can you tell how for 4 1 5 3 2 calculations comes out to be 16.??

Answer 2

Question is asking about number of comparisons. 

First case [1 2 3 4 5]

1 [2 3 4 5]    ->  4 comparisons
2 [3 4 5]  -> 3 comparisons
3 [4 5] -> 2 comparisons
4 [5] -> 1 comparison

Second case [4 1 5 3 2]
4 [1 3 2] [5] -> 4 comparisons
1 [3 2]  -> 2 comparisons
3 [2]  -> 1 comparison

Hence, in second case number of comparisons is less. => t1 > t2.

Comments

this seems intuitively correct to me though selected answer has different logic. I wonder which is correct. :(

---

Anshul_07

i m getting the same!

---

t1 --- > 10 comparisons and 4 swaps

t2 --- > 6 comparisons and 6 swaps

 

t1 > t2  ( comparisons )

Answer 3

We dont even need to compare the number of comparisions we know that Quick sort gives worst result

list is already sorted ascending or decending and when all element are equal it has time complexity of O($n^{2}$)  

in rest cases it is O($nlogn$)  hence t1>t2

Comments

For The given cases How Your logic works Please explain. Which will you select as pivot to get O(n^2) as the time complexity for above list

Answer 4

When first element or last element is chosen as pivot, Quick Sort's worst case occurs for the sorted arrays. In every step of quick sort, numbers are divided as per the following recurrence. T(n) = T(n-1) + O(n)

So, t1>t2