GATE Overflow Test Series | Algorithms | Test 1 | Question: 10

Question

Which of the following is/are the possible array contents after second pass of Quick Sort for the following initial ordering assuming first element is taken as pivot?$$34, 8, 64, 51, 32, 21$$

• A. $8, 21, 32, 34, 51, 64$
• B. $8, 32, 34, 51, 64, 21$
• C. $8, 34, 51, 64, 32, 21$
• D. $8, 34, 64, 51, 32, 21$

Comments

sir can you please show it stepwise

Answer 1

In first pass $34$ is the pivot. So, it'll get position as in the final sorted order which is $4^{th}$ position. This is true only for option A.

Comments

can you show the stepes after 2 nd pass

---

Can anyone please show all the steps till the end

---

Since 34 is the pivot element, all the elements to the left must be less than 34, and all the elements to the right of it must be greater than 34.

Here this condition is satisfied by option A only.
So Option A is the correct option.

For more you can refer to this video

---

@gatecse Can you please show it stepwise and clear the confusion whether full procedure of quicksort was required to be implemented or only till second pass as asked……..??

Answer 2

So basically in first pass (or swap) 21 and 64 get swapped and in 2nd Swap when the Right Bound crosses Left Bound, 34 gets placed before 51. Giving us 8,21,32,34,51,64