Answer to Question #132512 in Algorithms for Michael

Question

An array of 11 integers is being sorted in ascending order using Quicksort.
Suppose the algorithm has just finished the first pass of partitioning and pivot swapping thus changing the content of the original array into the following array:
[101, 103, 110, 106, 107, 100, 109, 111, 104, 112, 115]

From the resulting array above, determine how many integers could have been the pivot?
Note: elements == pivot are partitioned to the right.

Answer 1

Numbers 101, 103, 110, 106, 107 cannot be pivots, because to the right of them there is a number 100 less than each of these numbers.

For the number 100, there is a number 101 greater than 100 to the left of it, hence 100 is not a pivot. Numbers 109, 111 are not pivots, because to the right of them there is a number 104 less than each of these numbers.

For the number 104, there is a number 110 greater than 104 to the left of it, hence 104 is not a pivot.

112 can be a pivot because all the numbers to the left of it are less than 112 and all the numbers to the right of it are greater than 112.

115 can also be a pivot because all the numbers to the left of it are less than it.

Answer: 112, 115.