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

0

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

+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

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.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,716 questions

46,751 answers

140,564 comments

58,409 users