Question

Compute the first 4 pivots using quick sort algorithm on an array A=<10,15,17,18,6,120,30,250,95>. Write the content of the array A after each pivot is chosen.

Answer 1

In case of any queries, please revert back. I will solve them ASAP.

A={10,15,17,18,6,120,30,250,95}

Lets say we always choose the last element as the pivot.

What are the steps?

1. Choose Pivot

2. All elements smaller than pivot are left to pivot.

3. All elements larger than the pivot are right to pivot.

4. Repeat for left and right half

Order of elements does not change.

============== 1ST PIVOT =================

Pivot Chosen is 95 ie last element.

A = {10,15,17,18,6,30,95,120,250}

This is the array after the first pivot.

============== 2ND PIVOT =================

Pivot Chosen is 30 ie last element of left part!

A = {10,15,17,18,6,30,95,120,250}

This is the array after the second pivot. 30 was at the correct position.

=============== 3RD PIVOT ===================

Pivot Chosen is 6 ie last element of left part of 30.

A = {6,10,15,17,18,30,95,120,250}

This is the array after the third pivot. Here 6 was smallest so all elements moved to right.

==============4th PIVOT =====================

Now 6 has not left part. So we start with right part to move up the recursion. So, Pivot choosen is 18.

A = {6,10,15,17,18,30,95,120,250}

This is the array after the fourth pivot. 18 was at the correct postion as there is no greater element than 18.

If we move forward we see that 17,15 and 10 are at the correct positon! These will be 5th,6th and 7th pivot.

A = {6,10,15,17,18,30,95,120,250}

Now, recursion moves forward and checks right of 95.

So, 120 and 250 are at correct position

A = {6,10,15,17,18,30,95,120,250}