Question

Choose a pivot using the median of 3 technique and show the result after 1 pass of quicksort (stop just before choosing a 2nd pivot) for the list [ 85, 40,60, 30, 55, 63, 70, 75 ,25]

Answer 1

Given List

Step 1:

Select the pivot.

Move the pivot to the end.

Step 2:

Partition the subarray.

Move the left bound to the right until it reaches a value greater than or equal to the pivot.

That is as far as we go this round.

Move the right bound to the left until it crosses the left bound or finds a value less than the pivot.

Step 3:

Step left.

Swap the selected values.

Step 4:

Move the left bound to the right until it reaches a value greater than or equal to the pivot.

Step right.

That is as far as we go this round.

Step 5:

Move the right bound to the left until it crosses the left bound or finds a value less than the pivot.

Step left.

That is as far as we go this round.

Step 6:

Swap the selected values.

Step 7:

Move the left bound to the right until it reaches a value greater than or equal to the pivot.

Step right.

Step 8:

That is as far as we go this round.

Move the right bound to the left until it crosses the left bound or finds a value less than the pivot.

Step 9:

Step left.

Bounds have crossed.

When the right bound crosses the left bound, all elements to the left of the left bound are less than the pivot and all elements to the right are greater than or equal to the pivot.

Move the pivot to its final location.

Step 10:

Call quicksort on the left sublist.

Select the Second pivot.