+1 vote
208 views

Reply with solution @ Habibkhan,@Gabbar,@Arjun Sir

asked | 208 views

## 2 Answers

+3 votes
Best answer

Here the key thing is :

preserving the first pass of partition algorithm

So we need to find the position of pivot which is taken as 60 here..And 60 will get its correct place and divide the entire array into 2 parts : a) left subarray will contain values < 60  b) other part contains values > 60.

So we need not apply the partition algo to find the position of 60..Just find what would be its position in the sorted array because that will be the correct position..

Hence we write the sorted array as :  7   12    15    35     55    60    80   90   95                                                                                                                               ---------------------------------           ------------------

So as shown above we will have 5 elements to left of 60 and 3 elements to right of 60..

Hence  number of required permutations   =    no of permutations of left part * right part

=    5 !   *    3 !

=   120  *    6

=   7200

Hence 7200 is the correct answer..

answered by Veteran (99.2k points)
selected
0
@Habibkhan can you give pseudocode when first element is chosen as pivot?? Bcoz many implementations are there. Need a standard one.
0
Does this question has other correct answers???
+1
I follow the iterative version of quicksort partitioning which says :

x = a[p]

i = p

for j in (p+1,n)

{

if (x  >= a[j])

{

i++ ;

swap(a[i],a[j]) ;

}

}

swap(a[p] , a[i]) ;   // To finally find the place of 60 here we need to do this
0
Thanks @Habibkhan I think we can also use this code when we want to select pivot as last element correct?? @Shubham answer by @habibkhan is correct.
0
i got it
+1
120 *6 =720 and not 7200

So the answer is 720

Right??
+1 vote

Basically what quick sort does is...

It places the pivot element in its right position ie all elements left to it are smaller and those on the right r larger than the pivot

But this logic there are 5 elements smaller than pivot and 3 elements greater thus leading to 5 factorial combinations on left and 3 factorial combination on the right

5! * 3!  =720 possible combinations



answered by Junior (535 points)

0 votes
0 answers
1
0 votes
1 answer
2
0 votes
1 answer
3