The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
142 views

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

asked in Algorithms by Boss (5.5k points) | 142 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 (97.3k points)
selected by
@Habibkhan can you give pseudocode when first element is chosen as pivot?? Bcoz many implementations are there. Need a standard one.
Does this question has other correct answers???
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
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.
i got it
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 (477 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,961 questions
37,632 answers
96,400 comments
35,286 users