Redirected
retagged by
4,023 views
1 votes
1 votes
Consider an array consisting of the following elements in unsorted order (placed randomly) but 60 as pivot element

60 80  15 95 7  12 35 90 55

Quicksort partition algorithm is applied by choosing first element as pivot element . How many total number of arrangement of array integers is possible preserving the effect of first pass of partition algorithm
retagged by

3 Answers

6 votes
6 votes

Answer : $5! \times 3! = 720$ 

What is the Effect of the Partition Algorithm when Pivot is $P$ : After the Partition algorithm, $P$ will go to its correct position and All the elements less than or equal to $P$ will go to one side and all the elements greater than $P$ will go to the other side.

Quicksort partition algorithm is applied by choosing first element as pivot element. So, After the First Pass of Partition algorithm (i.e. One time Partition Algorithm), Our Array will look like the following :

$\left \{ 15,7,12,35,55 \right \} \,\,60\,\,\left \{ 80,95,90 \right \}$  

i.e. After the Partition algorithm, $60$ will go to its correct place and all the numbers less than or equal to $60$ will go to the one side and all the numbers greater than $60$ will go to the other side.

So, Now, total number of arrangements of array integers  possible preserving the effect of first pass of partition algorithm will be : $5! \times 3!$ as All the five elements that are less then $60$ can arrange in any order and all the three elements that are greater than $60$ can arrange in any order ---- and the effect of partition algorithm will still preserve.

1 votes
1 votes
First Pass places the pivot element at the correct position. So after first pass array looks like

[50, 35, 33, 60, 100, 72, 85].

60 is going to be intact at its place.

We can arrange 50, 35, 33 in 3! ways without hurting the information of the first pass, which is all elements before pivot is smaller, similarly for [100, 72, 85].

Thus total ways are 3!*3! = 36.

Related questions

2 votes
2 votes
5 answers
1
Shubham Sharma 2 asked Feb 7, 2017
2,011 views
Reply with solution @ Habibkhan,@Gabbar,@Arjun Sir
3 votes
3 votes
2 answers
2
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
1 answer
3
dhruba asked Jun 5, 2023
411 views
Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?a. 1/n...
0 votes
0 votes
2 answers
4
Ajink123 asked May 10, 2023
528 views
Sort the following array using quicksort algorithm. [40,11,4,72,17,2,49]