Quick Sort quiz



After the first partitioning operation is complete, what are the possible positions for the smallest item in the array? Assume that no items are equal.

It must be in the 0th position.
It must be to the left of the pivot.
It can be anywhere.
It can be anywhere but the last position.


Suppose we do not shuffle, and we attempt to quicksort an ordered array. Where will the first pivot end up? Assume no items are equal.

At the front.
At the back.
It depends on the input.


Suppose we partition an array of size 1251 and the pivot ends up in position 867. What is the entire set of positions in which the median might be found? Assume no elements are equal to each other.

Positions 0 through 434.
Positions 0 through 625.
Positions 0 through 866.
Any position.


If we have an array of size N with only 3 different values for its elements, what is the approximate probability that the first partition results in a completely sorted array? Assume there are an equal number of each element in the array.

0%
33%
67%
100%