The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 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

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

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

- 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,756 questions

46,768 answers

140,674 comments

58,557 users