quick sort partition procedure

Question

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?

Answer 1

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. 

Comments

@Arjun sir, please verify this. 

---

@Rude , your logic seems correct but In the question they have asked about after one pass and if we put above array in partition function then it will return 2 as pivot element .. right ??

---

Dear, read the question carefully, It says that after one pass array stand this. Now asking that how many element he could have chosen as pivot in the first step. Hence I have applied the logic.

---

ohh .. didn't see that ... thanks rude :)

---

I feel instead of "after one pass", it should be something like "after one of the passes"???

---

Nyc explaination rude. :)