The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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..**

@Habibkhan can you give pseudocode when first element is chosen as pivot?? Bcoz many implementations are there. Need a standard one.

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

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

+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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 397
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,707 questions

40,253 answers

114,361 comments

38,874 users