• retagged by
2,473 views
1 1 vote
Is below question and its answer correct? Or its just kind of rubbish?

After one  pass through the partition procedure of quick sort array stand as below:

2,1,4,5,9,7,8,10

How many possible pivots can you find in the array?

(A) 1         (B) 2        (C) 3        (D) None of these

The answer given is (C). I don't understand whats the logic behind the question as I don't understand what it is meant by "finding pivots by looking at the array". I understand that if partition procedure is once run, one element is at its final position. So if that it is the question shouldn't be the answer (A)? Am I wrong?

1 Answer

Best answer
6 6 votes

This is a perfectly logical question. 

To Answer this question you have to understand the what partition do?

In Quick Sort, in each iteration we select an element (which is called as pivot), and we traverse the complete array and put all the element which are smaller than pivot in left side of array and all the element which is larger than or equal to pivot (If they array have duplicate data), put that in right side or array. Hence in each iteration we are trying to fix the location of a element in sorted array. 

Now the given sequence is

2, 1, 4, 5, 9, 7, 8, 10

An element can be a pivot if all the value in its left is less than that value and all the value in its right is greater or equal to that value. 

10 ==> Pivot ==> All the value in left is less than 10.

8 ==> Not Pivot ==> 9 is in the left side and greater than 8

7 ==> Not Pivot ==> 9 is in the left side and greater than 7

9 ==> Not Pivot ==> 7 and 8 are in the right side and less than the 9

5 ==> Pivot ==> all the value in its left is less than and all the value in its right is greater than 5

4 ==> Pivot ==> all the value in its left is less than and all the value in its right is greater than 4

Similarly you see that 1(Not Pivot) and 2(Not pivot). 

Hence total number of Pivot possible is 3, Hence the answer. 

• selected by
Position:
Show:

Related questions

1 1 vote
1 answers 1 answer
896
896 views
Rohan Mundhey asked Nov 9, 2016
896 views
Consider the following sequence of letters (Assume always select last element as pivot and array index starts with 0)Q, U, I, C, K, S, O, R, T, E, X, A, M, P, L, EWhat is...
2 2 votes
8 answers 8 answers
5.7k
5.7k views
3 3 votes
1 1 answer
244
244 views
GO Classes asked Aug 31
244 views
During sorting, one complete processing of all elements whose final positions have not yet been determined is called a pass.Which of the following sequences cannot be the...
0 0 votes
1 1 answer
148
148 views
GO Classes asked Aug 10
148 views
Consider the Quick sort algorithm which sorts elements in ascending order using the first element as pivot. Then which of the following input sequence will require a maxi...