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

@Ray Tomlinson [41532] array it will be 7 comparisons not 6

---

swapping happens based on the parition algorithm so first paritiion we are getting same no of comp after first parition element order are changed according to the own paritiion algo so infact first element comes which element also depends on the paritiion algo

so from the information when element is sorted algo it tooks n^2 time and not sorted or reversed then its took some less amount of time we can solve this question

---

similar question 

 https://gateoverflow.in/80366/gate-cse-1987-question-1-xviii

https://gateoverflow.in/2744/gate-cse-1996-question-2-15

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

@SomeEarth

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

---

Number of recursive calls will not be the same.

In 1st case there will n level and in 2nd case logn asymptomatically

---

see worst case happens when all elements are sorted in quick sort so 1st one is sorted so its time is high but second one is unsorted so compared to t1,t2 is fastly do so t1>t2 which is option c

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

Answer 5

Hoare partition (Given : pivot = first element. Generally we can take any elememt as pivot)

Counting rules  :

1. Count every pivot-vs-element comparison inside scans (including pivot with itself). 
2. Do not count "Stopping test $i \ge j$ comparisons".

Notation  
Blue box = pointer $i$  
Red box = pointer $j$  
Nested box = $i=j$

Algorithm (one partition on $A[L..R]$)

pivot $= A[L]$, $i=L$, $j=R$  

repeat  
i-scan: while $A[i]<$ pivot do $i\leftarrow i+1$  
j-scan: while $A[j]>$ pivot do $j\leftarrow j-1$  
if $i<j$ then swap $A[i],A[j]$, $i\leftarrow i+1$, $j\leftarrow j-1$  
else stop

Case 2: Input $[4,1,5,3,2]$

Partition on $[4,1,5,3,2]$, pivot $=4$

Start
\[
\begin{array}{ccccc}
\color{blue}{\boxed{4}} & 1 & 5 & 3 & \color{red}{\boxed{2}}
\end{array}
\]

Step 1: i-scan  
$4<4$ (false)

Comparisons = 1
\[
\begin{array}{ccccc}
\color{blue}{\boxed{4}} & 1 & 5 & 3 & \color{red}{\boxed{2}}
\end{array}
\]

Step 2: j-scan  
$2>4$ (false)

Comparisons = 1
\[
\begin{array}{ccccc}
\color{blue}{\boxed{4}} & 1 & 5 & 3 & \color{red}{\boxed{2}}
\end{array}
\]

Swap 1: swap 4 and 2
\[
\begin{array}{ccccc}
\color{blue}{\boxed{2}} & 1 & 5 & 3 & \color{red}{\boxed{4}}
\end{array}
\]

Update pointers: $i\leftarrow i+1,\ j\leftarrow j-1$
\[
\begin{array}{ccccc}
2 & \color{blue}{\boxed{1}} & 5 & \color{red}{\boxed{3}} & 4
\end{array}
\]

Step 3: i-scan  
$1<4$ (true), $5<4$ (false)

Comparisons = 2
\[
\begin{array}{ccccc}
2 & 1 & \color{blue}{\boxed{5}} & \color{red}{\boxed{3}} & 4
\end{array}
\]

Step 4: j-scan  
$3>4$ (false)

Comparisons = 1
\[
\begin{array}{ccccc}
2 & 1 & \color{blue}{\boxed{5}} & \color{red}{\boxed{3}} & 4
\end{array}
\]

Swap 2: swap 5 and 3
\[
\begin{array}{ccccc}
2 & 1 & \color{blue}{\boxed{3}} & \color{red}{\boxed{5}} & 4
\end{array}
\]

Update pointers: $i\leftarrow i+1,\ j\leftarrow j-1$
\[
\begin{array}{ccccc}
2 & 1 & \color{red}{\boxed{3}} & \color{blue}{\boxed{5}} & 4
\end{array}
\]

Partition-1 totals  
Comparisons $=1+1+2+1=5$  
Swaps $=2$

Subarrays: $[2,1,3]$ and $[5,4]$

Partition on $[2,1,3]$, pivot $=2$

Start
\[
\begin{array}{ccc}
\color{blue}{\boxed{2}} & 1 & \color{red}{\boxed{3}}
\end{array}
\]

Step 1: i-scan  
$2<2$ (false)

Comparisons = 1
\[
\begin{array}{ccc}
\color{blue}{\boxed{2}} & 1 & \color{red}{\boxed{3}}
\end{array}
\]

Step 2: j-scan  
$3>2$ (true), $1>2$ (false)

Comparisons = 2
\[
\begin{array}{ccc}
\color{blue}{\boxed{2}} & \color{red}{\boxed{1}} & 3
\end{array}
\]

Swap: swap 2 and 1
\[
\begin{array}{ccc}
\color{blue}{\boxed{1}} & \color{red}{\boxed{2}} & 3
\end{array}
\]

Update pointers
\[
\begin{array}{ccc}
\color{red}{\boxed{1}} & \color{blue}{\boxed{2}} & 3
\end{array}
\]

 

Partition-2 totals  
Comparisons $=1+2=3$  
Swaps $=1$

Remaining subarray $[2,3]$

Partition on $[2,3]$, pivot $=2$

Start
\[
\begin{array}{cc}
\color{blue}{\boxed{2}} & \color{red}{\boxed{3}}
\end{array}
\]

Step 1: i-scan  
$2<2$ (false)

Comparisons = 1
\[
\begin{array}{cc}
\color{blue}{\boxed{2}} & \color{red}{\boxed{3}}
\end{array}
\]

Step 2: j-scan  
$3>2$ (true), $2>2$ (false)

Comparisons = 2

$i=j$ (double box)
\[
\begin{array}{cc}
\color{blue}{\boxed{\color{red}{\boxed{2}}}} & 3
\end{array}
\]

Partition-3 totals  
Comparisons $=1+2=3$  
Swaps $=0$

Partition on $[5,4]$, pivot $=5$

Start
\[
\begin{array}{cc}
\color{blue}{\boxed{5}} & \color{red}{\boxed{4}}
\end{array}
\]

Step 1: i-scan  
$5<5$ (false)

Comparisons = 1

Step 2: j-scan  
$4>5$ (false)

Comparisons = 1

Swap: swap 5 and 4
\[
\begin{array}{cc}
\color{blue}{\boxed{4}} & \color{red}{\boxed{5}}
\end{array}
\]

Partition-4 totals  
Comparisons $=2$  
Swaps $=1$

Case 2 total comparisons
\[
t_2 = 5+3+3+2 = 13
\]

Comments

Please check out my other answer on "Lomuto Partition" - Here

 

Answer 6

We don’t need to do any calculations here. A sorted list is known to produce the worst case time complexity for quicksort, which is O(n²). Since the first list is already in ascending order (sorted), its running time becomes O(n²).

The second list is unsorted, so quicksort runs in its average case of O(n log n).

Therefore, t1 > t2, and option C is correct.