The Gateway to Computer Science Excellence
0 votes
267 views

Loading Question

in Algorithms by Boss (11.1k points) | 267 views
+2
All elements to left of pivot should be less than pivot and all elements to right should be greater.

Hence, (A) is correct.
0
but i think we must first apply the algorithm partition it and then we have to give pivot of second pass in answer. Am i right?
0
See the question is clear. Read it once again "it says we have finished first  partitioning".
0
Yes,Now i get it.

1 Answer

+2 votes

2,5,1,7,9,12,11,10  

this is our array after  1st  partitioning  in quick  sort.

before solving it you should know that---->

1) Quick sort is  an algorithm that uses  divide and conquer  approach.

2) in this we choose an element  as pivot , pivot in  general  is  a  point of  balance ,  so by referring  an  element  by  pivot in quick sort means  that  it  will be  at  his  place after  first pass or  after a partition.  (usually we take last element in array or list as  pivot)

3) after partition  the  element we have chosen as pivot  will  be at it's correct position  in such a way that elements to it's left will be smaller than it and elements to its right will be larger than it.

eg---->   let array be 5,4,1,2,3   let pivot be 3   then after first partition array would look like this

                 1,2,3,5,4   and you may see 3 reached at its correct position and elements left to it 1,2 are smaller   and elements                         right to it are larger.

now  in our   question

we are given array after  1st partition 

2,5,1,7,9,12,11,10   so   we know nothing about  its previous arrangement  so we dont know that  which no. was chosen as pivot

but   from  2) we know pivot will be at its correct place.    so  according to array  we can see that  7 & 9 are at their correct place 

 (   in sorted form----->1,2,5, 7 , 9 ,10,11,12     if we compare it with above sequence then we see  7& 9 are at correct place)

but this is not over  check  using   3)  that  left of pivot  is always small  and  right is pivot is always larger

so checking element 7 we see  left of it is smaller  and right of it is larger  so it  seems it can be pivot

now check  9  we see  left of it is smaller  and right of it is larger  so it also seems it can be pivot

but  it is not possible to take 2 elements as pivot at same time

so  either  7  can be pivot  or  9 can be pivot.

so correct answer is a) either 7 or 9 can be pivot

by Active (1.6k points)
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,704 users