The Gateway to Computer Science Excellence

Quick Sort [closed]

+3 votes
484 views

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
in Algorithms by Boss (21.3k points)
closed by | 484 views
0
Even i got in the same way Pc
0
Do you get 7 ?
+1
No i too got 6
0
same here got 6, but in my case 12 and 16 are not changed.
0
Even I am getting 6.

Elements after partitioning I got are:

12 11 13 14 15 18 16 17
0
it has to be 6..itself !

2 Answers

+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

by Active (2.3k points)
edited by
0
it is the case of central  element . I think so
+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

by Boss (25.5k points)
0
while performing the 1st pass should I swap 15 with last indexed element i.e. 14 ?
+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  .
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...
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
+1

yes @santhoshdevulapally 
i too got this order.
12,11,13,14,15,18,16,17.

0
+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
0
can u help me with the 1st method ? its algo ?
+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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,707 users