retagged by
1,023 views
1 votes
1 votes

Quick sort is run on following inputs

I1: stricltly increasing order of n input sequece

I2: stricltly decreasing order of n input sequece

Let S1 and S2 be the number of swaps made by the input I1 and I2 respectively Then

 

A). S1<S2

B). S1>S2

C). S1=S2

D). Cannot predict anything for arbitrary n

retagged by

2 Answers

3 votes
3 votes

 NOTE: Assuming desired sort is ascending order, Choosing last element as pivot always. 

i am getting S1 > S2 , see how

PARTITION(A,p,r)
1 x = A[r]
2 i = p - 1
3 for j = p to r - 1

4            if A[j] <= x
5                     i = i +1
6                     exchange A[i] with A[ j ]
7 exchange A[i + 1] with A[r]
8 return i + 1

 

 

If I am Wrong please let me know.

1 votes
1 votes
Here the exact value of n has no role to play. Since for S1 we have a strictly increasing number series, it would only swap pivot with itself n number of times in the complete procedure.

Whereas for strictly decreasing number series, no matter what pivot is chosen it will always exceed n because it has to compulsorily swap the pivot and also the other elements at least once (because obviously the series won't turn in to an increasing series magically).

Hence option A is correct.

Related questions

1 votes
1 votes
1 answer
2