Algorithm

Question

Answer 1

Basically what we need to know here is the position of pivot which is 60 in this case after applying the first pass of partition algorithm.A pass of partition algorithm is completed when the pivot chosen gets its proper place.Using iterative quicksort method (see the partition of algo of this : http://www.geeksforgeeks.org/iterative-quick-sort/) , we find after 1st pass , the array looks like :

55  15  7  12  35  60  80  90  95

So we can see all elements less than 60 are at its left side and all elements right to 60 are greater than it.In other words , 60 which is the pivot has got its correct place.This is the required effect of partition algo.

Now , according to the question , we need to find arrangements preserving this effect.So all elements left to 60 can be permuted and all right elements to 60 can be permuted but separately so that the position of 60 is not disturbed.

Hence , no of arrangements in left part = 5!= 120(since no of elements left of 60 = 5]

and no of arrangements in right part = 3!= 6

So total no of required no of ways by multiplication principle = 120 * 6 = 720

Hence , 720 should be the required no of ways

Comments

Except 60 which is pivot, if we take all the permutations of remaining elements (I.e 8 elements)  then also 60 will be at proper position right ? Then answer should be 8! .

---

@Xylene "after first pass" you have to find permutation after the first pass!

---

@saxena0612, If thats the case then the habib's answer is correct. Otherwise, we can have 8! permutations leaving 60 because we need 60 as a pivot. For all those 8! permutations, 60 will be the pivot and it will be in correct place or preserves the position of pivot after 1st pass of quick sort.

---

@Habibkhan if we fix 60 at first position, and do the permutation of the remaining 7 elements, then also after applying the first pass on all 7! permutations, we will get same position for 60, which is the effect of first pass ( as the job of first pass is to place 60 at its right position)

---

@charul but then we need to preserve the property that :

All elements left of 60 should be smaller and right of 60 should be greater than it..

This property will be violated if u permute all 7 elements..It is possible say the element '7' may come to the right of 60 and then the above property will be invalidated..

Thus elements left of 60 and right of 60 are permuted separately ; they cannot be permuted together..