The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+25 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$

+29 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.

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.

+14

Total number of comparisons made by **partition **algorithm for input array of size $n = n+1$

(See 2nd page here http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/quicksort.pdf)

[12345] 6

[1] [2345] 5

[2] [345] 4

[3] [45] 3

[4] [5]

Total = 6+5+4+3 = 18

[12345] 6

[123] [45] 4+3

[1] [23] [4][5] 3

[2] [3]

total = 6+4+3+3 = 14

Hence $t_1 \gt t_2$

+13 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.

+9 votes

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

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

+3 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

–3 votes

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,080 questions

45,572 answers

132,069 comments

49,047 users