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.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 484
- Exam Queries 434
- Tier 1 Placement Questions 17
- Job Queries 56
- Projects 8

36,075 questions

43,521 answers

123,666 comments

42,747 users