retagged by
2,012 views
2 votes
2 votes

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

retagged by

5 Answers

Best answer
3 votes
3 votes

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

                                                             =   720

Hence 720 is the correct answer..

edited by
2 votes
2 votes
After 1st pass all element less than 60 goes left to 60 and greater goes right to 60 .

left to 60 are 15,7,12,35,55 we arrange these in 5! ways

right of 60 are 80,95,90 arrange these in 3! ways .

total ways 5! * 3! = 120 * 6= 720 .

since 60 has fixed location after 1st pass.
1 votes
1 votes

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 

 
 
Answer:

Related questions

3 votes
3 votes
2 answers
1
dhruba asked Jun 5, 2023
985 views
In QuickSort algorithm, which of the following statements is NOT true regarding the partition process?a) Partition always divides the array into two non-empty subsets.b) ...
0 votes
0 votes
2 answers
2
Ajink123 asked May 10, 2023
528 views
Sort the following array using quicksort algorithm. [40,11,4,72,17,2,49]
0 votes
0 votes
2 answers
4