Answer to Question #132511 in Algorithms for Michael

Question

An array of 10 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:
[100, 107, 110, 101, 105, 106, 109, 111, 114, 112]

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

Answer 1

100 can be a pivot because all the numbers to the right of it are greater than it.

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

Numbers 101, 105, 106, 109 cannot be pivots, because to the left of them there is a number 110 greater than each of these numbers.

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

For the number 114, there is a number 112 less than 100 to the right of it, hence 114 is not a pivot.

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

Answer: 100, 111.