The Gateway to Computer Science Excellence

+3 votes

Consider an array with the following elements: 12, 18, 17, 11, 13, 15, 16 and 14.

How many element will change their initial position after completion of partition algorithm by choosing 15 as pivot?

**Given Answer** : **7** ( only 16 is not swapped )

**My Answer : 6** ( 16 and 11 are not swapped )

My approach

12, 18, 17, 11, 13, 15, 16 and 14. **15 is pivot swap it with leftmost element**

15 | 18, 17, 11, 13, 12, 16 , 14 **18>15 & 14 <15**

15 | 14, 17, 11, 13, 12, 16 , 18 **17>15 & 12<15**

15 | 14, 12, 11, 13, 17, 16 , 18 **i and j meet each other at 13 so swap with pivot value**

13 14 12 11 15 17 16 18

So 11 and 16 are not changed all other elements have changed their position

**Correct me if i am wrong **

closed as a duplicate of:
Sorting

+1 vote

12, 18, 17, 11, 13, 15, 16, 14. **15 is pivot swap it with right most element**

12, 18, 17, 11, 13, **14**, 16, | **15**

12, **11**, 17, **18**, 13, 14, 16, | 15

12, 11, **13**, 18, **17**, 14, 16, | 15

12, 11, 13, **14**, 17, **18**, 16, | 15

12, 11, 13, 14, **15**, 18, 16, | **17**

12, 11, 13, 14, 15, 18, 16, 17

clearly 12 and 16 are not changed.

if we use pivot as leftmost element then 16 doesn't change

12, 18, 17, 11, 13, 15, 16, 14. **15 is pivot swap it with left most element**

**15 |** 18, 17, 11, 13, **12**, 16, 14

15** |** **11**, 17, **18**, 13, 12, 16, 14

15** |** 11, **13**, 18, **17**, 12, 16, 14

15** |** 11, 13, **12**, 17, **18**, 16, 14

15** |** 11, 13, 12, **14**, 18, 16, **17**

**14**** |** 11, 13, 12, **15**, 18, 16, 17

in this case answer is seven

+1 vote

**METHOD 1 : Pivot Choosing as Middle Element**

**step1:** Elements greater than 15 move to right hand side of 15 in same order.

**step2:** Elements which are less than 15 put in same order when they are LHS of 15 else move them to ahead of 15 in same order.

**step3:** Fix the position of 15.

After doing this arrangements of array elements are:

**12 11 13 14 15 18 17 16 **

Ans=7

**METHOD 2 : Pivot Position is choosen as Right Most Element**

12, 18, 17, 11, 13, 15, 16, 14. 15 is pivot swap it with right most element

12, 18, 17, 11, 13, 14, 16, | 15

12, 11, 17, 18, 13, 14, 16, | 15

12, 11, 13, 18, 17, 14, 16, | 15

12, 11, 13, 14, 17, 18, 16, | 15

12, 11, 13, 14, 15, 18, 16, | 17

12, 11, 13, 14, 15, 18, 16, 17

clearly 12 and 16 are not changed.

Ans= 6

**METHOD 3 : Pivot Position is choosen as Left Most Element**

if we use pivot as leftmost element then 16 doesn't change

12, 18, 17, 11, 13, 15, 16, 14. 15 is pivot swap it with left most element

15 | 18, 17, 11, 13, 12, 16, 14

15 | 11, 17, 18, 13, 12, 16, 14

15 | 11, 13, 18, 17, 12, 16, 14

15 | 11, 13, 12, 17, 18, 16, 14

15 | 11, 13, 12, 14, 18, 16, 17

14 | 11, 13, 12, 15, 18, 16, 17

Ans = 7

Clearly this is Ambiguous Question . We need to know the position of Pivot Element . Made Easy has asked the same in Last Year Test Series as well

+1

actually when the pivot is not taken at last indexed . it causes a problem for me.

can u help me a bit more? so that I could understand it clear .

can u help me a bit more? so that I could understand it clear .

0

@Gabbar ,how to do if pivot is not last element

if we swap pivot and last element and perform partition algorithm

the order of elements are 12,11,13,14,**15**,18,16,17.

0

this is method used when pivot is choosing as middle element....there so many versions of Quick sort available ... This is one of it.

for pivot choosing first or last element for it diffent algo availble... for them also shortcut available...

for pivot choosing first or last element for it diffent algo availble... for them also shortcut available...

0

for some version algo different partitions possible?

then which one follow in the exam.in the above question u got one partition and i got one ,which would we consider in the exam

then which one follow in the exam.in the above question u got one partition and i got one ,which would we consider in the exam

+1

@santhosh

This Question is ambiguous !

They should mention position of Position of Pivot also. Here we will get two different answers . Hopefully GATE questions will not be this much ambiguous

This Question is ambiguous !

They should mention position of Position of Pivot also. Here we will get two different answers . Hopefully GATE questions will not be this much ambiguous

+1

**This is question very good **

**passes are like this**

**12 **11** 17 **18** 13 15 16 14 >>> 11 and 18 changes it's initial position**

**12 11 13 18 17 15 16 14 >>>13 and 17 ****changes it's initial position**

**12 11 13 14 17 15 16 18 >>>here 14 and 18 will swap but only 14 will change initial position**

**12 11 13 14 15 17 16 18>>>>here 15 and17 will swap but 15 ****will change initial position**

according to me answer is **6**

52,315 questions

60,427 answers

201,757 comments

95,237 users