Answer to Question #133593 in Algorithms for Cheng

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:
[101, 102, 100, 104, 108, 106, 108, 110, 114, 109]
From the resulting array above, determine how many integers could have been the pivot?
Note: elements == pivot are partitioned to the right.

Answer 1

These integers can be found by determining what elements are on left and right. After the first pass, the elements on left and right must be smaller and greater respectively. Thus the pivots may be

104

108

110