Dark Mode

15,861 views

39 votes

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?

- $t_1 = 5$
- $t_1 < t_2$
- $t_1>t_2$
- $t_1 = t_2$

edited
Jan 19
by ASNR1010

Actually to be more specific I have to say two different partition procedure both are correct. In one way you have one fix variable and you are moving the other to get partition(your's). You can also get the same partition by using a two variables in which one pointing to last and another just subsequent of the pivot and checking by pivot until one crosses the other and that should be replaced with pivot to get the partition and here, I'm considering pivot to 1st element(in this method you get 16).

0

56 votes

Best answer

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$

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$

3

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. **L**eiserson(C**L**RS) himself :)

3

44 votes

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.

5

4 votes

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